0511 Who Are The Student Yet To Submit
#include<stdio.h>
#include<string.h>
int main(){
bool nos[31];
int no,i;
memset(nos,true,31);
for(i=0;i<28;i++){
scanf("%d",&no);
nos[no]=false;
}
for(i=1;i<31;i++){
nos[i]?printf("%d\n",i):i;
}
}
0512 Caesar Cipher
解法
簡単なのでそのまま書くだけです。
#include<stdio.h>
int main(){
char c[1001];
scanf("%s",c);
for(int i=0;c[i]!='\0';i++){
c[i]=(c[i]-'A'+23)%26+'A';
}
printf("%s\n",c);
}
0513 Shuffle The Cards
#include<stdio.h>
#include<string.h>
int main(){
int now[201],next[201],n,m,k,i;
scanf("%d %d",&n,&m);
for(i=0;i<2*n;i++)now[i]=next[i]=i+1;
for(i=0;i<m;i++){
scanf("%d",&k);
if(k==0){
for(int i=0;i<2*n;i+=2){
next[i]=now[i/2];
next[i+1]=now[i/2+n];
}
memcpy(now,next,sizeof(next));
}else{
memcpy(next+(2*n-k),now,4*k);
memcpy(next,now+k,4*(2*n-k));
memcpy(now,next,2*4*n);
}
}
for(int i=0;i<2*n;i++) printf("%d\n",now[i]);
}
0514 Quality Checking
解法
合格した組の部品はすべて良品です。
後は良品2つ不良品一つで不合格となっているセットから不良品を見つけ出せばいいわけです。
#include <stdio.h>
#include <algorithm>
bool search();
int main()
{
while(search()){
}
}
bool search()
{
int as[102],bs[102],cs[102];//部品が適正なら1、不適なら0、判断つかずなら2
int a,b,c,sa,sb,sc;
int dataA[1002],dataB[1002],dataC[1002],kekka[1002];//結果の保存
scanf("%d %d %d",&a,&b,&c);
if(a==0 && b==0 && c==0) return false;
int n;
sa=1;
sb=a+1;
sc=sb+b;
scanf("%d",&n);
int m=std::max(std::max(a,b),c);
for(int i=0;i<m;i++){
as[i]=bs[i]=cs[i]=2;//最初全製品を不明とする
}
for(int i=0;i<n;i++)
{
scanf("%d %d %d %d",&dataA[i],&dataB[i],&dataC[i],&kekka[i]);
dataA[i]-=sa;dataB[i]-=sb;dataC[i]-=sc;
if(kekka[i]==1){
//合格であった場合3つとも良品とする
as[dataA[i]]=bs[dataB[i]]=cs[dataC[i]]=1;
}
}
for(int i=0;i<n;i++)
{
//判別できるのは二つが良品で一つが不良品で不合格となっている場合のみ
if(kekka[i]==0){
if(as[dataA[i]]==1&&bs[dataB[i]]==1)cs[dataC[i]]=0;
if(as[dataA[i]]==1&&cs[dataC[i]]==1)bs[dataB[i]]=0;
if(bs[dataB[i]]==1&&cs[dataC[i]]==1)as[dataA[i]]=0;
}
}
for(int i=0;i<a;i++) printf("%d\n",as[i]);
for(int i=0;i<b;i++) printf("%d\n",bs[i]);
for(int i=0;i<c;i++) printf("%d\n",cs[i]);
return true;
}
0515 School Road
#include<stdio.h>
#include<string.h>
int a,b;
void calc(){
int map[17][17];
bool stops[17][17];
memset(map,0,sizeof(map));
memset(stops,false,sizeof(stops));
int n,x,y;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&x,&y);
stops[x][y]=true;
}
map[1][1]=1;
for(int x=1;x<=a;x++){
for(int y=1;y<=b;y++){
if(stops[x][y])continue;
map[x][y]+=map[x-1][y]+map[x][y-1];
}
}
printf("%d\n",map[a][b]);
}
int main(){
while(1){
scanf("%d %d",&a,&b);
if(a==0 && b==0) break;
calc();
}
}
0516 Maximum Sum
#include<stdio.h>
int n,k;
void calc(){
int sum=0,as[100001],a,max,p=0;
for(int i=0;i<k;i++){
scanf("%d",&a);
sum+=a;
as[i]=a;
}
max=sum;
for(int i=k;i<n;i++){
sum-=as[p];
scanf("%d",&as[p]);
sum+=as[p];
p=(p+1)%k;
if(max<sum)max=sum;
}
printf("%d\n",max);
}
int main(){
while(1){
scanf("%d %d",&n,&k);
if(n==0 && k==0) break;
calc();
}
}
0517 Longest Steps
解法
ソートして手前から集計していくだけです。
#include<stdio.h>
#include<vector>
#include <algorithm>
int n,k;
void calc(){
std::vector<int> nos;
int a,old=0,now=1,mode=0,ans=1,sum;
for(int i=0;i<k;i++){
scanf("%d",&a);
if(a==0){
mode=1;
}else{
nos.push_back(a);
}
}
std::sort(nos.begin(),nos.end());
for(int i=0;i<nos.size()-1;i++){
if(nos[i]+1==nos[i+1]){
now++;
}else if(nos[i]+2==nos[i+1] && mode==1){
sum=now+old+1;
ans=sum>ans?sum:ans;
old=now;
now=1;
}else if(nos[i]+2<nos[i+1] && mode==1){
sum=now+old+1;
ans=sum>ans?sum:ans;
now=1;
old=0;
}else{
ans=now>ans?now:ans;
now=1;
old=0;
}
}
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d %d",&n,&k);
if(n==0 && k==0)break;
calc();
}
}
0518 The Oldest Site
解法
2点を結ぶ線分ABをA、Bを中心にそれぞれ90度、-90度回した先に点があればそれは正方形をなす。
ということを利用して解きます。
私の場合高速化とかあまりまじめにやらないほうなのでわかりやすさ重視で実装しています。
#include<stdio.h>
#include<set>
#include <algorithm>
void solve(int n);
int menseki(int x1,int y1,int x2,int y2);
class point{
public:
int x,y;
bool operator<(const point& p) const
{
if(x!=p.x) return x<p.x;
return y<p.y;
}
};
std::set<point> points;
std::set<point>::iterator it;
int xs[3001],ys[3001];
int main()
{
int n;
scanf("%d",&n);
while(n!=0){
solve(n);
scanf("%d",&n);
}
}
void solve(int n)
{
points.clear();
point p;
for(int i=0;i<n;i++){
scanf("%d %d",&xs[i],&ys[i]);
p.x=xs[i];
p.y=ys[i];
points.insert(p);
}
//2点が決まれば残りの2点が決まることを利用してループで解く
int mensekiMax=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
mensekiMax=std::max(mensekiMax,menseki(xs[i],ys[i],xs[j],ys[j]));
}
}
printf("%d\n",mensekiMax);
}
int menseki(int x1,int y1,int x2,int y2){
int vx=x1-x2;
int vy=y1-y2;
//90度回転
int rx=-vy;
int ry=vx;
point p1,p2;
p1.x=rx+x1;
p1.y=ry+y1;
p2.x=rx+x2;
p2.y=ry+y2;
if(points.find(p1)!=points.end() && points.find(p2)!=points.end()){
return vx*vx+vy*vy;
}
//-90度回転
rx=vy;
ry=-vx;
p1.x=rx+x1;
p1.y=ry+y1;
p2.x=rx+x2;
p2.y=ry+y2;
if(points.find(p1)!=points.end() && points.find(p2)!=points.end()){
return vx*vx+vy*vy;
}
return 0;
}
0519
解法
問題をグラフに翻訳すると半順序集合の順番をつける問題だと判明します。
一位のチームに勝ったチームはいないのでまずはそのチームを探す。
一位のチームに入る↑と点を削除すると2位のチームに勝ったチームが存在しなくるので2位のチームが確定します。
後はこれを繰り返します。
ある順位を決めるとき複数のチームが3位候補や4位候補になるならそれは他の順位表の可能性を示唆するので他の順位表もありとなります。
ループをやめて優先順位付きキューを使えばもっと速度は出るけれど、実装の容易さを優先して記述した。
#include<stdio.h>
#include<set>
#include<vector>
int main(){
int n,m,a,b;
scanf("%d %d",&n,&m);
std::set<int> G[5001];
std::vector<int> dellList[5001];
for(int i=0;i<m;i++){
scanf("%d %d",&a,&b);
G[b].insert(a);
dellList[a].push_back(b);
}
int count=0;
int spents[5001]={0},ans=0;
while(count<n){
int perm=0;
std::vector<int> dells;
for(int i=1;i<=n;i++){
if(G[i].empty()&&spents[i]==0){
count++;
perm++;
spents[i]=1;
printf("%d\n",i);
dells.push_back(i);
}
}
for(int i=0;i<dells.size();i++){
int dellNo=dells[i];
for(int j=0;j<dellList[dellNo].size();j++)G[dellList[dellNo][j]].erase(dellNo);
}
if(perm>1)ans=1;
}
printf("%d\n",ans);
}
0520 Lightest Mobile
解法
saiki1関数では
モービルを上から下へ見ていきます。
一番下にたどり着いたら辺の比で最小の重りをつるします。
その重さの合計を上に返します。
上ではかえってきた重さと辺の比から、左右かえってきた重さを何倍の比にすればよいかを計算して上に返します。
最後にsaiki2で上から下へ辿り各重りを何倍にしていけばいいかを計算します。
少しコードサイズが膨らんでいますが変数名を省略しなかったから膨らんだと考えています。
#include<stdio.h>
#include<vector>
struct mobile{
int rightLen,rightNo,rightWeight,
leftLen,leftNo,leftWeight;
};
std::vector<mobile> mobiles;
int gcd(int a, int b)
{
int c;
while (b > 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int weightAns;
void saiki2(int now,int bai){
if(mobiles[now].rightNo==0){
weightAns+=bai*mobiles[now].rightWeight;
}else{
saiki2(mobiles[now].rightNo,bai*mobiles[now].rightWeight);
}
if(mobiles[now].leftNo==0){
weightAns+=bai*mobiles[now].leftWeight;
}else{
saiki2(mobiles[now].leftNo,bai*mobiles[now].leftWeight);
}
}
int saiki1(int now){
int leftNo=mobiles[now].leftNo,rightNo=mobiles[now].rightNo;
int leftWeight,rightWeight,leftWeight2,rightWeight2;
if(leftNo==0 && rightNo==0){
leftWeight =1;
rightWeight=1;
}else if(leftNo==0 && rightNo!=0){
leftWeight =1;
rightWeight=saiki1(rightNo);
}else if(leftNo!=0 && rightNo==0){
rightWeight=1;
leftWeight =saiki1(leftNo);
}else{
rightWeight=saiki1(rightNo);
leftWeight =saiki1(leftNo);
}
leftWeight2 =leftWeight *mobiles[now].leftLen;
rightWeight2=rightWeight*mobiles[now].rightLen;
int t=gcd(rightWeight2,leftWeight2);
mobiles[now].rightWeight=leftWeight2/t;
mobiles[now].leftWeight =rightWeight2/t;
int ans=mobiles[now].leftWeight*leftWeight+mobiles[now].rightWeight*rightWeight;
return ans;
}
void setData(int n){
mobiles.clear();
mobile m;
mobiles.push_back(m);
int topMobile=1;
std::vector<int> upMemo;
upMemo.resize(102);
for(int i=0;i<102;i++)upMemo[i]=-1;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&m.leftLen,&m.rightLen,&m.leftNo,&m.rightNo);
mobiles.push_back(m);
upMemo[m.leftNo]=upMemo[m.rightNo]=i+1;
}
while(upMemo[topMobile]!=-1){
topMobile=upMemo[topMobile];
}
weightAns=0;
saiki1(topMobile);
saiki2(topMobile,1);
printf("%d\n",weightAns);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
最終更新:2013年03月11日 03:22