tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Advent Calendar

はじめに: 言い訳
自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。

Advent Calendarには入門記事や高度な理論みたいなものをまとめたものが多くて実装の仕方みたいな記事が少ないように感じたので、失敗例として実践的なやらかしたコードをまとめます。なかなか古いソースコードが多いので、今とかなりコーディングスタイルが違うと思います。
注意:あまりにソースコードが長いものが多いので、ソースコードはideoneに貼ることにします。

1. グリッドグラフ上のBFS
int dx={1,0,-1,0};
int dy
={0,1,0,-1};
のような配列をつくり、遷移先をループで回し、内外判定すると簡単にグリッドグラフ上でBFSすることが出来ます。まあ4通りの遷移先しかないときは、別に4通り全部書いてもたいした実装量ではないのですが…
http://poj.org/problem?id=1198
ソースコード:http://ideone.com/FwkA7F
動く長さが増えたりすると遷移先が増えすぎて死にます。

2. 構文解析中の定数
whileで文字が数字でなくなるまで見るというのが妥当でしょうか。一桁や二桁なら別にそんなことをする必要はないと思いますが…
http://poj.org/problem?id=1114
ソースコード:http://ideone.com/fvlge4
さすがにif文が深すぎて実装が無駄すぎます。

3. 探索
探索は苦手ですが、さすがにこれは… 新年企画として解いたものです。
http://poj.org/problem?id=2012
ソースコード:http://ideone.com/qYbwKc
場合わけを分けてはいけない(戒め)

4.幾何
場合わけは極力避けるというのをちゃんと頭に入れておかないと、今でもこういうコードを書いてしまいます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1177
ソースコード:http://ideone.com/RS3mTT
これは場合わけゲーじゃないらしいです

5.ドラゴン
個人的に2011までのJOI合宿で最難問だと思っていますが、誰も信じてくれません。何度もコードを書くのに失敗しました。
http://joisc2011.contest.atcoder.jp/tasks/joisc2011_dragon
ソースコード0(本番中 WA)
ソースコード1(WA):http://ideone.com/cylr2l
ソースコード2(苦し紛れのAC?):http://ideone.com/2o5t4U
ソースコード3(AC):http://ideone.com/LyEW2H

あとでまだ公開したいものがあるので、あとで公開します。

おわりに: 言い訳
自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。自分の中では12/8の担当だと思っていました。