日記管理人 堀江伸一 〒675-0033-79-16 *2011/2/17 会津大学オンラインジャッジ。 さすがに170門も解くと気楽に解ける問題が減ってくる。 0～100までは、簡単問題中心。 まずはプログラムに慣れましょう というレベル。 100～200はプログラムをおもちゃ代わりに簡単な問題解きましょう。 というレベルだな。 まだ初歩的な教科書通りのアルゴリズムで解ける世界。 *2011/2/16 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0117&lang=jp リンク先問題をダイクストラ法で解くコード。 書きかけ。 一部テストデータでテストしてみたら不安のある結果になったので 一度書籍でダイクストラ法を確認しないといけない状態。 とりあえずの簡易データ。 7 9 1,2,8,8 1,3,4,4 1,7,3,3 2,6,1,1 3,4,5,5 4,5,2,2 5,6,7,7 5,7,1,1 6,7,2,2 2,5,10,10 点３から点２、点２から３への最短移動距離の合計がおかしい #include <stdio.h> void search(int s,int g); int map[21][21]; int values[21]; int m=1000000000; int n; int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ map[i][j]=m; } values[i]=m; } int a,b,c,d; for(int i=0;i<m;i++){ scanf("%d,%d,%d,%d",&a,&b,&c,&d); map[a][b]=c; map[b][a]=d; } int x1,x2,y1,y2; printf("test\n"); scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2); search(x1,x2); } void search(int s,int g){ int start=s; int goal=g; int min; values[start]=0; for(int k=1;k<=n;k++) { min=m; for(int i=1;i<=n;i++) { if(min>values[i]) { min=values[i]; } } if(min==m) break; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(values[j]>map[j][i]+values[i]) { values[j]=map[j][i]+values[i]; } } } } for(int i=1;i<=n;i++){ printf("v[%d]=%d\n",i,values[i]); } } *2011/2/14 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0235&lang=jp を解くコード。 何か無駄にコードが長くなるのが僕の特徴。 冗長性が信頼性につながらないのがプログラムの世界。 無駄は省きたいものである。 以下書きかけ #include <stdio.h> void solve(int n); int times[21][21];//島のつながりと橋の時間を表す int moves; int moveCount; int sum; bool moveOKs[21]; int main() { int n; scanf("%d",&n); while(n!=0){ solve(); scanf("%d",&n); } } void solve(int n) { int count,p1,p2; moves=n-1;//移動する橋の数 moveCount=0;//移動した橋の数 int i1,i2,t; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ times[i][j]=0; } moveOKs[i]=true;//移動前ならtrue } for(int i=0;i<n-1;i++){ scanf("%d %d %d",&i1,&i2,&t); times[i1][i2]=t; times[i2][i1]=t; } //頂点になる橋は計算にいらないので削除する for(int i=2;i<n;i++){ count=0; for(int j=1;j<n;j++){ if(times[i][j]>0){ count++; p1=i; p2=j; } } if(count==1){ times[p1][p2]=times[p2][p1]=0; moves--;//移動しなくていい橋が一つ減る } } } void search(int islandNO,int n,int parentsNo){ //islandnoは今いる島、 parentsNoは前にいた島； if(moveCount>=moves){ return ; } for(int i=1;i<=n;i++){ if(parentsNo!=i && times[islandNO][i]>0){ sum+=times[islandNO][i]; if(moveOKs[i]==true){ moveCount++; moveOKs[i]=false; } search(); } if(moveCount>=moves){ return ; }else{ sum+=times[islandNO][i]; } } } *2011/2/14 ７パズルを解くコード。 完成状態から探索を初めて、ダイクストラ法であるパターンに行きつくまで何手必要か。 をすべてのパタンで求めて解いた。 パズルが小さいから何とかなる方法で、もっと大きなパズルになるとこの手法は使えなくなる。 もっと根本的な手法が必要？ #include <stdio.h> #include <map> void moveOKStage(int,int); void search(int); void move(int,int,int,int); int rs[9]; std::map<int,int>::iterator it; std::map<int,int> next; std::map<int,int> moveOK; std::map<int,int> moves; int main(){ int s,r,keta=1; for(int i=8;i>=0;i--){ rs[i]=keta; keta*=10; } search(123456780); while(scanf("%d",&s)!=EOF){ s++; s*=rs[0]; for(int i=1;i<8;i++){ scanf("%d",&r); s+=(r+1)*rs[i]; if(r==0){ s+=i; } } printf("%d\n",moves[s]); } } void search(int start){ int s; int cC=0; moveOKStage(start,0); int p; moveOK.swap(next); while(1){ next.clear(); cC++; it=moveOK.begin(); while(it!=moveOK.end()){ s=(*it).second; p=s%10; move(p,p+1,s,cC); move(p,p-1,s,cC); move(p,p+4,s,cC); move(p,p-4,s,cC); it++; } if(next.size()<1){ break; } moveOK.swap(next); } } void move(int p1,int p2,int s,int deep){ if(p1<0 || p1>7 || p2<0 || p2>7){ return ; } if((p1==3 && p2==4) || (p1==4 && p2==3)){ return ; } int u=s; u=u+((u/rs[p2])%10)*(rs[p1]-rs[p2])-rs[p1]+rs[p2]; u=u-p1+p2; moveOKStage(u,deep); } void moveOKStage(int u,int deep){ if(moves.count(u)==0){ moves[u]=deep; next[u]=u; } } *2011/2/14 7パズルを解くコード。 コードの短縮と実行速度加速とメモリ使用量の低下のバランスを目指してみた。 こういう問題はビット演算で解くのが本質なのだけど、その方法を知らないので、7パズルの状態を8ケタの数字+空き枡のある位置の情報1ケタの数字、計9ケタとして実装してみた。 とりあえずコードを書いただけで未テスト。 、、、テスト中、、、 うーん、テストデータによる結果は時間切れ。 これは逆かな？ 最初にダイクストラ法を使ってキューブの全状態の関係を求める方法を使えばいいのだろうか？ #include <stdio.h> #include <map> bool moveOKStage(int); void search(int); bool move(int,int,int); int rs[9]; std::map<int,int>::iterator it; std::map<int,int> next; std::map<int,int> moveOK; std::map<int,int> moves; int main(){ int s,r,keta=1; for(int i=8;i>=0;i--){ rs[i]=keta; keta*=10; } while(scanf("%d",&s)!=EOF){ s++; s*=rs[0]; for(int i=1;i<8;i++){ scanf("%d",&r); s+=(r+1)*rs[i]; if(r==0){ s+=i; } } printf("s=%d ",s); search(s); } } void search(int start){ bool cF=false; moveOK.clear(); next.clear(); moves.clear(); int s; int cC=0; if(moveOKStage(start)==true){ printf("0\n"); return ; } int p; moveOK.swap(next); while(1){ next.clear(); cC++; it=moveOK.begin(); while(it!=moveOK.end()){ s=(*it).second; p=s%10; cF=move(p,p+1,s)|move(p,p-1,s)|move(p,p+4,s)|move(p,p-4,s); if(cF){ printf("%d\n",cC); return ; } it++; } if(next.size()<1){ break; } moveOK.swap(next); } } bool move(int p1,int p2,int s){ if(p1<0 || p1>7 || p2<0 || p2>7){ return false; } int u=s; u=u+((u/rs[p2])%10)*(rs[p1]-rs[p2])-rs[p1]+rs[p2]; u=u-p1+p2; return moveOKStage(u); } bool moveOKStage(int s){ if(s==123456780){ return true; } if(moves.count(s)==0){ moves[s]=1; next[s]=s; } return false; } *2011/2/14 strrev(一伸江堀) 平面板の上に回転するローラーを複数用意。 このローラにチェーンを巻きつけ、チェーンが一周するように張る。 チェーンには磁石を張り付け、チェーンの外周は一定間隔でコイルで編まれたホースで囲む。 これで電気を流せばモータにならないかしら？ *2011/2/12 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0554 リンク先問題を解くコードを書いてみた。 #include <stdio.h> int main(){int a,b,c,d,s;scanf("%d %d %d %d",&a,&b,&c,&d);s=a+b+c+d;printf("%d\n%d\n",s/60,s%60);} これ以上どうやってコードを短くするのか？ アマチュアプログラマである僕にとって謎だ。 後45文字も短くできるらしい？ ええええ？ 謎すぎる。 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0106&lang=jp この問題、ナップザック問題の亜種かもしれないので、探索で解いたけど、もしかしたら探索いらなかったかもしれない？ C店、B店、A店の順で選ぶ貪欲法でいけたかな？ 後、欠片も汎用性がないコードを書いてしまったorz. 書いた後で気がついた。 A,B,Cからどれだけ選ぶかを ３重forループで回せばいいだけじゃん、そしたら計算量小さくなったし(爆) なんという無駄コード（爆） 今日書いたコード。 #include <stdio.h> #include <stdlib.h> int money[51]; bool moveOK[26][18][11]; void search(); void solve(); void saiki(int wsum,int a,int b,int c); int main(){ int n; search(); scanf("%d",&n); while(n!=0){ n=n/100; printf("%d\n",money[n]); scanf("%d",&n); } } void solve(){ for(int i=0;i<51;i++){ int min=money[i]; for(int j=i;j<51;j++){ if(min>money[j]){ min=money[j]; } } money[i]=min; } } void search(){ for(int i=0;i<26;i++){ for(int j=0;j<18;j++){ for(int k=0;k<11;k++){ moveOK[i][j][k]=true; } } } for(int i=0;i<51;i++){ money[i]=1000000; } saiki(0,0,0,0); } void saiki(int wsum,int a,int b,int c){ if(wsum>50){ return ; } if(moveOK[a][b][c]==false){ return ; }else{ moveOK[a][b][c]=false; } int m=(a/5)*1520+(a%5)*380+(b/4)*1870+(b%4)*550+(c/3)*2244+(c%3)*850; if(m<money[wsum]){ money[wsum]=m; } saiki(wsum+2,a+1,b,c); saiki(wsum+3,a,b+1,c); saiki(wsum+5,a,b,c+1); } *2011/2/10 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0042&lang=jp うーん？ この問題はナップザック問題の亜種かな？ 簡単な解法としては、mapを使いキーを重さ、値を宝の価値と定義する。 最初にmapに品物を入れる。 mapの要素を順番に取り出し、それに ある品物を足す、足さないを順番に行い、新しい重さと価値でkeyに代入を行う。 このときKeyがもう埋まっているならより価値の大きい方でkeyの値を更新する。 keyがまだ存在しないならその値でkeyを更新する。 keyが重さの総和を超えたら、それは無視する。 全ての品物のチェックが終わった時 最後にイテレータを回して、mapの中で一番値の大きいものを探す？ という方法を考えついたのだけど、あっているかどうか少し自信がない。 問題はmapの中身が恐ろしい個数になる可能性がある点。 ジャッジ通るといいなあ。 *2011/2/8 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0126&lang=jp 書きかけの数独の間違いをチェックするコード。 問題を読んでから何分で解けるかの早解きを目指したが何か無駄が多い気がする、それにコードが間違っていたのでやり直し。 早解きは苦手。 #include <stdio.h> #include <map> int main(){ int n; } void search(){ int map[9][9]; int NoCount[9]; int t; std::map<int,int> err; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ NoCount[i]=0; } for(int j=0;j<9;j++){ scanf(" %d",&t); if(NoCount[t]==0){ NoCount[t]=1; }else{ err[i*9+j]=1; } map[i][j]=t; } } for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ NoCount[j]=0; } for(int j=0;j<9;j++){ t=map[j][i]; if(NoCount[t]==0){ NoCount[t]++; }else{ err[i*9+j]=1; } } } for(int i=0;i<9;i+=3){ for(int j=0;j<9;j+=3){ for(int k=0;k<9;k++){ NoCount[k]=0; } for(int k=0;k<9;k++){ if(NoCount[map[i+k/3][j+k%3]]==0){ NoCount[map[i+k/3][j+k%3]]=1; }else{ err[(i+k/3)*9+j+k%3]=1; } } } } for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(err.count(i*9+j)==1){ printf("*%d",map[i][j]); }else{ printf(" %d",map[i][j]); } } printf("\n"); } } *2011/2/8 http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.jsp?id=sinapusu2002 会津大学のプログラムの問題集、現在138問解。 さすがにこれだけ解くと気楽に解ける問題が無くなってくる。 答えや考えかたは検索すれば良いコードが見つかるんだけど自分で解くのが大事かなと考えて、解いた後だけ参考程度に見てる。 解く前は、足元すくってくるような意地悪なデータがあったらどうしようとか、計算誤差が問題になる微妙な問題はどう解くかとか色々悩むのですが 解き終わった後にみるとこんな簡単な問題で悩んだりしてたのかと思ったり。 こういうのってプログラマとして少しは成長してるのかな？ さすがにこれだけ解いてるとただ解くだけでなく、実行速度一位とかコードの短さ一位とかに興味がわく。 変数一文字、改行削除してまで稼ぐコードの短さは興味がないので、コードの短さはそこそこでいいけど、実行速度上位はとりたくなるところ。 *2011/2/4 SFネタ記録 -スピークバード 音を発する機能を持った飛行ロボ。 歩兵用装備。 遠隔操作で飛ばし、足音や人の声、銃声等を発することができ、その地点に人がいると思わせる効果を持っている。 GPS誘導で目標地点まで移動するサイボーグ系のスピークマウス等もいる。 移動経路はネズミの脳まかせ、脳に端子が埋め込まれ、背中に装備一式を背負うことが可能で目的地まで移動してカメラ偵察、音声欺瞞を行う能力を持つ。 装備は太った鼠に見えるようカバーで覆われる。
