れんしゅうちょう。

■ [ICPC]ICPC2014 アジア地区予選 東京大会 参加記 23:18

去年に引き続き, チーム Sophinyan として, ACM/ICPC アジア地区予選 東京大会に参加しました.

結果は, 7完最下位の, 9 位(チーム順位) でした. 順位表

チーム順位	大学順位	国内チーム順位	国内大学順位	解いた問題数	時間
9	8	6	5	7/11	1089

酷いバグに苦しんで, 時間さえあれば解ける問題に時間を残せなかったなど, 反省点はありますが, 健闘できたかなぁと思います.

僕は, 選手としての ICPC はこれで終わりです.

運営/手伝いをして下さった方々, スポンサーの方々, JAG の皆様, 応援して下さった皆様, それから(同じチーム, またはライバルとして)一緒に闘って下さった皆様, ありがとうございました.

以下, 詳細.

提出時刻付きの順位表とかが後悔されたら, 時刻を挿入する更新をする可能性があります.

みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!

*1

序盤以外は, 大体同時に二問を頭に入れるように努力していた.

1問を実装しつつ, もう1問の実装を考えるとか, 1問のバグ埋めてそうな所を思い出しつつ別のを書くとか.

いつものように時系列順(?)にイベントを列挙したやつ.

時系列順にしたかったけど, 割と記憶が危ういので, 色々違いそう.

少なくとも, 同じ問題内での思考順序みたいなのはあっている気がする.

始まる.

us 配列化と caps lock 潰しをし, .vimrc とテンプレを書く.

A(RLE)を聞きつつ, 自分でも読む.

入力形式が, 1回の実行で複数ケースあるいつものアレじゃなくて, 若干戸惑うも, ジャッジ環境が変わったからかぁと納得.

書く. 提出. AC.

B(+と*のやつ) を聞く.

一瞬真面目にパーザ書くのかと思いきや, スタックつかって頑張る系だった.

(左優先は逆ポーランドみたいな感じでやる. 掛け算優先は, 掛け算のみちゃんとやって, 足し算は無視して, あとで合計取る.)

書く. なぜか struct とか使って, ちゃんとトークナイズしながら入力を取っていて, 一瞬真面目に書こうとした跡がある. 提出. AC.

C(進んだり戻ったりするやつ) を聞く.

被ってる所は一個にして... 的な事を言われて, ぱっと証明といい方針が思いつかなかったので, (考えている暇はもったいないので)D(放物線)を聞く.

D の計算をお願いしつつ, 順位表で operasan が解いていた F(全域木) を読む.

Cを imos 法のようにやると簡単に解ける事に気づいたので, C を書く. 提出. AC.

D を大体実装する. 出力するものを知らなかったので, 聞くと, 速度らしい. 式をお願いしつつ F と平行して実装する.

D は, サンプル 2 だけ答えがあわず, とりあえず clar 投げながら, サンプル 2 の解析をお願いする.

Fを実装し, 投げるも, TLE. 計算量大丈夫なのにーと思いつつ定数倍高速化するも, TLE.

なぜか完全に O(nm * 小さいの) だと思っていたけど, これ O(m^2 * 小さいの) じゃん (完全にアホだった)(大絶望).

候補の辺を, 最初の全域木に使った n 本に制限すればいいだろうと思いつつ, 簡単な実装を考える.

D の 45 度というコーナーケースを教えてもらい, その時の値を計算してもらう.

F の(既に書いた UnionFind を使う)実装を思いつき, 書く. 提出. AC. (実はちょっと修正するだけでよかった気もする. この辺迷走していた.)

D も提出. AC.

E(車), G(括弧), H(ルンバ) も既に聞いていた気がする.

H は, かなりの量の写経しなければならないので, 手が開いた時や煮詰まった時に写経しつつ後回しにする事に.

G は, 解法は割とすぐ解り, 書く. 投げる. RE.

仕込んでいた, いくつかの自明な条件の assert で落ちているらしく, 探しても変な所は見つからない.

E を平行して実装しつつ, デバッグする.

G は, しょうがないので, どの assert で落ちているかを submit debug. 非常につらい.

二分探索の方法を変えてみたり, 色々やるも, やはりバグが取れない.

E は, 提出するも, 提出する物だか提出先だかを間違え, TLE と認識する.

状態を int にエンコードしたりしつつ, G のデバッグ.

E は encode したら何やらダメで, 提出先を間違えた事に気づき, 元の状態まで undo して提出したら, AC した.

G は, デバッグ出力と共に色々削って行ったら特定でき, クソみたいなバグで死んでいた.

update 時の, 見ている node の範囲がおかしくて, segtree の node を二倍用意したら AC した.

何が悪かったかというと, ライブラリのミスで,

void update(int l, int r, ll v, int k=0)

みたいなのを,

void update(int l, int r, ll v, int k=1)

と書いていた(死).

あとは, H をひたすら写経していた所で時間切れ.

解き方が解っているのに解けなかった問題があるのは悔しい.

しかし, 周りのチームも似たような状況だったようだし, 完全に解らなくなるのもまた悔しいだろうし, 7完できただけありがたいと思うべきかもしれない.

ツイートする