ICPC World Finals 2013
コンテスト中の流れのメモ
- 開始直後、izさんがEclise、vim、キーボードを設定
- その後izさんが15分毎に時刻を表示するPerlスクリプトを記述
- 開始15分程度でJを読み終わり、三角形分割等のライブラリーを写せば行けると考え、izさんにライブラリの一部を写してもらうことに
- 開始35分で、全員合わせて全ての問題が読み終わったので、問題の読み合わせフェーズ開始
- 読み合わせの結果、Fが簡単そうだったので、解法をtodoさんと相談した後に実装(10分程度)→Accepted(0:57)
- 読み合わせの結果、よく分からない問題があったので、その問題をizさんに読んでもらうことに
- Cの解法を最小費用流と誤解していたが、todoさんと相談して、違うことが分かったので再考し、最大流でTLEせずに解くことが出来るということに気づいたので再度相談し、実装。謎のTLEを受け、Dinicを書くもののやっぱりTLE。todoさんに見せたところ一瞬で記述ミスに気づいたので急いで修正してAceepted(2:04)
- todoさんがAが書けるということで一応解法を聞く。大丈夫そうだったので、実装開始
- todoさんがAを実装している間に、D、Hを考える。Hは解法をかなり詳しく詰める。Dはひらめいたけど、そこまで詰められず。
- AがAcceptされたあと(2:38)、Hの実装を始める。
- サンプルの順番が問題文と違うという罠に嵌ったものの30分程度で完了し、Accepted(3:08)
- Dを試しに実装してみると、時間的に間に合いそうなので、きちんと実装する。
- 提出してもWA。デバッグ出力を消し、コーナーケースを潰してもWA。結局、条件の記述ミスがあったので、修正してAccepted(3:50)
- そのままJの実装開始。実装している間にtodoさんとizさんが三角形と円の共通部分の面積を考えだしていてくれたので、合流して最後まで実装。WA。誤差条件やらassertを加えたりしてみてもやっぱりWA。
- 最終的に幾何ライブラリ部分(わたしが写した部分)に一箇所ミスがあったので修正してAccepted(3:44)
- izさんがBの式を出していてくれていたので、todoさんがいろいろ弄っていたが間に合わずにコンテスト終了
最初が遅いのは想定通りだけど、D、Jで時間とられているのはまずいなあ…。逆にWAで嵌ってしまっていてもしっかりリカバリー出来ているのは良かったです。
ACM-ICPC アジア地区予選2012 参加記録
ICPCアジア地区予選に参加しました．
チーム編成
チーム名：UselessUltimate & Escapist Coders
メンバー：@todo314(todo), @k_operafan(k_operafan), @izuru_matsuura(iz)
結果
8問正解，ペナルティ1007で3位でした．
戦略
- PCを占有する時間が出来るだけ短くなるように，紙コーディングや紙デバッグを出来るだけ活用する．
- 開始1時間・2時間・3時間・4時間後にチーム全員で問題の内容や解法の案についての共有を行う．実装出来そうな場合，実装時間についてもある程度見積る．
- 最初はAをiz，Bをtodo，Cをnomeaningが読む．
各問題について
自分が通した問題についてだけ書きます．全体の流れはhttp://d.hatena.ne.jp/todo314/20121121/1353495586を参照
C問題
ちょっと読んでみたら繰り返し二乗法をやる感じで解けそうだったので，とりあえず書いてみたら通った．
D問題
間違っている点を仮定して連立方程式を解く解法で解いた．
ところが"ループの終了条件ミス"で2WA，EPSの設定ミスで1WAしてしまった．
このバグに気付くのに結構タイムロスをしてしまった．
E問題
izさんとペアプロ．
dijkstra+BFSで書いたものの，謎のSegmentation Faultに悩まされる．
30分近く悩んだのだが，"ループの終了条件"を間違えていて，vectorの範囲外にアクセスしたのが原因だった．
G問題
izさんがライブラリを写してから交代して実装．
点と直線の距離はライブラリにあったので，余弦定理を活用して点と線分の距離を求めた．
結構細かいミスがたくさんあり，サンプルが通らなかったが，１つ１つ修正していき，サンプうを合わせた．
正しそうだったので提出してみたらTLEした．
計算量を考えると大丈夫そうだったので，適当な枝刈り(解が小さくなる場合)をすることでAcceptedされた．
本番終了後に分かったのだが，TLEの原因はsetを使ったことであったらしい．
I問題
todoさんが解法を大体考えていたが，境界条件とかが煮詰まっていなかったので，一緒に条件を整理した．条件整理後は結構すんなり書くことが出来て，結構すんなり通すことが出来た．
ACM ICPC2012 アジア地区予選
@hiyakashi_さんに「ICPCって1日目と3日目は何してるの」と聞かれたので，コンテストの参加記録とは別にそこらへんについて箇条書き形式で適当に書きます．
一日目
- お昼御飯にうどんをたべた
- 参宮橋駅でしめじたんさんとしおしおたさんと合流．LiveArchiveについて語りながらオリンピックセンターに向かった．
- 参加登録をして，コンテスト会場へと移動した．
- Tシャツが青と好きな色だったので一人喜んだ．
- 座席は隣が"icp.py"で，前が"morumotto reloaded"で結構やばい感じだった．
- コンテストについての説明を受けて，Praction Sessionに．
- PCにログインしてみると素のGNOME3だったので，とりあえず強制FallbackをONにした．
- 日本語キーボードを使っているのに英字キーボードの設定になっていたので適当に直した．
- PC^2を起動してみたが，何故か何も表示されない．何個か起動して，置いてあるディスプレイではなくノートPCのディスプレイに写っていることが分かった．
- どうやら今回はデュアルディスプレイを使えるらしいが，全くの想定外だったのでizさんとtodoさんと相談して，サブディスプレイをどのように使うかを決めた．とりあえずデバッグ用にコードを写すのと順位表を写すのに使うことに決めた．
- Practice問題を開いて，問題を解いてみることに．とりあえずizさんがAでWA，TLE，ACを出していた．その後todoさんがBでWAとACを，わたしがCで同じくWAとACを確認した．
- izさんがAをコンパイルした瞬間，サブミットしていないのに風船が二つ来てビックリした→あちらのミスでした
- Practice Sessionが終わり，JavaChallengeに．
- todoさんがコーディングをし，izさんとわたしがアルゴリズムを考える作戦に．
- とりあえず距離を求める関数が必要な気がしたのでちょっと考える→実はAPIにありました．
- 初期位置は分散させるか，密集させるか悩んだものの，各個撃破されたら不味いということで出来るだけ相手から遠い所で密集させることに．
- izさん「こういうゲームでは単純なプログラムが強い」ということで，とりあえずとにかく最も近い点に攻撃するだけな作戦を考案．実行してみたら意外に強くてビックリ．
- お金と資材の活用方法についてizさんと話し合う．鉱脈のレベル上げをしてしまうと複雑になりそうだったので，とりあえずロボット生産のレベルを1->2にするだけで，Stoneは全部売り払う戦略に．
- ロボット生産のレベル上げの場所は速度が重要ということで，戦線に最も近い所からレベルを上げる戦略に．
- ゲームを何度か実行してみると序盤負けが多かったので，既に占領されている鉱脈のうち弱そうな所を集中攻撃するアルゴリズムに変更．
- 結果，序盤で弱いチームを潰すようになって勝率が結構良くなる．
- ここまで実装した時点で残り時間がほとんど無くなってしまっていて，このまま提出することに．
- Java Challenge終了後，一旦部屋に荷物をあずけてから，歓迎会の会場へと移動した．
- チーム紹介，University of Agitsuneのがフリーダムな感じでとても面白かった．~shiokawaのは0と1だけで記述されていてビックリした．
- natriumさんから高専プロコンで用いたらしいサイコロを頂いた．
- 雑談していたらいつのまにか終了時間になっていて，一日目終了.
二日目
- コンテスト会場に移動．
- コンテスト終了後，問題解説や表彰式を行う会場へ移動．
- 軽食(？)が用意されていたので他のチームの人と問題について雑談しつつ食べた．
- 問題解説は解いている人が少ない順だった．確か，J,H,E,I,G…という感じな順番だった気がする．
- 解説はAをO(1)で解いていて凄かった．
- 続けてJava Challengeの結果発表が行なわれた．
- UECodersは残念ながら8位だった．個人的にはもう少し行けるかなあという感じだったのでちょっと悔しかった．
- (もう少し試行回数を増やした方が良かった気がする)
- その後コンテストの結果発表があった．
- UECodersは3位で，メダルとパズルゲームと数学パズルの本を頂いた．
- コンテストでメダル貰うのは初めてだったし，とても嬉しかった．
- 懇談会．
- 軽食ととりつついろいろな人と会話．楽しかった．
- JavaChallengeオープン参加の結果発表があった．hasiさんが全体で優勝しててぱなかった．
- 女帝さん怖い
- 懇談会終了後の懇談会(SAKE CHALLENGE)
- (省略)
- オリンピックセンターに戻ったあと，やばい人達がぷよぷよしてるのを観戦したりした．
三日目
- 三日目はエクスカーション(日本チームは企業見学)でした．
- わたしは，サイバーエージェントとGoogleとDeNAを見学するルートでした．
- サイバーエージェント様では会社の説明を受けてから，オフィスを見学させていただいた．
- 仕事をする環境としてはかなり良さそうな感じであった．2
- お昼御飯はGoogle様の食堂で頂いた．
- Google様はICPCのOB・OGが異常に多くてビックリした．
- DeNA様では会社の概要の説明を受けてから，エンジニアとの少人数での話し合いがあった．
- エンジニアとして働いている人とかなり近い所で話すことが出来て，とても良い経験となった．
ICPC 国内予選 2012 参加記録
ICPC国内予選に参加しました。
チーム編成
チーム名：UselessUltimate & Escapist Coders
メンバー：@todo314(todo), @k_operafan(k_operafan), @izuru_matsuura(iz)
結果
| 問題数 | ペナルティ | A問題 | B問題 | C問題 | D問題 | E問題 | F問題 | G問題 |
| 5 | 18197 | 17:25 | 23:53(+1) | 1:16:14 | 58:36 | 1:47:09 | - | - |
全体で6位なのでアジア地区大会に進めそうです！
戦略
とりあえずA〜Dまではtodoとk_operafanが交代で通す。その後は臨機応変に解ける問題を探していく。
回答の提出時には必ずizが正しいファイルかどうかのチェックを行う。
各問題について
A問題
実装：todo
解法：todo
いつのまにか終わっていました。
B問題
実装：k_operafan
解法：k_operafan
デバッグ：iz
問題文の読み違いで1WA出してしまいました。
A問題をtodoさんに書いてもらっている間に、izさんとデバッグし、A問題を通したあとに、通しました。
C問題
実装：todo
解法：todo
実装が重そうな問題でしたが、todoさんが12分で書き終えました。
D問題
実装：k_operafan, iz (ペアプロ)
解法：k_operafan
ワーシャルフロイドを使って路線ごとの最短距離を計算してからダイクストラを使って解きました。
乗り換えの部分のグラフの構築ミス(無向グラフのはずが有向グラフになってた)にちょっと嵌ってしまいました。
E問題
実装：iz→k_operafan(途中交代)
解法：k_operafan, todo
幾何+ダイクストラの問題。
グラフの構築前までizさんにやってもらい、グラフの構築をわたしが実装しました。
F問題
実装：k_operafan, todo(ペアプロ)
解法：todo, k_operafan
DPを終了40分前に閃いたのですが、実装中に+1しわすれるというケアレスミスをして嵌ってしまい、時間内に実装しきることが出来ませんでした。
悔しいです。
G問題
解法を3人で話しあったのですが、難しそうだったので、F問題に集中することに決めました。
感想
- やっぱりチーム戦は楽しいです！
- B,Dで若干バグに嵌ったため、バグを作らずに実装する練習をもっとした方が良さそうだと思いました。
