The 2017 ACM-ICPC Asia Yangon Regional Programming Contest 参加記
はじめに
kazuma, nakano, 僕の3人でチーム KazumaDragon としてミャンマーの Regional に参加しました．
ミャンマーで開催されるのが今年が2回目とのことで，まだ記録が少ないと思うので参加記を書こうと思います．
前半はプラクティスとコンテストについて，後半は旅程の全てを（大体）時系列順に箇条書しています．
プラクティス
- 開始前にスコアボードを見ると5問もある．なんか雑に開始した気がする．
- Aは線形方程式，Bは式をパースして場合分けを丁寧に頑張るだけ，CDは（僕は）読んでない，Eは基本貪欲に取っていく枝狩り探索？みたいな出題．Bは途中で問題の修正が入った．
- 意外とまともだなあ．去年も見た目はまともらしかったしね．
- とりあえず環境を確認する．
- IntelliJ，NetBeans，Eclipseなどがある．Java勢に優しい．
- 普通のテキストエディタもターミナルが一緒についてるそこそこ使えるやつがあったのでそれで書くことにした．
- というかVimがあるって書いてあったのに vim を叩いたら無いって怒られた．困るよ〜．
- テンプレートを書いて，WAを出すコードを投げる．CE．は？
- C++11 すら使えないらしい．環境はいいんだからオプションちゃんとつけてほしい．多分最適化オプションもついてないので pragma optimize しましょう！
- 修正して出す．TLE．なんでやねん（これは僕が提出先を間違えていただけで向こうは悪くない
- 気づいて再提出．ちゃんとWAが来る．良し．
- REを出すコードを投げる．REがちゃんと返ってくる．やったぜ．
- TLE の限界やスタックサイズの確認もする．予想よりまともで安心．手元でちゃんと動くなら大丈夫そう．
- そろそろAC1個だけ貰いに行くかということで，Aがやるだけなのでちゃんと読む．
- 行列と列ベクトルのサイズが早速書いてない．Clarの練習用にわざと書いてないんだろうなと解釈する（ほんまか？
- Clarを投げたら予想通りのサイズで安心．書く．バグる．なんとかAC．
- 色々あってこの時点で終了まで20分ぐらい？まあACいらんし適当に過ごそうと考える．
- 終了20分前ぐらいにスクリーンと照明が急に音を立てて落ちる．草．なんで落ちたのか未だに不明．
- 終了直前にまた照明が音とともに落ちる．なんでや．
- ちなみに手元のPCは落ちないので安心してください（？）
- ここで終了．一応結果を伝えると，E問題がめっちゃ通されてました．
- なんだ問題自体は普通じゃん．難易度もPracticeの割には高かったように思う．
- 難しかったねーと適当に感想戦をする．
関係ないけど，うちの大学の実験室よりはるかにPCのスペックが良かった．弊大学は†悔い改めて†
本番
- カウントダウンとともに開始．パスワードを入力してログインするところから始まる．
- 僕がテンプレートとか用意する間に他の2人に問題を読んでもらう．
- Practice で作ったファイルが全部残ってて草．これええんか？
- なんかGがセグツリで高速化する実家DPらしいので書く．初期化部分をミスってバグったがAC．
- 次にDが素数と合成数列挙するだけと聞いたので書く．WA．やべえ．
- flush のせいかなと思い flush して提出するもWA（めっちゃもったいない）．うーん？
- コード読んでる限り変なところは無いので後回しにしてしまう．（なんで問題文を読み返さなかったのか）
- （他の問題概要を聞いていたが順番を覚えていない．確か I を聞いた気がする…サンプル合わなくてIの誤読に気がついた？だったかな）
- Aを読んだらやるだけだが実装どうするか迷ってしまう．他の問題考えながらということで後に回す（これも微妙な選択かなあ
- Dは少し誤読していたらしい．文字列が与えられるんだけど，space を含むらしく getline が必要とのこと．Practiceでもそうだったけどやたら getline 書かされるなあ．直してAC．
- Fが簡単らしいので概要を聞いて書く．なんか僕の理解が甘かったらしく変なコードを書きかけてしまい，kazuma が見かねて代わりに書く．AC．ごめんなさい．
- （ここから1時間ぐらい辛かった気がするがなんで辛かったのか覚えていない）
- Cの概要を聞いたが制約がヤバすぎる．テストケースの数 10^5 ってなんやねん．クエリじゃないんだぞ．
- しかも各テストケースで 10^10 ぐらいの出力が要求されるらしい．えぇ…．流石に Clar を投げるがよくわからない返答が返ってきて，なんかよくわからないため後回しにすることにした（これが結果的に一番もったいなかった）
- JとLは見た目がやばくてみんな敬遠していた．（結果的には正しかった
- Bを読んだので kazuma に伝えたら実家なのでかけるとのこと．僕が書くより早そうだったため任せてしまう．
- union find木だけ僕が書いたんだけど，結構バグらせてしまった（大反省）．それ以外もちょっとだけバグって時間をロスするが，一応ACする．
- 裏で簡単だと聞いていた H の紙コーディングをしていたため，その後すぐにACする．
- nakano が I を頑張って書いていた．Iには全く関わっていないので，裏でAを紙コーディングする．
- 紙コーディングが終わって書く．ちょっとバグったけどすぐ直してAC．
- この時点で10位ぐらい？初アジアにしてはいいんではということで少し安心する．
- Eの概要を聞いて真面目に考える．3次元空間上の点を，最小限の直線で全て貫くという問題．
- この間 kazuma は K問題を，nakano は I （と K）を考察していた．
- 点の数 n <= 100 なためフローが生えかけたが無理なので（それはそう）棄却する．
- こんなんNP困難やろという気持ちになる．適当に枝狩りしかないが n <= 100 はやばそうなので一旦逃げる．
- kazuma が E をちょっと考えて最小費用流でいける（僕が棄却したのと全く同じやつ）という意見をくれた．なぜが行けると勘違いして（は？？？）書いてしまう．
- ライブラリ移すパートでバグらせる．なんとか直してサンプルチェック．合わない．当たり前や．
- これ無理やんけとなったので，あとに回す．
- Kをちょっと聞いたところ，10^8 のオーダーでエラトステネスっぽいことをするらしい．まあ無理だよね
- I はバグっているらしいし，ここらへんかなり辛くなってくる．解ける問題が無い．（この時僕の頭にC問題の文字はなかった
- kazuma がエスパーする．「10^8 じゃなくて 10^7 で通るんでは？ｗ」とか言って投げる．
- 僕はさすがに無理だと思っていたが AC する．流石に草．
- もはや書いてある制約が何も信じられない．そしてここで僕がエスパーする．
- 僕「Eは n <= 100 じゃなくて n <= 10 とかやろｗ」
- kazuma は流石にありえないやろ，と言って嫌そうな顔をしていたが，僕の独断により n <= 20 ぐらいの bitDP 解をちゃっと書く．投げる．AC．
- もう顔中草まみれや．
- とりあえず nakano の I を祈る．めっちゃバグっていたが AC した．さすがプロ．
- Iが通った時点で9完，残り15分ぐらいだったので，もう書けないかなとなって感想戦をしていた．
- 本番の問題よりPracticeの方が難しくない？みたいなことを話していた気がする（これは嘘で，不正ACをしているため
- なんか終了5分前ぐらいで謎の封筒を渡されたり，写真を取られまくったりする．順位表が凍結されている意味とは…
- 終了．終わった直後は満足していた．
終わった後に気がついたんですが，問題文が書いてある前に注意書きみたいなページがあって，そこにジャッジが投げうる結果がすべて丁寧に書かれていた．こういうのはPracticeで書いてくれたほうがうれしいですね．
本番の問題概要
自分で読んだのは結局ABだけなので雑にまとめます．本文は公式ページから読めるけどね．
- A問題．完全二分木をトーナメント表みたいな形式で出力する．表の深さ N <= 13．
- 再帰でいい感じに書いた．出力が多いので fast IO を使うと安心っぽい．
- B問題．友人関係と敵対関係，および推移律的なルール群が与えられるので，各クエリで与えられた2人の関係を答える．関係の数は 50個以下．
- 冷静に考えると2部グラフ判定するだけ．UFで適当に．サイズが 10^5 でも解ける．想定はクエリごとにDFSで探索とかかな．
- C問題．グリッド状のタイルを，あるルールに従って色塗りしていく．各時刻で新たに塗られるマスを出力していく．タイルの幅と高さはそれぞれ 10^5 ，テストケースの数は 10^5個
- 制約がヤバイ問題その1．実装はやるだけですが若干めんどくさいか．Clarを投げるのは最低限必要で，あとはStandingsをみて解ける問題か確認するのが大切．実際うちのチーム以外の上位陣は通しているしね．
- D問題．文字列が与えられるので，各文字を 8bit 整数とみて01ビット列に直す．その後はそれに合わせて合成数と素数を出力するだけ．入力サイズはめっちゃ小さい．
- E問題．3次元上にある点をできるだけ少ない点で貫くときの，最小の直線の数を求める．点の数 n <= 100
- 制約がやばい問題2．多分枝刈りが想定だが，エスパー力も大切（いいえ）．assert(n <= 26) してREせず通ったため，書かれている制約の最大値が本当に入力に存在するとは限らないらしい．
- F問題．2つの商品があって，それぞれコストと利益が「問題分に」与えられているので，あるコスト以下で利益を最大化する．
- 入力サイズが小さいので全通り試すと通ります．問題分が無駄に長かった．
- G問題．数列に含まれる単調非減少列の中で，総和が最大のものを求める． N <= 10^5
- 典型すぎる．セグツリで高速化するDPで．
- H問題．シード値と b が与えられ，それらから数列 a_n を作っていく．i < j で a_i = a_j となるタイミングを検出せよ．ただし，a_{i+1} = (a_i を b 進数で表したときの各桁の平方和を10進数で表したもの) とする．b <= 17．
- bが小さいので愚直に1つずつ計算していくだけですぐ衝突する．
- I問題．一直線上に N 地点 Hyperloop がある．各 Hyperloop 間の距離は d_i である．i 番目の Hyperloop では，ある時間（任意に選べる．0でも良い）の間加速度 a_i で加速できる（加速中はその場にとどまっているみたいな感じです）．このとき，初期地点から最終地点まで行くためにかかる最短の時間を求めよ．テストケース T <= 90, N <= 10^3, a_i <= 10^4, d_i <= 10^4
- まともに難しい問題1．O(N^2) のDPで解いたらしい．O(N^2)のDPにする前は，嘘貪欲とか，頑張って場合分けするとかやっていてバグったらしい．このセットの中だと一番解きがいがある問題っぽい？
- J問題．文字列 $S = S_0S_1 \ldots S_{N-1}$ のハッシュを $H(S) = \sum b^{n-i-1} \times D(S_i) \mod m $ によって定める．ただし $D(a) = 0, D(b) = 1, \ldots, D(z) = 25$である．ここで，h, b, m, n が与えられる．長さ n の文字列で，ハッシュ値が h となるものは何通りあるか求めよ．
- まともに難しい問題2．本番はどのチームも解いていない．噂によれば FFT とダブリングで解く？みたいなことを聞いた気がする．
- K問題．[l, r] に含まれる自然数で，約数の総和が 3 で割り切れるものの個数を求める．1 <= l <= r <= 10^8，テストケースの数は20個．
- 制約がヤバイ問題その3．制約を信じるなら線形で前処理して各テストケースO(1)しかないがわからない．エラトステネスににた感じの処理でオーダーがO(nloglogn)ぐらいには落とせたらしいが，それでもやばいね．
- L問題．正五角形に同じサイズの正方形を（問題文の図に書いてある詰め方で）8個詰めるとき，詰め込める最大の正方形の大きさを求める，みたいな問題．
- 本番では避けていた（というかほとんど読んでない．Standingsみても手を付けているチームは少なかった）．二分探索で頑張るか，手計算で頑張るか．めんどくさそう．
結果
A,B,D,E,F,G,H,I,Kの9完遅解きで4位でした．ちなみにI問題のFA＆唯一のAC．150ドルGET．日本人のスポンサー（？）の方と一緒に写真を撮った．
1位も9完だったので，僕がCを書いていれば1位だったと思うとチームのみんなには申し訳ないと思っていた．
D の誤読がなければ確実に3位には入れたため，結果を見たときは嬉しさと同時に悔しさが残る…．まあ結果論だし，今の結果に納得はしています．
旅程まとめ
7日（前々日）
- 飛行機は8日朝だが，家から間に合わないことに気がつく．
- 空港近くの友人宅に泊めてもらう．夜ふかしした．
8日（前日）
- 7時ぐらいに空港着．
- 受付でWAが生える．向こうのミスっぽいが焦る．
- なんかいい感じにいけるらしいのでセーフ．幸先悪いなあ．（こういうことがあるので早めに空港には行きましょう
- 出国時に荷物検査で引っかかる．筆箱にカッターナイフがあるのを忘れていた．
- とりあえず北京につく．乗り継ぎが8時間ぐらいあった．（乗り継ぎが長いとつらいので，飛行機のチケットは早めに取りましょうね．
- ミャンマーには結局24時ぐらいについた．ICPCの人たちが出迎えてくれた．
- タクシーを捕まえてくれたんだけど，早速車の治安が悪い．空港前がすでにカオス．
- ホテル着．さすがにすぐに寝る．
- 結局この日は友人宅での朝ごはんと，機内食 x 2 しか食べていない．
9日（Practice当日）
- 6時半おき．早すぎるからもっと遅くしてほしい．
- ホテルにバスが迎えに来てくれる．
- 相変わらず車の治安がアレ．10秒に一回はクラクションがなる．
- 大学着．大学内に普通に犬が徘徊していて笑う．
- Practiceを適当にやる（内容は上に書きました）
- なんか向こうが観光の手配もしてくれるらしい．シュエダゴン・パゴダに案内される．
- でかい．修行僧がタブレットでなんかしていて，すごいなあとなる（語彙力が無い
- 外の露店の揚げ物を買って食べる(2000キャットぐらい．日本円換算はだいたい10分の1すれば良いです．つまり200円．）美味しいが油が強かった．（胸焼けした
- 果物とかはお腹をこわす可能性があるらしいので，怖い人はやめておくのがよいです．
- ホテルに帰る．近くに外国人向けの店があったのでそこで晩御飯（14000キャット？）．さすがに美味しかった．
- チームで若干明日の戦略を考えて，早めに寝る．
10日（コンテスト本番）
- 6時15分起き．なんでこんなに早いんだ．
- 同じホテルの他の人々がこない．競プロerは万国共通で集合が下手らしい（要出典）．20分ぐらい遅れる．
- 2件目のホテルでも人々が集合時間にこない．頼むよ〜．
- 予定より大幅に遅れて大学につくとコーヒーとパンが配られる．おいしいパンだった．
- コンテスト開始時間がガバガバになっているのに何のアナウンスもない．大丈夫か？
- 待っていたら唐突に大声でカウントダウンが始まる．カウントダウン開始が何の前触れもなく3秒前に行われるってどうなんだ．
- コンテストの内容は上に書いた．
- コンテスト終了後は大学でお昼ご飯が配られる．まあまあ美味しかった．
- その後は観光に連れて行ってくれる．Taukkyan War Cemetery という共同墓地とショッピングモール．
- 太平洋戦争時の連合国軍戦没者の共同墓地っぽい？
- 墓地なのに沢山の人がにこやかに写真を取っていて少し驚く．
- ショッピングモールで人権を得る（SIMを買う）
- ショッピングモール付近は車の治安がやばすぎて，もはや僕達を回収してくれるバスがどこにいるのかわからない．
- 結局出発が30分ぐらい遅れる．しかも一部の人の回収に失敗していて草．そりゃそうなるわ．
- 閉会式の会場につく．めっちゃいいホテル．
- 席が余っていなくて，VIP席に案内されてしまう．しかも主催者テーブルっぽい．
- 偉い人の話を聞いてリザルトを見る．結構盛り上がっていた．
- その後は突然POPなミュージックとともに前で踊りが始まる．VIP席（舞台に近い）にいたせいか巻き込まれて踊ることになった．
- ビュッフェ形式のはずなんだけど，VIP席に座っているのでホテルの人が料理を運んできてくれる．最高に運がいい．
- 当然料理は美味しかった．
- 主催者の人とちょっと話をする．日本の東京は苦手らしい（人が多いため）．わかるなあ．
- あとは適当に写真を取ったりしてホテルに帰る．早起きする必要がないので適当にすごす．
11日
- 今日は何もないので飛行機の時間までブラブラすることに．
- ホテルまでICPCの人たちが迎え（タクシー）に来てくれるらしいので，チェックアウトした後またホテルに戻る必要があった．
- 13時ぐらいにチェックアウト．荷物を預けてダウンタウンの方へ．
- もちろんタクシーを捕まえる．8000キャットで乗せてくれた．
- 前日に，お土産を買う店をコーチが聞いてくれたらしいが，月曜日が定休日らしい．運が悪い．
- 中心部に近づくと，車の量が激しくなってきた．
- 日本人もよく行くという，Monsoon という店でご飯を食べる．チキンカレー(6800キャット) とお酒(5000キャット)を食べた．美味しい．
- その後は適当にぶらつく．
- しかし暑すぎて辛くなってきたため，適当なカフェに入ってスムージー(2500キャット)を頼んで良い時間まで粘る
- その後はスーパーを見つけてお土産を買って帰る．大体 3000 キャットぐらい使った．
- 変なオジサンに「オンナノコどう？」って聞かれた．（いら）ないです．
- 晩御飯は一風堂を見つけてしまったので吸引される．美味しい．
- 一部日本語で接客していた．「イラッシャイマセ」「麺カタメ」「カエダマ」など．
- タクシーを捕まえてホテルまで送ってもらう．1つ目のタクシーはなぜか理由も話さず断られてしまったらしいが，2つ目のタクシーは5000キャットで乗せてくれた．
- 飛行機にのって爆睡する（機内食を逃す
