ACM/ICPC 2011 国内予選 参加記
ついに念願の国内予選突破です！
すごくうれしいです！＞＜
Respectid:shioshiotaさんな感じで参加記書きます.
| 順位 | チーム名 | メンバー | A | B | C | D | E〜G | 解答数(総ペナルティ) |
|---|---|---|---|---|---|---|---|---|
| 19 | R......2D | @Respect2D @kioa341 @slip0110 | 0:04:39 | 0:17:12 | 0:36:07 | 2:10:16 | - | 4 (3:08:14) |
開始1時間前
昼寝し始める.
開始40分前
昼寝から目覚める.
ちょっとすっきり.
開始30分前
A問題であせるといけないし, AOJの実装問題を解こう.
→WA出した...
→やばい. すごく不安.
開始1分前
F5連打ダダダダダダダ.
開始
Aを@Respect2D, Bを@kioa341, Cを@slip0110が読む.
A問題
Aが素数問題の超楽勝実装だったので, まじで喜びました.
@Respect2DがAを実装.
A AC
Aを解いた時点では, 全体で2位だったらしいです.
あとできいて, びっくりしました.
@Respect2Dは, C問題に移る.
B問題
@kioa341が担当. (この間に@Respect2Dは, @slip0110からCの問題概要を教えてもらう)
スタックで解く方針でやってたらしいです.
途中, つまづいたらしく, @slip0110が手助けしつつ, 実装.
B AC
@kioa341は, Dの読解に移る.
C問題
@Respect2Dと@slip0110が担当.
@Respect2Dが, 問題概要を@slip0110から教えてもらう.
@slip0110が, B問題の手助けに行ってる間に, 解法を@Respect2Dが考える.
再帰と幅優先で実装できそうな感じ.
@slip0110に横で見てもらいつつ, @Respect2Dが実装.
C AC
@Respect2Dと@slip0110は, 2人ともD問題に移る.
D問題
チーム3人で取り掛かる.
とりあえず, @kioa341から, 他の2人は問題概要を教えてもらう.
@slip0110は, 円の交差判定の関数を書く.
その間, @kioa341と@Respect2Dは解法を考える.
@kioa341「2^24のオーダは最低でもかかってくるよね」
このオーダ数に少しでも何かかけたら, オーダー数が明らかに間に合わないと考える.
@Respect2D「それだったら, 普通に再帰とか幅優先とかやったら無理じゃないの？何か他にいい方法ないの？」
ここがD問題の落とし穴だった...
1時間, あれこれいろいろなアルゴリズムをさまよっていきついた先は, 円の交差関係がDAGに落とせるっていうことだった.
@kioa341「一番上側から, どんどんペアを消していく処理を幅優先 or bitDPで書けばいいんじゃないか？」
はい, 絶対できないと思っていた幅優先に戻ってまいりました.
@Respect2D「え, でもそれって最初に言ってたけど, オーダー数的に大丈夫なの？」
@kioa341「考えてみればそんなに状態数多くならないような気がするんだよね. オーダー数とかじゃなくて」
@slip0110「とりあえず, 打ってみたら？」
↓
@kioa341が主に実装. @Respect2Dは, ビット演算のところとかは実装協力.
@slip0110は, 横で間違ってないか確認.
かけた！
Sample通す→通っちゃった.
Large通そう→まさかの通っちゃった.
出した→合っちゃった.
D AC
とりあえず, Congratulationを見た瞬間大はしゃぎでした.
それと同時に, 深読みしすぎたことに3人とも反省.
E〜G
Eは, 終了20分前頃に, 分割統治すれば解けそうだと思いつきましたが, 実装間に合わず.
Fは手を出すわけもなく.
Gは手を出すわけもな・・・え？
実は, Gに手を出していたんですね.
バカなことに.
しかも, D解き終わってから終了30分前頃まで, Eを見ずにずっとGを見ていたという馬鹿さ加減.
結局あきらめ.
素直にEを全力で解きにいってたら, 5問いけたかもしれないですね.
解法思いついてたので.
