チーム Sophinyan として, ACM/ICPC アジア地区予選 会津大会に参加.
5完最下位の, 17位(チーム順位). 順位表
| チーム順位 | 大学順位 | 国内チーム順位 | 国内大学順位 | 解いた問題数 | 時間 |
|---|---|---|---|---|---|
| 17 | 11 | 13 | 7 | 5/10 | 703 |
割と色んな人と喋れて, 楽しかった.
結果的には, 反省点はいくらでもあるけど, 当初の目標(去年のように Honorable Menthion にならず, 順位が欲しい)は達成出来て, 良かったと思う.
来年はもう少し上を目指したい.
例に依って参加記というよりただイベントを時系列順に並べた何かだが, とりあえず, 競技に関係する所だけ書こうと思う.
初日は, バスが遅れて辛みを感じ, CapsLock潰しが出来なくて辛みを感じ, JavaChallengeはそもそも動かし方すら解らず辛みを感じた.
結局JavaChallengeは幅探すらバグってrandで出したけど, 提出ミスってたっぽく不参加に. CapsLock潰しは他チームの方に教えていただいた.
色々すっ飛ばして本番.
CapsLock潰しと.vimrcをちょっと手間取りつつ書いて, A問題を読み始める.
のdfsだなぁという感じだが,
なら一瞬で書けると思って, それがどれくらいの大きさか解らず, まぁとりあえず書いてみた.
実は10の12乗とか超えてる感じらしく, まぁサンプル余裕で通らないので, を書く事に.
ライブラリでnビットのうちkビットだけ立ったやつを列挙するループを持ってきてたのを思い出して, それ使って書く→AC(13分).
この辺でB, C問題後輩が読んでいてくれて, それを聞く.
Bはまぁシミュレーション一択だなぁと思いつつ書く. ちょっとクソみたいなバグ(次使う用の配列を読んで弄ってた)出したけどAC(38分).
C問題は, ちょっと手でサンプルみつつ確認.
座標に比べて圧倒的に四角形の数が少ないので, まぁ座圧してやる.
なんかこれもクソみたいなバグ(floodfillで隣接が同じ色か確認せずに塗って再帰)出したけどAC(103分)
確かデバッグしながらD問題とE問題を把握したような気がする.
E問題はまぁひと目でダイクストラ余裕でしたという感じなので, 書く.
サンプルの3つ目でくっそ時間かかって, つらみを感じる.
しょうがないので, Hを解く. こっちもサンプルあわずに辛い.
なんかこの辺でJ以外の全ての問題をデバッグ中に把握して, 各問題の評価をしていた.
D: 算数だけど式立てるのヤバそう. 実数にして分数探索する手もあるけどどっちにしろつらい.
E: ダイクストラやるだけで計算量も余裕そうなのになんで遅いのか全くわからなくて辛い.
F: 最近点対みたいな感じなのは解るけど, そもそも最近点対書いた事無いし, 後回しだなぁ.
G: なんかずらしながらsegtreeをアップデートしてく系のDP高速化テクっぽい感. 家でゆっくり時間がある時にやるならいいけどこの状況で解ける気はあんまりしない.
H: よくある点列挙して各点で判定するだけの幾何なのにつらみ. サンプルで死んでるのでまだマシ.
I: なんかDPっぽいけど, じっくり腰を据えてやんないとちゃんと見えなさげ.
J: ひと目で正規表現クロスワードだけど, ある程度解かれるまで読む価値無し.
なんか, 結果的に大体評価はあっていた気がする.
とりあえず, Eの高速化と, Hのデバッグを思いついた事から並列でやった.
下の二つは, 折り重なるようにやっていて, AC時間が9分しか違わなくて, 点数もったいない感がすごい.
Eは, ダイクストラが間違っていないかを何度か見てみるけど, 何度見ても正しい.
とりあえずA^*にしてみるも, 全然速さ変わらん.
Eはstringで持って, 辺を一々作ってるのが遅いのかと思い, 前計算で各頂点をintにエンコードして, グラフを配列で陽に持つ.
それでもクソ遅くてダメげ.
途中で出力してみると, どうやらサンプル出力の半分程度のコストのところまではなんとか行ってて, 双方向ダイクストラにすればよいと思い, 本で終了条件カンニングしつつ書く.
サンプルもなんとか出力出たので投げる→AC(230分).
ちなみに, 原因はおそらく GLIBCXX_DEBUG フラグ. 死にたい.
Hは, サンプルを見ると, 候補の交点が一つも無いパターンで死んでるっぽい.
適当に候補の点を, 適切な線分のn等分点とかで追加してみて, TLEとWAを数回出す.
(候補の交点の入れ方的に)交点なけりゃOKという事に気づき, それで提出→WA.
EをACしてから, 順位表を見つつ, Hのバグ取りに性を出すべきか, Dを頑張って倒すべきか迷って, 迷いながら最後に100-2*hogeくらいの矩形に入ってるか判定する所でEPS噛ましてない事に気づき, 修正→AC(239分).
デバッグ中に後輩にDの立式をお願いしてたり, 少しづつ書いたりした気がするけど, あんまりうまいこと行かない.
自分でも立式しようとしていて, 色々方針を転換していてヤバかった.
結局終了間際にサンプルが結構あってるヤツが出来たけど, 重なるパターンとかで明らかに死んでいてアレだった. 辛い.
良かった点:
1. 問題を殆ど読まなくてよかった事.
チームメイトがかなり読んでくれた上に誤読も無く, 僕がちゃんと読んだのはAだけで済んだ.
2. 解けない問題, 諦める問題の選定が割と的確に早く出来た事.
解けない問題を延々と考えて時間を使ったりする余裕は無いので, 最後以外ほぼフルに｢結果的に点数に寄与した問題｣に時間と頭を使えたのは, 非常に良かった.
良くなかった点:
1. EとHを交互にやっていて, 両方ACが遅くなってしまった事.
思いついた順にやったので仕方ない所はあるが, (点数的な意味での)時間が非常にもったいなかった.
2. Hを適当に投げすぎた事.
EPSでのWAはまぁ仕方ないと思えるが, 他のは適当すぎた.
ちゃんと考えれば解ったことなのに, てきとーに解決しようとするのは非常に良くない.
3. operator書くのサボった事.
D問題, 式がごちゃごちゃするのは明らかだったので, ちゃんと分数クラスにoperatorぶち込んで, ヤバい感じの sub(div(add(a,Q(60,1),... みたいなのを書かないで済むようにするべきだった.
4. 方針を色々思いつかなかった事.
Aは全探索でも普通に間に合うので, 普通にもっと簡単に書けるのに気づかなかった.
Cの多面体定理とかも(選ばなくても)思いつくべき方針の一つだった.
来年に向けて, 精進したい.
追記(@ 12/15 23:15)
来年は皆さん TwitterID/Icon 入りの名札下げてきて下さいお願いします.