第8回 2008年度情報オリンピック 本選
予選突破ボーダーが60〜70点、本選突破ボーダーが2完プラスマイナス部分点と、ようやく数学オリンピックと同程度のボーダーに落ち着いてきたか、と思っていた矢先に、なぜか易化しました。
いや、まあ数オリと同程度に落ち着ける必要は別にないんですけれどもね。
以下、適当なつてから入手した、各問題に対する所感とか。
問題１
I I O I O O I I O I O I …… I I O I O と、IとOが等確率でn個並んでいる文字列があります。
この文字列中に現われる「I O I」の数の期待値はいくつでしょう。
という有名(?)問題がありますね。
……何の関係もないけど。
一般の文字列に対しても適用できるアルゴリズムで解いた頭の悪い人もいたかもしれません。
問題２
店舗と宅配先の座標を全部ひっくるめて、ソートする。
端から順に見ていき、注文先があったら、その前後にある最も近い店舗を探して、距離を出す。
これを繰り返して、答えを出す。
という手抜き解法でも間に合うように、制限時間が2秒に設定されているのでしょうか。10000の2乗。
問題３
Ｊ君が赤ペンに持ち替えてアミダを辿り始めようとする直前、横から手を伸ばして横棒を一本削除する問題。
ちなみに自分は、下から辿っていく（ように組む）派です。
問題４
格子状のマス目の辺を辿って、(1,1)から(5,4)まで最短距離で到達する方法は何通りあるでしょう？
てな具合の問題は誰しも1度は解いたことがあるはずです。
つまり、現行の算数のカリキュラムの内容には動的計画法のエッセンスが含まれているということに他ならないのです。
算数すげぇ。
問題５
情オリらしからぬ、教科書的な強実装問題（半分くらい偏見）。
これだったら、予選の6番の方が難しかったのではないでしょうか。
ボーダー予想
解いていた時間よりも解き終わって暇してた時間の方が長かったであろうあの人とかあの人とか、確実に5完しているであろう面々は世界行ってらっしゃいとして、残る10枠ちょいを普通人が争うことを考えます。
全体的に、比較的2006年度のセットに近い難易度であることと、参加者全体のレベルが上がっていることを考慮に入れると、54点/100点くらいかなぁ、ボーダー。
