「アルゴリズム勉強日記」の編集履歴（バックアップ）一覧に戻る
アルゴリズム勉強日記 - (2011/05/29 (日) 09:46:01) のソース
http://rose.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja
リンク先は会津大学オンラインジャッジというプログラマ向け問題集を扱ったサイトです。
私はこのサイトでsinapusu2002という名前で登録しプログラムの問題集を解いてます。
私の成績
http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.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
迷路を解く問題。
２、３度ほど不正解を喰らってしまったので、他の人の正答コードを使ってテストデータを用意。
テストデータをキチン通るまで修正してアセプト。
直感と惰性だけで無意識のうちにコードを修正してたのでどこが悪かったのか良くわからない状態。
半分無意識でコード打ってた。
脱出口は一度に一人しか脱出できないという条件を多人数が一度に脱出できると勘違いしてたのが不正解の理由だったのかも？
他の人のコードの詳細を読むのは今から。
