北京大学ではプログラマ向け練習問題を多数掲載しています。 そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。 このサイトの問題を解いた記録を掲載しています。 プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。 とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。 *POJ1177 AOJに掲載のSheetという問題の亜種なのでそれを思い出しながら解く。 考え方さえわかっていればそんなに難しい問題ではない。 問題は速度が出なかったこと。 AOJでは最速クラスのコードを叩き出した私ですが世界では遅かった。 AOJは日本国内限定、熱心な参加者も少ないしどうしても限定されたランクになる、熱心なのは300人ほど。 それに対しPOJは参加者が圧倒的に多い、むむむこれが世間の標準レベル、このレベルでコード実行速度を競うことでようやく世間の平均値に辿りつけるのかと感心。 AOJでは結構実行速度の速いコードを書いてるほうの私ですがPOJという世間一般レベルでの評価では遅い方。 まだまだ精進だなあと感じた次第。 今回のコードは最後のWhileとForの3重ループが悪かったのかも？ ループは重ねると遅くなるという実感はあるのだが、ループは楽だからなあつい使っちゃうんだよな。 #include<stdio.h> #include<queue> #include<string.h> #include<vector> struct point{ int xLeft,y,inOut,xRight; bool operator<(const point& p)const{ if(y!=p.y)return y>p.y; return inOut<p.inOut;//inが先に来るようにする } }; int main(){ int n; std::priority_queue<point> points; scanf("%d",&n); point p1,p2; p1.inOut=1; p2.inOut=-1; int inOutCounts[20003]; std::vector<int> inYPosMemo[20003]; memset(inOutCounts,0,sizeof(inOutCounts)); for(int i=0;i<n;i++){ scanf("%d %d %d %d",&p1.xLeft,&p1.y,&p2.xRight,&p2.y); p2.xLeft=p1.xLeft; p1.xRight=p2.xRight; points.push(p1); points.push(p2); } const int shift=10001; while(!points.empty()){ p1=points.top(); points.pop(); p1.xLeft+=shift; p1.xRight+=shift; for(int x=p1.xLeft;x<p1.xRight;x++){ inOutCounts[x]+=p1.inOut; if(inOutCounts[x]==0){ inYPosMemo[x].push_back(p1.y); }else if(inOutCounts[x]==1 && p1.inOut==1){ inYPosMemo[x].push_back(p1.y); } } } int ans=0,y1,y2,y3,y4,pLeft; for(int x=1;x<20002;x++){ ans+=inYPosMemo[x].size();//上下両端を足しこむ pLeft=0; for(int pNow=0;pNow<inYPosMemo[x].size();pNow+=2){ y3=inYPosMemo[x][pNow+1]; y4=inYPosMemo[x][pNow]; ans+=2*(y3-y4); while(pLeft<inYPosMemo[x-1].size()){ y1=inYPosMemo[x-1][pLeft+1]; y2=inYPosMemo[x-1][pLeft]; if(y4>=y1){ }else if(y2>=y3){ break; }else if(y3>=y1&&y1>=y4 && y4>=y2){ ans-=2*(y1-y4); }else if(y1>=y3&&y3>=y2&&y4>=y2){ ans-=2*(y3-y4); break; }else if(y1>=y3&&y3>=y2&&y2>=y4){ ans-=2*(y3-y2); break; }else if(y3>=y1&&y1>=y4&&y2>=y4){ ans-=2*(y1-y2); } pLeft+=2; } } } printf("%d\n",ans); } *poj1406 四角い燃料と三角錐の燃料を補給する問題。 簡単な問題なので中学生でもとけそう。 #include<set> #include<stdio.h> std::set<int> cube,pyramid; void setData(){ for(int i=0;i*i*i<=151200;i++){ cube.insert(i*i*i); } for(int i=0;(i*(i+1)*(i+2))/6<=151200;i++){ pyramid.insert((i*(i+1)*(i+2))/6); } } int main(){ setData(); int n,ans; std::set<int>::iterator it,it2; while(1){ scanf("%d",&n); if(n==0)break; ans=0; for(it=cube.begin();(*it)<=n&&it!=cube.end();it++){ it2=pyramid.upper_bound(n-(*it)); if(it2!=pyramid.begin())it2--; ans=(*it)+(*it2)>ans?(*it)+(*it2):ans; } printf("%d\n",ans); } } *poj1047 http://poj.org/problem?id=1047 142857*1～6までは12487を循環シフトしたものになっている。 あるｎ文字の数字が与えられるのでその数字に1～ｎ-1までをかけたものがその数字が循環シフトになっているかを求める問題。 簡単なので中学生でも解けそうです。 #include<stdio.h> #include<string> #include<iostream> #include<set> void add(std::string& num1,const std::string num2,int size){ int up=0; for(int i=size-1;i>=0;i--){ num1[i]+=num2[i]+up; up=num1[i]/10; num1[i]%=10; } //return up==1?false:true; } bool calcData(std::string num){ char t; int size=num.size(); std::set<std::string> nums; std::string fNum=num; for(int i=0;i<size;i++){ num[i]-='0'; fNum[i]-='0'; } for(int i=0;i<size;i++){ t=num[0]; for(int p=0;p<size-1;p++)num[p]=num[p+1]; num[size-1]=t; nums.insert(num); } for(int i=0;i<size-1;i++){ add(num,fNum,size); if(nums.find(num)==nums.end())return false; if(num==fNum)break; } return true; } int main(){ std::string num; while(1){ std::cin>>num; if(std::cin.eof())break; if(calcData(num)){ printf("%s is cyclic\n",num.c_str()); }else{ printf("%s is not cyclic\n",num.c_str()); } } } *poj1157 簡単な問題なので正答率を稼げるおいしい問題と思って挑戦する。 しょうもないポカミスに気づかず論理的に正しいのに何故正解にならないのかと不思議だった問題。 最初は読解ミスとはいえ読解後のWA３連続はダメージ大きいです。 動的計画法の計算部分のy<=hとx<=wを間違えてy<hとx<wにしていたというポカ、はい馬鹿発見ですね。 #include<stdio.h> #include <algorithm> const int sizeMax=103; void setData(){ int memo[sizeMax][sizeMax]; int score[sizeMax][sizeMax]; int h,w; scanf("%d %d",&h,&w); for(int y=0;y<=h;y++){ for(int x=0;x<=w;x++){ memo[y][x]=-10000000; if(y!=h&&x!=w)scanf("%d",&score[y][x]); } } memo[0][0]=0; for(int y=0;y<h;y++){ for(int x=y;x<w;x++){ memo[y][x+1 ]=std::max(memo[y][x],memo[y][x+1]); memo[y+1][x+1]=std::max(memo[y][x]+score[y][x],memo[y+1][x+1]); } } printf("%d\n",memo[h][w]); } int main(){ setData(); } *poj1218 酔っ払った看守がドアを開放したり閉じたりしていく問題。 #include<stdio.h> #include<string.h> const int roomMax=102; bool lock[roomMax]; int ans[roomMax]; void setData(){ memset(lock,true,sizeof(lock)); for(int i=2;i<roomMax;i++){ for(int j=i;j<roomMax;j+=i){ lock[j]=!lock[j]; } } int count=0; for(int i=1;i<roomMax;i++){ count+=lock[i]?1:0; ans[i]=count; } } int main(){ int t,n; setData(); scanf("%d",&t); while(t--){ scanf("%d",&n); printf("%d\n",ans[n]); } } *poj1080 http://poj.org/problem?id=1080 ２つのDNAデータからDNAの類似度をスコアーとして算出する問題。 典型的な動的計画法の問題で楽々です。 #include<stdio.h> #include<iostream> #include<string> #include <algorithm> int dnaScore[5][5]={ {5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,0}}; int dnaToNo(char t){ if(t=='A'){ return 0; }else if(t=='C'){ return 1; }else if(t=='G'){ return 2; }else if(t=='T'){ return 3; }else{ return 4; } } void setData(){ int len1,len2,score; int memo[102][102];//memo[1つめのDNAをM文字目まで読んで][２つ目のDNAをN文字目]まで読んだ場合の最大値 for(int x=0;x<102;x++){ for(int y=0;y<102;y++)memo[x][y]=-1000000;//一列ずつの動的計画法 } std::string dna1,dna2; std::cin>>len1>>dna1; std::cin>>len2>>dna2; if(len1<len2){ //dna1を長くしてコードを簡単にする std::swap(len1,len2); std::swap(dna1,dna2); } memo[0][0]=0; for(int x=0;x<len1;x++){ for(int y=0;y<len2;y++){ score=memo[x][y]+dnaScore[dnaToNo(dna1[x])][dnaToNo(dna2[y])]; memo[x+1][y+1]=std::max(memo[x+1][y+1],score); score=memo[x][y]+dnaScore[dnaToNo(dna1[x])][4];//-にして読み飛ばす memo[x+1][y]=std::max(memo[x+1][y],score); score=memo[x][y]+dnaScore[4][dnaToNo(dna2[y])]; memo[x][y+1]=std::max(memo[x][y+1],score); } } printf("%d\n",memo[len1][len2]); } int main(){ int t; scanf("%d",&t); while(t--){ setData(); } } *poj1163 http://poj.org/problem?id=1163 三角形に配置された数字を上から下へ移動しながら合計値が最大となるルートを見つけその数を返す問題。 #include<stdio.h> #include<string.h> #include <algorithm> int main(){ int n,l,t,ans=0; int memo[102][102]; scanf("%d",&n); memset(memo,0,sizeof(memo)); for(int y=1;y<=n;y++){ for(int x=1;x<=y;x++){ scanf("%d",&t); memo[y][x]=std::max(memo[y-1][x-1]+t,memo[y-1][x]+t); ans=std::max(ans,memo[y][x]); } } printf("%d\n",ans); } *poj3748 Bit演算をする問題。 Bit演算は苦手なので少しコードが冗長。 #include<stdio.h> int main(){ int r,x,y; int bit; scanf("%x,%d,%d",&r,&x,&y); bit=~(1<<(x)); r&=bit; bit=~(7<<(y-2)); r&=bit; bit=6<<(y-2); r|=bit; printf("%x\n",r); } *poj1019 http://poj.org/problem?id=1019 数列を繋げて文字列を作った時、i文字目にどんな数字が入ってるかを答える問題。 何個目の数列かを計算して、めんどくさかったので後は力づくで答えた。 #include<stdio.h> #include<set> #include <sstream> #include <iostream> #include <string> std::set<int> datas; std::string nums; int saiki(int num,int num9,int deep,int sum){ if(num<=num9)return num*deep+sum; return saiki(num-num9,num9*10,deep+1,sum+num9*deep); } std::string IntToString(int num){ std::stringstream ss; ss<<num; return ss.str(); } void setData(){ datas.clear(); unsigned int sum=1; int i=1; datas.insert(0); while(sum<=2147483647){ datas.insert(sum); nums.append(IntToString(i)); i++; sum+=saiki(i,9,1,0); } } int main(){ int t,no,top; std::set<int>::iterator it; setData(); scanf("%d",&t); while(t--){ scanf("%d",&no); it=datas.lower_bound(no); if(it!=datas.begin())it--; std::cout<<nums[no-(*it)-1]<<"\n"; } } *poj2665 http://poj.org/submit?problem_id=2665 道路から木を撤去していく問題。 簡単な問題なので書くだけ。 #include<stdio.h> bool setData(){ int l,m; scanf("%d %d",&l,&m); if(l==0&&m==0)return false; int x1,x2; l++; while(m--){ scanf("%d %d",&x1,&x2); l-=(x2-x1+1); } printf("%d\n",l); return true; } int main(){ while(setData()){ } }
