*2011/4/13 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1049 リンク先は恐ろしく正答率の低い問題。 長期間一人しか正答者がいなかった難問。 正答者の数が増えたのは最近である。 統計情報を見ても不正解でグラフが真っ赤。 といっても世間的にはそんなに難しくはない問題なのかも。 本当に実力のある人は北京大学のオンラインジャッジとか、Google主催のオンラインジャッジ（ネット上でプログラマ向けの大会や問題集を扱ってるサイト）にいるから世間的にはたいしたことないのだろう。 AOJには実力のあるプログラマがそんなにいないから正解率が低いにすぎない。 AOJに集まる人にとっては難問だった、程度にすぎないのかも。 私もこの問題に挑戦。 この問題世間的には簡単に分類されるのだろうけど、私には難しく答えが出せない。 正しい答えを出すところまではいってるはずなんだけど、実行時間が長すぎて不正解を喰らう。 コードを効率化する方法がわからない。 家の数が１０軒でも全探索で10！*45程度の計算量 ３６０万*45回の計算量になる。 どうやって計算量を落とせばいいんだ？ #include <algorithm> #include <stdio.h> void setMap(int n); int main(){ int n; while(scanf("%d",&n)!=EOF){ setMap(n); } } void setMap(int n){ int map[10][10]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ //データの読み込み scanf("%d",&map[i][j]); } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ //より遠ざけたい人を基準に map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]); } } int lens[10];//ある並びで家が並んだ時の各人の家の位置 int *hp=new int[n];/各人の家の並び順 int min=2100000000;//21億 for(int i=0;i<n;i++) hp[i]=i; do{ for(int i=0;i<n;i++) lens[i]=0; //各人の家が特定の並び順になった時、家をぎちぎちに詰めた場合の最短の長さを求める処理 for(int i=0;i<n;i++) { for(int j=0;j<i;j++){ lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]); } } min=std::min(lens[n-1],min); }while(std::next_permutation(hp, hp+n));//家の全ての並び順を求める printf("%d\n",min);//答え delete [] hp; } *2011/4/4 http://dixq.net/rp/ 今日からリンク先を参考にSTG作りを開始。 今日はボードの表示まで完了。 良いサイトである。 設計図をきちんと引いてゲームを作るとどれだけうれしいかが実感できる導入。 多人数で開発を分担できるプログラム開発とは何かが分かる設計。 ゲーム作りのみならず、プログラムを書く時cppファイルをどう分けていくかというアプリ開発の基本が身に付く感じ。 しかも段階を追って学習できるので、C++の基礎が終わっている人なら一人でも学習できる親切設計。 学習に必要な時間も決して長くはない。 解説が高校生でもわかるほどにやさしい。 これで無料！ 驚くばかりにいい感じのサイトである。 名前 堀江伸一 住所 兵庫県加古川市加古川町南備後79-16 *2011/4/5 http://dixq.net/rp/ 今日は敵を表示させてみようまでコードを書く。 うーん理解しながら勉強すると時間がかかるなあ。 前半結構手間の多い処理記述が中心だけど、全ては後半楽をするための処理。 なのだ。
