ACM-ICPC 2018 Asia Yokohama Regional 参加記
はじめに
2018年12月8, 9日に横浜で行われた ACM-ICPC 2018 Asia Yokohama Regional の参加記です。
プラクティス～懇親会あたりまでの話を大雑把にまとめようと思います。
チームについて
自分はチーム Zerokan_Sunshine として kazuma, nakano と一緒に出ました。
基本的に担当は
- suibaka (自分) : 実装担当、自明とか典型とか幾何とか。あと問題読解。
- kazuma : 実装担当2。データ構造が得意（ICPCではあまり出ないので悲しい）
- nakano : 考察・問題読解担当、コードは書かない（早く US 配列に慣れろ）
となっています。
プラクティス
プラクティスは基本的に1問ACしてあとはジャッジで遊ぶだけなんですが、今年は問題が普通に過去問だったので真面目にやりました。
A 問題
kazuma が Link-cut tree で解けるとか言い出したので後回しにした（流石にネタ）
n 要素の数列が与えられるから合計値出力するだけ。
B 問題
覚えてないが全探索、kazuma に書かせた
C 問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320
知っているので油断していたらコーナーケースを忘れて 1WA 。
知っていると思考が無になる。
D 問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1605&lang=jp
これも解いたことがあるが今思えば条件判定部分を間違えていた。
間に合わなかった。
プラクティス後
雑にチーム紹介をして終わり。今年はご飯の提供がなかった。
まあ近くに中華街があるのでそっちで食べられた。
ただ寝不足が続いていてコンディションが悪い人が多く、ちょっと食べてさっさと寝た…んだったら良かったんだけどなー。
ABC
なんかABCがあった。後述の Snackdown まで仮眠をとるつもりが何故か眠れず、出ることにした。
さっさと終わらせて寝るつもりだったけど、冷えたので布団で暴れたり呪詛の言葉を吐いたりした。
Snackdown 2019
運の悪いことに今年は Snackdown の最終予選が 23:00 ～ 04:00 とかいうヤバヤバの時間で、しかも完全に予定がかぶっていた。
普通なら出ないって？僕らは頭が悪いので出ました。
詳細は脱線なので書きませんが、難しすぎて絶望した。
10問あって3完、ラスト1問は実装間に合わないとかだった。
多分Tシャツはゲットなのでセーフということにした。
就寝（04:30）
本番
8:30 ぐらいに起きて飯をくい、さっさと会場へ。
以下内容。
A 問題
問題文の解釈に少し手間取ったけどまあやるだけなので書いて終わり (0:12 AC)
C 問題
nakano が読んでいたので教えてもらって、Bのあとに書く予定だった。
B が自明 O(N^2logN) 解は多分 TLE するからめんどい、とのことだったので先に C を書くことにした (0:30 AC)
B 問題
kazuma が O(N^2) で通す。(0:41 AC)
疑問なんですが、5sec で N <= 5000 だったら O(N^2logN) は通ると思いますか？
僕はかなり微妙だと思います（強いて今回のセットで不満があるならここぐらいかな…）
虚無
虚無です。いつもの時間です。虚無虚無プリン。
G 問題
nakano が概要を教えてくれた、明らかに BIT だし kazuma に投げた。
まあいけるね、となったけど方針が想定と違っていて、駄目なケースがあった。
幸いサンプルに存在したので気づけてセーフ。nakano が想定解に修正して kazuma が通す。(1:40 AC)
E 問題
オイラー路が存在するように与えられたグラフに辺を生やせ、という構築。
第一感は解けそう、という感じ。
自分は D, K をやっていたので kazuma がやることに。
実装頑張って投げたが WA、しかし落ちるケースをすぐ発見（やりますねえ！）して AC (3:18 AC)。
G の次に解いたのが E なの完全に異常、僕のせいですごめんなさい。
K 問題
辞書順最大を誤読しており 1WA。Standings みればわかることなんだよね。
前の値から決めていくいつものやつじゃ～んとなる。
けど、普通にやったら O(N^3) なのでどうしようなあとなっていて、
nakano とあーでもないこーでもない言ってたら生えた。
O(N^2logN) の少し重めの実装になって、とりあえずTLEかどうか投げてから考えようと思ってたら通った (3:59 AC)
D 問題
これ最初の方からずっと考えていて、今それぞれの文字でどのインデックスにいるかの dp やるだけなのは割とすぐ見えていたんですが…
これのややこしいバージョンを解いたことがあって、経路復元パートで直前に使った数字しか記憶しないことに起因して、直前の状態が一意に定まらない、みたいな理解をしてしまい、実装がめんどくさいなーと思って後回しにしてしまった。K問題で虚無っていたというのもあるけど。
この場合、現状態として解となりうる状態の頂点集合を持ちながら、復元していく（最終的には一意的になる）実装になる。
でまあなんとか1発で通ったわけですが (4:41 AC)、これで通ってなかったら戦犯だな。
普通に BFS で0を優先的に使っていく遷移をすれば、直前の状態は一意的に定まっているので本当にやるだけでした。なーにやってんだか。
ここからは本番で解いてない問題
F 問題
nakano に解ける解ける言われて kazuma と2人で全力拒否していた問題。
どう考えてもこのセットで飛びついていいものではない。他にやることあるからね。
H 問題
解説聞いてかなりおもろいな～と思った。
グラフの形が特徴的だから、座標の辞書順に埋めていけば、すでに色が塗られている頂点は高々4個しか無い、というのがうまく効いていてすごい。
色の塗替えのあの発想は彩色問題の証明で見たテクな気がする。
I 問題
未だに完全理解していない。本番で4チームも通してるのすごくない？
懇親会
ご飯おいしかった。ごちそうさまです。
今年はブースもちゃんと回ることにした。
毎年1社はでかいカバンを配っているような気がするので、最初にそこにいくと後が楽でいいと思う。
Indeed ブースでコネクションハントをし、頑張って集めて T シャツゲット。
別のブースで真剣にコーヒー淹れていた人がいたんですが、なんか話しかけられない空気でちょっと怖かった…。
感想
決意表明として、来年も同じチームで来ることを誓おうと思います。
今年は同大学の earlybird が WF に行けそうなので、一緒に応援しましょう！！
あわよくばメダルを取って帰ってきてほしいですね～。
