RUPC2011
ooox-o--- 4完 258pt 34位
問題をしっかり読みましょう。
A. Swap Cipher
解けた。
一通り問題を見た。順番に解いていこう。
文字をずらすだけっぽい。書く→サンプル合わない。あれ？
よくみたら復号って書いてある。。順番逆にすればいいと。書く→AC。
F. Farey Sequence
解けた。
順位表を見てみたら問題Fが結構解かれていたので、Dの前にFをやることにした。
なんかスターンブロコット木っぽい。でもちょっと違う。図を描くのが面倒だし、たしかspaghetti sourceさんのところにリンクがあったはず。→http://mathworld.wolfram.com/Stern-BrocotTree.html
なんかリンクが。。。「Farey Sequence」っていうのか！個数の一般項が載ってる。
φ関数を足し合わせるだけか。。。書く→TLE。
はいすいません。部分和とります。書く→AC。
D. The Legendary Sword
解けなかった(コンテスト終わってから解いた)。
Dに戻る。流し読み(←これが元凶)。これも経路探索っぽい。greedyに近くの宝珠をたどればいいかな？書く→サンプル合わない。ですよね。
サンプルのちょっと上の「触れるだけで破壊できるため」だけ目に入る。ってことは順番をとばすような宝珠には触れてはいけないのか。(←勘違い)
とりあえず各頂点から次の宝珠まで行けるかどうかをチェックしないといけないな。(←勘違い)
4 4 S 2 1 2 . . 2 G . . . . 1 . . .
とかが撃墜ケースかな。これは8にならないといけないね。(←勘違い)
書く→WAとTLEとMLEのラッシュ。
なぜだあああ→終了。
E,G,H,I
読んだだけ。
コンテスト終了後
診断人さんのニコ生見てたら勘違いしていることがわかったので、書き直す→WA。
んー、、ってスタートする頂点IDが0固定になってるしorz。書き直す→AC。orz
反省
日本語なのに、問題の解釈ミスとかひどい。。。
ちゃんと問題を理解することを面倒くさがらないこと。
あとDPの問題はちゃんと復習すること。
