Qualificationは突破したのでRound 1に参加したけど3833位なので残念ながらRound 1は突破できなかった。
解けた問題
2問目のOverrandomized だけすべてのテストセットを突破した。 ベンフォードの法則を偶然知っていたので解けた。
ベンフォードの法則を知ってると、極めて簡単な問題で、1文字目の出現頻度を全部計算して多い順に並べていく(1文字目以外には出現してるのに1文字目には1度も出現してないものは0にマッピングする)という感じで解けた。プログラムは以下の通り。
ベンフォードの法則は確率的な話ではあるが、10000テストケースあれば十分な個数である。もし運悪くWAが出た場合は8と9を入れ替えたりしつつ全部試していくみたいなことをすればよかったのだろう。
ベンフォードの法則についてはwikipediaでどうぞ
反省
Overrandomizedだけ解けた時点で、開始してから1時間15分、1298位でなんかこれはもしかして予選突破できるのではないかという色気が出て、あとは部分点を稼ごうみたいな思考になった。 C問題の最初のテストケースを見るとDが2か3ではないか！ということでif文を量産したけどなんかWAが取れずに死んだ。
最初からCを全部解くつもりのマインドで戦ったほうが高得点が取れたと思う、というか部分点狙いだけでは絶対に予選突破できなかった。1時間15分で、1298位で余裕がない(予選突破できるのは1500位)にも関わらず部分点で勝とうとしたことが今から思えば甘すぎる。
感想
運良くベンフォードの法則を知っていて得点につながったにも関わらず予選突破できなかった。また来年次のラウンドに進むためにはさらなる精進が必要であろう。頑張ろう。
