ACM/ICPC 2012 国内予選参加記
「な〜でこ〜だYO〜！」
ブログの更新がすごく久しぶりです〜.
昨日は, ACM/ICPCの国内予選に参加していました.
今年は, 競技プログラミングがすごく活発化していて, 昨年よりも他のチームのレベルがすごく高くなってくるだろうと予測していたので, 正直国内予選を通過できるか不安でしたが, 無事通過することができました.
これが, ぼくにとっても, チームメイトのslip0110先輩にとっても, 本当に 最後のICPC になるので, 通過することができて, 本当にうれしいです.
東京大会は, 敗退してしまった人たちの分も, 今まで以上にがんばって勉強して, 上位を狙います.
最低目標は, 表彰式でチーム名を呼んでもらうことです.
ではでは, 国内予選の参加記を書きたいと思います.
ACM/ICPC 2012 国内予選詳細
大会の概要としては, 以下のような感じでした.
- 日時：7月6日(金) 16:30〜19:30
- 場所：Web参加
- 問題数：7問 (Problem A~G)
- チーム：大学生・大学院生による3人チームで編成(詳細ルールは公式ページを参照)
- チーム名：THE 2DM@STER
- チームメンバ：@Respect2D(M1), @slip0110(M2), @_shnyh(B4)
結果
ぼくのチームの結果はこんな感じでした.
- チーム別順位：16位
- 選抜ルール適用時の順位：12位
- 大学別順位：9位
- 大学内順位：1位
- 解答数：4問 (A, B, C, D)
- ペナルティ： 3:39:18 (4 AC / 0 WA)
- A - 0:08:53
- B - 0:34:40
- C - 0:51:30
- D - 2:04:15
国内予選の目標とその達成度
＜目標＞
昨年の結果を見てると, 今年はかなり高めの目標をかかげておかなければ, 予選通過は難しいと思ったので, うちのチームは次の内どちらかを満たすことを目標にしていました.
- 『0WAで4完高速解答』
- 『ペナルティどれだけ食らってもいいけど、5完確実』
つまり, 大会途中でWAを1回食らいでもしたら, 4完コースを捨てて, 5問絶対通さないといけないという縛りをしました.
＜達成度＞
結果, 1つ目の目標を達成 することができ, 4完チームの中では最上位につくことができました. 4問目の実装に時間をかけすぎたため, あともう少しというところで, 時間が足りず 2つ目の目標は達成することができなかった です.
昨年のOBOG夏合宿の雰囲気を見てると, 合宿に招待されるかされないかのボーダーラインが5完辺りだったのもあり, 2つ目の目標を達成したかったのですが, 解けなくて残念です... 夏合宿呼んでもらえるとうれしいなぁ〜.
計画停電について
＜仕組まれた計画停電＞
「7月2日から, 関電が計画停電を始める」という情報が6月の下旬に告知されました.
今年は, この件のせいで, 大会直前にいろいろと振り回されて大変でした.
この計画停電のスケジュールが, ぼくたちの国内予選通過を阻むかのようなスケジュールだったのです.
どういうことかというと, 立命館大学BKCの計画停電が
- 「7月6日の16:30から18:30にかけて」
行われるスケジュールになっていたのです.
まさかの国内予選の開始時刻とだだかぶり.
＜会議室を借りることに＞
どうせ, 停電なんて起こらないからどうでもいいじゃないかという人もいるかもしれません.
しかし, ぼくたちは停電がもし起こってしまって, そのせいで予選通過できなくなったら, 一生後悔するだろうと考えて, 計画停電されない地域に逃げることにしました.
うちの後輩たちも一緒に逃げないといけなくて, 結構大きな部屋が必要だったため, 近くのホテルの会議室をかりて, そこに移動することにしました.
ホテルの部屋はこんな感じでした↓
＜当日はドタバタひやひや＞
当日は, slip先輩に車を出してもらって, 大学からホテルへ荷物を運ぶのに2往復, ホテルから大学へ荷物を戻すのに2往復してもらいました. 本当に助かりました. あとは, 朝からネットワーク設定とかいろいろやらないといけなくて, 結構ドタバタしました.
一番ひやひやしたのは, コンテスト開始20分前頃から, ネットがかなり重くなってしまったときです.
会議室には, うちのチームを合わせて8チームいて, それらのチームが同時にネットにつなげようとして, トラフィックが詰まっちゃったせいでした.
テザリングできるチームには, テザリングしてもらって, なんとかトラフィック量を減らして解決しました.
そんなことを開始5分前頃までやってて, まじで焦ってました.
＜停電なかった＞
と, 実はうちのチームには, コンテスト以外にそんなドタバタ劇がありました.
ちなみに, 結局計画停電はありませんでしたっ！orz
危機管理の勉強ができた良い機会だったと思います.
各問題について
では, 各問題についてどんな感じでやったかを簡単に書きたいと思います.
＜Problem A＞
＜Problem B＞
- 割振り
- アルゴリズム：slip, shnyh
- コーディング：slip(打ち), shnyh(ツッコミ)
- 解法
- 完全に任せてたので知らないです
- コメント
- slipさんが焦りやすいので, Bは2人で解いてもらうことにしてました
- かなりバグらしたみたいで, 35分程度でAC
- stringをsort(s.begin(), s.end())でソートできるのをチームメイトが知らなかったらしいです. 便利なので覚えておきましょう.
＜Problem C＞
＜Problem D＞
- 割振り
- アルゴリズム：ぼく, slip
- コーディング：ぼく(打ち), slip(ツッコミ)
- 解法
- ダイクストラ
- [現在いる場所][直前に乗ってきた路線の会社][同じ路線でどれだけの距離連続で進んだか]の状態
- ただし, 「同じ路線でどれだけの距離連続で進んだか」の情報に関しては, 値が大きくなって, このままのダイクストラでは解けなさそうです
- そこで, 入力制約に注目します. 料金変動の区間の切れ目の距離は, 10000以下で与えられると書いてあります
- つまり, 距離10000を越えたら, そこからの料金は単調増加することがわかります
- そのため, 「同じ路線でどれだけの距離連続で進んだか」の情報は, 10000以下であればそのまま進んだ距離を保存しておき, 10000を越えたら10001等に固定しておけばよくなります
- コメント
＜Problem E＞
- 割振り
- アルゴリズム：slip
- コーディング：ぼく(打ち), slip(ツッコミ)
- 解法
- 幾何がんばって, グラフを生成
- 任意の円と円の交点から, 他の円と円の交点へ向かって, 円の内部のみを通って線分を引けるなら, グラフのエッジに含ませる
- あと, 1つ目の円の中心から円と円の交点, 1つ目の円の中心からn個目の円の中心, 円と円の交点からn個目の円の中心, それぞれについてエッジを作る
- グラフはDAGになるので, DPかダイクストラをして最短距離を求める
- dp[今何番目の円と円の交点か] = スタートからの最小距離
- 幾何がんばって, グラフを生成
- コメント
- 明らかに4問目の実装スピードが遅くて, 5問目が間に合いませんでした
- 今年の幾何は, やるだけだっただけに通せなくて残念です
- 多分, あと10~20分あれば通せてたと思います
感想
毎年毎年, どんどん難易度上がりすぎなような気がしてますが, 気のせいですか？
難易度というか, 実装量が増えてるというべきか.
そして, それだけのセットでも, 4完・5完してるチームが多くて, 参加者のレベル高すぎてびっくりします.
これはもう, 「ニワカ(競技プログラマ以外)は相手にならんよっ！！」の領域に達していてやばい.
とりあえず, そんな激戦区の中で, 無事予選通過することができてよかったです.
次はアジア地区です.
そっちの目標は, はっきり決まったらブログにまた書ければと思っています.
目指せ世界です！
ではでは〜
