KUPC2011

オンサイトで参加してきました。
オンサイトでの参加はICPC以外では初めてだったので、いろいろな人と喋れてとても楽しかったです。
来年は学生を終えている(はずな)のでオンサイトでの参加は難しくなりそうで寂しいです・・・

開催者の方は本当にお疲れ様でした、そしてありがとうございました。

結果は４問解いて46位でした。
5問目があと少しで解けそうだったので残念・・・

対話型の問題という私にとっては未知の問題があり、とても新鮮な感じのコンテストでした。

A: KUPC

入力中の'K', 'U', 'P', 'C'の数の最小値を取るだけ

B: 蝉

最初は逆戻りしないというのを見逃していたのでダイクストラをしてしまった。
そこを見逃していなければ簡単なDPで済んだのでちょっともったいなかった。

C: しりとり

これも問題をちゃんと読んでいなかったので単純に相手のミス待ちを実装してしまった。
読み直すと相手は2文字の単語しか言わないということなので、'a'の文字でハメる作戦で通った。

D: 列の構成

普段のプロコン的な発想で、一意に解を求められるという発想で挑むも何も思い浮かばな…くはないがグラフに直して考えてもちょっとうまく行きそうにない。
他の問題も見たがこれが一番解けそうなので考える。
なんか直感的に適当にやってもあたりそうな気がするぞ・・・
という発想からランダムに数列を作ってみて帳尻をあわせるという(過去のプログラミングコンテスト経験的には)全く新しい発想を実装。
ヒューリスティック(誤差の２乗の和が小さくなるようにする)を使って実装するも一部でTLEを食らう。
これ頑張れば通るだろうと思い、また、これ絶対想定解法ちゃうわｗｗｗと思いながら必死で色々試す。
実時間で数十ミリ秒、解に辿り着かなかったら最初からやり直す。ヒューリスティック的に悪い方向へしか進まなかったら最初からやり直す。を実装したあたりでAC。
どうやらランダムが想定解法だったらしくあばばばば

E: Fox Number

きつねのしえる、ペロッこれはir5さんの味、と思いながら考える。
最初はFox Numberでない数を作り出す方針で行く。(手元で)TLE。
範囲内の数を全部実際に判定する方針で行く。(手元で)TLE。
素数系の問題は計算量を見積もりにくい・・・
最後にFox Numberで"なさそうな"数を作り出し、実際に判定する解を実装。
時間的には間に合いそうだがWA。
コーナーケースがうまく対応できていないことに気づいたところでタイムアップ。

F: ボール

ん？これ単純なDPちゃうか・・・？
でも解いてる人少ない・・・。→きっとなにかあると思い放置。
あとで聞いたところによると普通にDPらしい・・・orz

G: XOR回路

ランダムという発想がなかったので、２分探索していくことしか頭になかった。
しかし普通に２分探索してもうまくいかなさそうなので全くわからなかった。

その他

基本的にみんなが解いている問題を解いていく方針で挑んでいるので、他の問題はコンテスト中は読みもしませんでした。制作者の方すいません・・・
今回乱択という新たな可能性を示したとても面白い問題セットだったと思います。
新らしすぎて私は発想が及びませんでしたがね！