第9回日本情報オリンピック予選 エア参加記
はじめに
運営側のトラブルのせいで、予選開始後数時間はろくに問題ページにアクセスできませんでした。
入力ファイル計30個を全部ダウンロードすることが事実上不可能だったため、問題文ページにアクセスすることを最優先。
問題１〜問題６の問題文ページにそれぞれアクセスを試みていたところ、最初に開けたのが問題６だったため、やむなく最難問題から解き始める羽目に。そのまましばらく他の問題文に1問たりともアクセスできなかったため、一番最初に解き終わった問題が最難問題という珍しい体験ができました。この数年間で初めての経験です。
問題１ レシート
10冊の本の総額と、そのうち9冊の本の値段がそれぞれ与えられるので、残り1冊の本の値段を答えなさい。
n軒の書店を巡って本を買ったものの、うち1つの店Xでレシートをもらい忘れたため、財布の減少額と所持しているレシート群から店Xで使った金額を求めよう……ってシチュエーションは現実でもしばしばあるよね。
やるだけ。組むだけなら1分かかるかかからないかです。
問題２ すごろく
「○マス進む」と「○マス戻る」の特殊マスがある1次元すごろくのマップと、i回目にサイコロを振ったときに出る目が与えられるので、何ターンでゴールできるかを答えなさい。
この問題文には図がついているのですが、例のトラブルのせいで図が表示されません。一応、テキストだけで十分な情報を得ることができたのが不幸中の幸いでした。
やるだけ。この辺までは、本来ならば組む時間よりもその他もろもろに要する時間の方が長いと思われます。
問題３ パーティー
あなたの友達、およびあなたの友達の友達をパーティーに招待する。n人の集団の友達関係が与えられるので、パーティーに招待するべき人数を答えなさい。
＜ためしに隣人部のメンバーで実験してみた＞
・あなた → 友達 → 友達の友達
・小鷹 → 夜空、星奈、幸村、理科、マリア → φ 結果5人
・夜空 → 小鷹 → 星奈、幸村、理科、マリア 結果5人
・星奈 → 小鷹 → 夜空、幸村、理科、マリア 結果5人
・幸村 → 小鷹 → 夜空、星奈、理科、マリア 結果5人
・理科 → 小鷹 → 夜空、星奈、幸村、マリア 結果5人
・マリア → 小鷹 → 夜空、星奈、幸村、理科 結果5人
予選なので、n≦500でも構わずワーシャルフロイドできるのはいいね。しょせん友達の友達までなのでそんなに楽できるわけでもないですが。
問題４ カード並べ
2桁以下の正整数がn個（n≦10）与えられる。その中からk個（2≦k≦4）の数を選んで、文字列として好きな順番で結合させる。このとき、結果として得られる文字列は何通り考えられるか答えなさい。
nCkだろうとnPkだろうと似たようにすっきり書けるpermutation系関数はあまりに偉大です。
問題５ 通勤経路
100×100以下のサイズの碁盤目状の都市が与えられる。都市の左下から右上まで最短経路で通勤したいとき、通勤ルートは全部で何通りあるか、100000で割った余りを答えなさい。ただし、一度曲がると直後の交差点では曲がれないものとする。
日本情報オリンピック定番、碁盤目の街を右か上に歩いてゴールを目指すDP問題です。
この問題文には図がついているのですが、例のトラブルのせいで（後略
問題６ 方向音痴のトナカイ
10×10以下のサイズの町のマップが与えられる。町の各マスは「家」「教会」「空き地」のいずれかである。サンタクロースが教会から出発し、飛車の動きを繰り返してすべての家をちょうど1回ずつ訪問して、最後に教会に戻る。空き地マスに止まることはできず、まだ訪問していない家が残っている段階で教会に止まることはできない。また、一度訪問した家の上を通過することもできない。このとき、家を訪問して教会へと戻る道順は何通りあるか答えなさい。ただし、町に教会は1つ、町は23箇所以下しか存在せず、答えるべき経路は2000000通りを超えないものとする。
最初に解いた最難問です。例年の最終問題よりは遥かに易しいような気がします。
普通に考えれば全状態(24)×(2^23)を持ちつつDPですが、なんかただの再帰全探査で間に合いそうな気がしたので手抜き探索を組みました。
結果、20分ほどで入力5データをすべて処理完了。ちょっと見積もりを間違えると死亡するので、良い子は真似しないでねを推奨します。
情オリには同点なら早く提出した方が強いとか無いので、いろいろと気が楽です。
