■ [others]IPSC2012 
http://ipsc.ksp.sk/contests/ipsc2012/results/
uwiさんとkomiyaさんとのチームyaranaidakeで参加
経過
- 開始。おもい
- ひとまず自分が最初に問題文を開けたので最初から読む。Aはやるだけだったのでやる
- A1,A2 AC
- 次にBを読もう…と思ったら問題文も入力もなくて「何このエスパーゲー…？」と早速IPSCの洗礼を受ける
- とりあえず空ファイル提出だけやって次へ
- Cを読むとeasyは簡単なDPだったのでやる
- C1 AC
- そうこうしてたらF1がuwiさんによって解かれていた
- Jが、mp3を与えられてなんかやる問題らしい。uwiさんが絶対音感を発揮して一瞬で通した（ファーストアクセプト）。ぱない
- J1,J2 AC
- Dを読んでみたら超めんどい業務系データ処理ゲーだったので逃げてIを見てみる
- ハッシュ値から元の文字列を復元する問題みたいだけどそれ以上の見当が付かない
- エスパーゲーのBが結構解かれていたのでやってみる
- komiyaさんがMに取り組んでいて、行列式がどうこうという話をuwiさんとしている。ついて行けないので黙々Bを試行錯誤する
- とりあえず提出してみてエラーメッセージから条件を読み取る、というタイプの問題だった。ICFPC2010みたいな
- 初見のインパクトがいやらしいだけで、やってみればそんな難しくなかった
- B1,B2 AC
- 個人的にはeasyよりhardのほうが簡単だった
- komiyaさんがM1を手作業で解いて通していた。これもまたIPSCの醍醐味
- F2がまだ通ってなかったのでやる。嘘解法気味だったけど出すとあっさり通った
- F2 AC
- 次に問題文3ページもあってまだ誰もやってなかったKへ
- 読んでるうちに他のメンバーによってE1とG1が通される
- K最初わけがわからなかったけど、落ち着いて考えてみたら侵入先の部屋の鍵のことはガン無視してマスターキーを作ればいいだけだった。国語ゲーだ
- K1,K2 AC
- Kを通したと同時に、16分間計算し続けていたuwiさんのマシンがG2の答えを出したらしい
- 国内最強のRabbit Unagiチームを一時追い抜いて盛り上がる
- Iを考えたけどbrute-forceくらいしかやることが思いつかない…。最近ksnctfやってたのに
- そうこうしてたらuwiさんがD1を通す
- あとはkomiyaさんと一緒にC2を考えたりIでエンディアン変えてbrute-forceしてみたりしたけどだめだった
- ラスト100分で1点しか取れなかった…残念
結果
- 22点/39点中
- 37位/650チームくらい
感想
Iが解けなかったのがかなり痛い…。あとLに誰も手を付けなかったのはちょっともったいなかったかも。
赤コーダー×3でも37位とは世界は広いなあ。
Iは、みんなWeb上のツールでハッシュ値をクラックしようとしてたので、コンテスト終盤にはハッシュ値をググったら答えが出てくる状態になってたらしいw
やっぱりCTF系では「わからなかったらググれ」は基本だ
チームを組んでコンテスト参加するのは初めてでした。
協力しながら作業表を埋めていくのが面白かった。
しかし3人いても全部の問題に取り組むというのは相当うまくマネジメントしないと難しいですね…
■ [GCJ]Google Code Jam 2012 Round2 
- A
- 長くてわかりづらい問題文を耐えて読む
- それぞれのツタでどの高さのところをつかんだかを記録して、スタートから順に進めていく
- 遠いところから伝った方が下をつかめるので、「どの高さのところをつかんだか」が更新されることはない
- ので、しゃくとり法っぽくどのツタまでを使ったかを先に進めていくとO(N)でできるけど、N=1万だからそこまでやる必要もなくO(N^2)でやった
- 問題の解釈を間違えていてサンプルで引っかかった。よく読み直してクリア
- B
- マットの面積が円の面積の5倍以上とずいぶん広いので、てきとーにランダムに置けば大丈夫なんじゃないの？ と思う
- 一応、一番大きい円を決めうちで（0,0）に置いておく、というくらいの最適化はやった
- けどそれなりにコードが面倒になってしまったので、全部円の大きさ順でソートしてやった方がよかった
- ひとまずsmallをやってみる。しょうもないバグで2回ミスったけど通った
- largeはいけるかちゃんと検証してないので手元でいろいろテスト
- 大丈夫そうだったので提出
- C
- とりあえず、視線がクロスしているような場合にimpossibleになるというのはわかった
- あとはいまいちわかりそうでわからない
- smallはたかだか9!通りしか入力があり得ないので埋め込みできるかも、とか思う
- ひとまずランダムでやってみたら、最悪ケースと思われる（10,9,8,7,6,7,8,9,10）も数秒で終わった
- のでsmall提出してみたら通った
- D
- ひとまず簡略化のため、横にひとつながりになっている部分は左端に寄せて1マスとして扱う
- 左上から順に見ていって、「他のマスがだめなマスに落ちていかないような方法で、注目しているマスを下の列に落とせるか」を調べていくと、O(N^5)くらいでできるのではないか、と思った
- 実装してみたがややこしくて間に合わず
結果
5年目の参加で初のRound2通過!! （1622→893→845→712→125）
