※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「アルゴリズム勉強日記」の編集履歴(バックアップ)一覧に戻る

アルゴリズム勉強日記 - (2011/05/29 (日) 09:44:07) の最新版との変更点

追加された行は青色になります。

削除された行は赤色になります。

 http://rose.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja
 リンク先は会津大学オンラインジャッジというプログラマ向け問題集を扱ったサイトです。
 私はこのサイトでsinapusu2002という名前で登録しプログラムの問題集を解いてます。
 
 私の成績
-http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.jsp?id=sinapusu2002
+http://judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=sinapusu2002
 
 
 極力自力で解こうとしていますが、どうしても解けない問題は検索して答えを見たり、掲示板で質問して解いてます。
 その際のカンニング履歴を記録することにしました。
-個人的なものです。
+個人的なもので、自分一人が分かれば十分な記録です。
 
 
 
 カンニング履歴
 ----
 1
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
 Problem E: 忍者のビル登り
 ポカミスによる場合分けの見落としに気付かず解けず。
 掲示板で質問し、親切な方にテストデータを用意してもらいそのデータをきちんと処理できるまで修正して提出。
 
 
 
 
 
 
 ----
 2
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0112&lang=jp
 A Milk Shop
 解法は正しかったがlong long 型の存在を知らずに解けず。
 掲示板でlong longの存在を教えてもらい解く
 
 
 
 
 
 
 ----
 3
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0080&lang=jp
 0080 : Third Root
 ポカミスで計算式の終了条件を勘違いして解けず。
 ネットで検索して答えを見て納得して解く。
 本当につまらないミスだった。
 
 
 
 
 
 ----
 4
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0059&lang=jp
 0059 : Intersection of Rectangles
 最初、自分で考えた非効率な方法による処理で一応解く。
 効率的な方法があるだろうなと考え、ネットで検索した方法を提出して合格。
 
 
 
 
 
 
 ----
 5
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0033&lang=jp
 Problem 0033 : Ball
 帰納法で解こうとして何故か解けず。
 ネットで答えを検索、全探索で解く。
 
 
 
 
 
 ----
 6
 Problem 0114 : Electro-Fly
 最初、何も考えずに解こうとするも時間切れ。
 掲示板でアドバイスを待ってる間に、GCDとLCMを組み合わせる方法を思いつくも自信が持てず。
 掲示板でも同じ方法で解くことを進めてもらい自信を持って解く。
 
 
 
 
 
 ----
 7
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0125&lang=jp
 最初、月日年を個別に計算して経過日数をちまちま計算する効率の悪い方法で解く。
 きちんと解けるも、素人考えでは思いつかない方法があるに違いないとネットで検索。
 西暦0年からの経過日数を導き出す公式を使いそちらを提出してクリア。
 
 
 
 
 ----
 8
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0529&lang=jp
 0529 : Darts
 この問題最初ナップザック法で解こうとして惨敗。
 ナップザック法では100万*100万の組み合わせを調べることになるので当然時間切れ。
 次にSetを使い、1回だけの組、2回の組み合わせ全てをsetに、
 1回の組+それで最高点になる2回の組をsetから
 2回の組+残り点数で最高点になる2回の組をsetから。
 という考え方で解こうとするも少しだけ計算時間が長く不正解。
 考え方は正しかったが使った道具setが悪かった。
 ネットで検索したバイナリサーチを使った方法に修正して合格。
 
 
 
 
 ----
 9
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0557&lang=jp
 これもlong long型を知らなかったために最初解けず。
 解法は正しかったがlonglongをしらないために解けず。
 掲示板でlong longの存在を教えてもらい解く。
 
 
 
 
 ----
 10
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0090
 Problem 0090 : Overlaps of Seals
 最初、円周上を点が回った時、シール上に点がはいるはいらないという複雑な方法で解こうとするも計算誤差を制御できず惨敗。
 他の方の考え方をぱっと見覗いて、それをヒントにコードを記述して解く。
 交点が他のシールの中にあるかないかで解くとシンプルな方法に関心。
 
 
 
 
 ----
 11
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1103
 英語が読めないために、問題を翻訳してもらいそれを参考に解く。
 英語を読めるのも問題のうちと考えたらカンニングになるかな。
 
 
 
 ----
 12
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1217
 家族図と質問文が与えられる。
 家族図に対して質問文が正しいならTrue、正しくないならFalseを返せ。
 この問題、木構造を作り上げて解くという手間のかかる方法で解く。
 struct node{
 	node* parentNode;//親のノード
 	std::string name;
 	std::vector<node> childNodes;//子のノード
 };
 木構造の幹からのびる幹の保存にvectorを使ったのが間違いの元。同一名称が出てこないということを使い高速化のためにmap<string,node*>に名前をキーにnodeのメモリ座標を保存するという方法を採用。
 vectorが拡張されるたびにメモリ位置がずれてmapに保存したメモリ座標とずれるいうことに気付かず、バグとりで何度もはまる。
 掲示板で理解力の低い私を見はなさないとても親切な方にご指摘を頂き解く。
 本当はこの問題親一人しかない木構造ということを利用してmap<string,string>で簡単に解ける。
 質問文の種類がある人の親の名前さえ得られれば答えられる質問のみというのが問題を解くカギ。
 この限りにおいてmap<string,string>で解ける。
 親戚を問う問題だったら木構造必須。
 
 
 
 ----
 14
 http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1155&lang=jp
 長ったらしいコードを書いてアセプト。
 コードが記号列を処理する時、)を見つけたら(を削除する時、-(という組み合わせがあッた場合の記述を処理し忘れたために不正解を喰らう。
 公開されているジャッジデータの存在を掲示板で教えてもらい、ジャッジデータをきちんと処理できるまでコードを修正してアセプト。
 どうしてもわからないので途中で他の人の答えをちらみもした。
 この問題驚くほど短いコードで解決できるらしいが一応自分で考えたコードでアセプトしたかったので参考にせず自前コードを微修正してアセプト。
 問題も解けたので短いコードを研究。
 短いコードは再帰下降構文解析という、状態遷移マシーンを再帰にすることで構文解析を可能にするテクニックらしい。
 何となく概念は理解。
 僕が自分で再帰下降で構文解析を書くとかなり時間がかかると思うけど、多分普通に情報系の授業を受けていたら誰にでも使いこなせるものだと思う。
 こういう時大学行っといたらよかったなと痛感、俺の知らないプログラムテクニックとか大学ならたくさんあるんだろうな。
 大学レベルの教育や研究とプログラムが結びつくと仕事がいっぱいあるんだろうなと考えたりはする。
 自前の長いコードはこちら。
 http://www14.atwiki.jp/c21coterie?cmd=upload&act=open&pageid=427&file=1155HowcanIsatisfytheeLetmecounttheways4.txt
 
 
 
 
 
 
 
 
 
 
 ----
 *15
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547
 普通に長めのコードでアセプト。
 今回のカンニングはコード記述後、提出前にテストデータでコードをチェックする時にカンニング。
 他の人の正答コードを使ってテストデータを用意しそのデータでコードをチェックしてから提出し合格。
 テストデータを自分で用意することも問題のうちとするなら明らかにカンニング。
 正答者の中では最も長いコードで提出。
 今回も他の人の短いコードを研究。
 賢いメモ化探索の方法があるらしい。
 
 
 
 16
 http://d.hatena.ne.jp/k_operafan/20101226/1293368885
 迷路を解く問題。
 2、3度ほど不正解を喰らってしまったので、他の人の正答コードを使ってテストデータを用意。
 テストデータをキチン通るまで修正してアセプト。
 直感と惰性だけで無意識のうちにコードを修正してたのでどこが悪かったのか良くわからない状態。
 半分無意識でコード打ってた。
 脱出口は一度に一人しか脱出できないという条件を多人数が一度に脱出できると勘違いしてたのが不正解の理由だったのかも?
-参考にした人のコードの詳細を読むのは今から。
+他の人のコードの詳細を読むのは今から。
+
+
+
+
+17
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0527
+碁石を一定のルールで並べてオセロのようにひっくり返す問題。
+最初何も考えず、碁石一つを配列の要素一つで表現する方法で玉砕。
+2度目は提出前にジャッジデータでテストしてから提出。
+記述ミスのポカミスを一つ訂正して合格。
+
+
+18
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0536
+ジャッジデータでテストしてから提出。
+場合分けのポカミスで意外と時間がかかったのと、再帰を使わなかったのでソースが無駄に膨らんだ。
+ソースコードの短さと実行速度でいつも回答者ランキング上位にいるPLDWさんはすごいなあと思う。
+機会があれば師事して教えてもらいたいがプログラマで子弟制度なんてないだろうし面識もないしなあ。
+
+
+19
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548
+この問題、正しい答えは出るのだけど、コードが遅いので時間切れで不正解になりました。
+高速化について延々悩んだのち、結局JOIのサイトにある考え方を見て100%カンニングして正答。
+まさかあんな簡単なことで答えが出るとは思わなかった。
+カンニングに使った答えの掲載されているページ。
+http://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t6/review/2010-yo-t6-review.html
+自分の提出したソースコード。
+他の正解者がメモリを大量に使ってる中、私一人メモリ使用量最低で正解。
+http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8B%89%E5%BC%B7%E6%97%A5%E8%A8%98&file=0548Reindeerwithnosenseofdirection0.txt
+
+
+20
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
+自力で解くのがめんどくさかったので
+http://blog.livedoor.jp/kenyoi/archives/3995712.htmlを参考に関数を少しだけ縮めてアセプト。
+
+
+21
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
+どうしても考え方がわからなかったので答えの考え方を書いたページを見て解きました。
+カンニングしましたが実装で工夫をしてコード実行速度1位(2011/11/24時点)を叩き出しました。
+http://www.ioi-jp.org/joi/2005/2006-ho-prob_and_sol/2006-ho-t5-review.html
+
+
+
+22
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0551
+つららが折れるまでの時間を計算する問題。
+コードに自信が持てなかったので公開されているジャッジデータでチェックしてから正答。
+
+
+23
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0550
+お菓子の棒を二人で分ける問題。
+不正回を食らったのでジャッジデータを検証してみたらジャッジデータに不備(いくつかのデータで問題と余分な関係ない入力が末尾に1つ)あることが判明。
+この余分なデータに対する対処を書いて2回でアセプト。
+
+
+
+*24
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553
+RPGを題材にしたダンジョンを下る問題。
+コードのHP上げ下げ分岐条件に自信が持てず公開されているジャッジデータを使ってテストしてからアセプト。
+ジャッジデータで2か所ポカミスを見つけてアセプト。
+
+
+
+
+*25
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0504
+カードゲームを題材にした問題。
+まだ解いてないがどうしても考え方がわからなかったので答えを読み、実装方法は分かったものの答えの考え方が分からなかったので考え方を掲示板で質問もした問題。
+
+
+*26
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537
+ビンゴを題材にした問題。
+まだ解いてない。
+答えの考え方を読むも効率的な実装方法まで到達できず手を出しかねている問題。
+
+
+*27
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1011
+炭素化合物で炭素の最大数を返す問題。
+英語の問題文を読解できず、掲示板で翻訳してもらい只今挑戦中。
+翻訳だけでいいのに、答えや考え方まで教えてもらい非常に親切にしていただいた問題。
+
+
+*28
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2105
+音楽ソフトを題材にした練習問題。
+どうしても解けないので公式からジャッジデータを頂いて挑戦。
+VC++.netとBCCで同じコードをコンパイルして実行するとVC++ではきちんと動くのにBCCではきちんと動かないという問題に直面。
+どうなってるのかよくわからない状態。
+
+
+
+*29 570 Zig-Zag Numbers
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570 
+ジグザグ数という数の個数を数えて返す問題。
+一発合格するつもりが答え出力時のprintfたった一行を間違えて書いていたのに気付かず2連続WAを食らう。
+ジャッジデータを使ってミスに気づきその一行だけ修正してクリア。
+すごくもったいない感じがした問題。
+
+
+
+*30 2401 Equation
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401 
+この問題は実装もアルゴリズムも1回目から間違ってなかったが採点データ読み込み部分だけを書き間違えて3連続タイムリミッドを食らった問題。
+採点用データを入手して解く。
+簡単な問題でアセプトの稼ぎ時だったのにもったいないことをしたと思う。
+以後ポカミス注意だな。
+
+
+
+*31 soj2002 X-Ray Screening System
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2002 
+この問題はどうしても解き方がわからなくて他人のコードを参考にしてしまった問題。 
+非常にシンプルな解法だったので自力で解けなかったのがかなり悔しかった思い出がある。 
+どんな順番で重なってるかの組み合わせを調べて、上手くいくのがあるかどうかを決めて調べていくだけでした。