京都大学プログラミングコンテストに参加しました。
結果
ooooo------
解法とか
A - アルデンテ
いきなり複雑そうな数論っぽい問題だなぁーと思っていたけれど、
- 1≤N≤100
- 1≤T≤1,440
ということだったので、それぞれの砂時計の時間を何倍かして、範囲に収まるかどうか調べた。
B - 簡易オセロ
- 両端から黒→白→黒と取っていって、最後に残った色？→サンプルは通ったが、WA
- 分からないので他の問題を眺めてみたり
- 手でシミュレーションしてみる。
- コマの数が関係ないなら連続したのは簡略化していいよねー（例：oooxxxoox → oxox）
- 数を数えて、白の数≥黒の数 の時は白が勝つっぽい… → 書いて提出したら通った。
C - ソーシャル
boolの配列 usagi に、気分を害したうさぎがいたらチェックを入れていく方法で書いた。
仲の悪いうさぎの情報を取るときに、1-indexed ということに気づかず、2WA。これはひどい。
D - 権力
蟻本 p.47 の問題のような貪欲で解けます。
- 最初に"Impossible"かどうかを判定しておきます
- 入力例１の場合、2番目の 1-5 を守れる教授がいないと、1号室を守れないので、確定です。
- 5号室までは守れることが確定したので、次に採用するのは「始点が6号室以下の教授」の中で、終点が一番大きい教授です。3-7、2-5、4-8 の教授が該当しますが、一番大きい8号室まで守れる教授を採用します。
- これを最後の部屋がカバーできるまで繰り返します
pair<int, int> の配列で教授のデータを持っておいて、ソートすることで探索を撃ち切ることができます。（5号室までしか守れていない時には7号室〜 を守れる教授は要りません）
1WAを貰った原因は、5号室まで守れているときには6号室〜 を守れる先生でも良いのに、5号室〜 を守れる先生、としていたことでした。
E - じゃんけん
KUPCの醍醐味といった感じですね。
勝てる手が多い（≒強い）手を優先的に選べるようにルーレットしたり、完全乱択を試したりしてみましたが、なぜか1ケースだけWA
結果のページをいま見てみると、テストケースの名前が "00_teuchi_00" になっているので、
明らかに狙った、意地悪なケースがあったようですね
他の方の解法によると、「どの手にも勝てる完全無敵な手があるときにはそれを出し続ける」という方法で解けるそうですが、私は「あいこで地道に点数を稼ぐ」という方法でやってみました。
このじゃんけん大会では、
- 勝つと3点
- 引き分け1点
- 負けは0点
じゃんけんを1000回やって350点取ればよいので、約1/3回を引き分けにすれば勝利です。
というわけで、相手がたくさん出した手を優先的に選べるようなルーレットで出したところ、そのテストケースを抜けられた & 他のケースは乱択で勝利、ということで7WAの後AC
というわけで、以前よりは順位が上がってきたように思います。
今週末はICPC、私の学校からは始めての出場ということで、悔いのないように頑張りたいです。
