Waseda PCP Virtual Contest 2017/10/28 解説

このページは2017/10/28に開催されたWaseda PCP Virtual Contest for JOIの解説です。

問1 Change-おつり
'07-'08 予選1問目

一見めんどくさそうに見えますが、非常に簡単な問題です。おつりを500円から順に割っていくだけです。

問2 Christmas Party-クリスマスパーティ
'14-'15 予選2問目

もうすぐ来るけど、僕らは憂鬱になるだけの行事、クリスマス。
この問題は読解力があれば解けそう。ターゲットを配列に保存しておいて、足し算しましょう。気をつけて欲しいのは配列のインデックスについてです。配列は0から始まります。

問3 Card Game-カードゲーム
'07-'08 予選3問目

完全な実装ゲームです。3問目は例年めんどくさいですが、これもかなりめんどくさいです。割とここで詰まっている人が予想よりもずっと多かったので、驚きました。
解法ですが、特にアルゴリズムがあるわけでもなく、ゴリ押しです。僕はイテレータでごりごり押しました。

問4 JOI Flag-JOI旗
'10-'11 予選6問目

流石に難易度が鬼畜でした、これを作った人はきっと人間ではないのでしょう。さらにコンテストでやる場合、時間制限があるので最適化をかけないと通らないという鬼畜ぶり。本当にすみません。
まず、この問題は「良いJOI旗」を何通り数えられるかを考えるのではなく、「悪いJOI旗」を何通り数えられるのかを考えます。つまりは余事象です。しかし、これだけではオーダーに全く間に合いません。
さらに、直前のN個のますで"JO"が何処にあるか、さらに一つ前のますが'J'かどうか(次が'O'の時に"JO"であることがわかるため)をbitで保存します。
しかし、これだと、20 * 20 * 2^20 * 2個の配列が必要になって、MLEになってしまいます。そこで、直前のマスの情報のみ分かれば十分であることがわかるので、二つの情報を更新していけばいいことが分かります。なので、配列の数は2 * 2^20 * 2個ですみます。（それでも、僕の環境ではグローバル環境に宣言しないとエラーになりましたが）

正直言って、僕も初見で解くどころか、解説を見てやっと納得というところです。自分が解けない問題は人に出さないようにしましょう。本当にすみませんでした。

問5 Cheese-チーズ
'10-'11 予選5問目

結構昔に解いて、気に入ってた問題なので使いました。僕としては、4問目を飛ばして、5問目に取り組んで欲しかったです。
問題が少し複雑なので、日本語力が要求される気がしますが、冷静に読めば、要はSから番号順に工場を回っていけばいいことに気づきます。アルゴリズムは想定解法としてはBFS(幅優先探索)です。BFSを複数回できるか以外は基本なので、特に難しいことはありません。

問6 Foehn Phenomenon-フェーン現象
'16-'17 本選1問目

僕が本選で詰まってしまった問題です。実は、冷静に解けばすぐに解けるような問題になっています。
一つ前の標高との差を保存してしまえば、気温の増減は計算でき、地殻が変動しても変える値は二つで済むので、それを元に答えを計算します。しかし、観測する場所が地殻変動する場合は気温が変わらないことを気をつけましょう。
分かればとても解きやすい問題です。