読者です 読者をやめる 読者になる 読者になる

KUPC 2012

京都大学プログラミングコンテストに参加しました。

結果

ooooo------

解法とか

A - アルデンテ

いきなり複雑そうな数論っぽい問題だなぁーと思っていたけれど、

  • 1≤N≤100
  • 1≤T≤1,440

ということだったので、それぞれの砂時計の時間を何倍かして、範囲に収まるかどうか調べた。

B - 簡易オセロ
  • 両端から黒→白→黒と取っていって、最後に残った色?→サンプルは通ったが、WA
  • 分からないので他の問題を眺めてみたり
  • 手でシミュレーションしてみる。
  1. コマの数が関係ないなら連続したのは簡略化していいよねー(例:oooxxxoox → oxox)
  2. 数を数えて、白の数≥黒の数 の時は白が勝つっぽい… → 書いて提出したら通った。
C - ソーシャル

boolの配列 usagi に、気分を害したうさぎがいたらチェックを入れていく方法で書いた。
仲の悪いうさぎの情報を取るときに、1-indexed ということに気づかず、2WA。これはひどい

D - 権力

蟻本 p.47 の問題のような貪欲で解けます。

  • 最初に"Impossible"かどうかを判定しておきます
  • 入力例1の場合、2番目の 1-5 を守れる教授がいないと、1号室を守れないので、確定です。
  • 5号室までは守れることが確定したので、次に採用するのは「始点が6号室以下の教授」の中で、終点が一番大きい教授です。3-7、2-5、4-8 の教授が該当しますが、一番大きい8号室まで守れる教授を採用します。
  • これを最後の部屋がカバーできるまで繰り返します
  1. はじめにRubyで書いていたら、TLEするというワロスな状況になり
  2. C++で書きなおして提出したら、TLE + 1ケースだけWA

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、私の学校からは始めての出場ということで、悔いのないように頑張りたいです。