ICPC 2019 Asia Bangkok Regional 参加記(コンテスト)

はじめに
コンテスト
- -20分(09:30)
- -10秒
- 0分
- 10分
- 69分
- 108 分
- 114分
- 139分
- 142分
- 162分
- 191分
- 240分ぐらい
- 282分
- 300分
- コンテスト後
反省
感想
問題概要
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N

はじめに

The 2019 ICPC Asia Bangkok Programming Contest の参加記です.
チーム TigerSone で出場しました.
チームメイトは etonagisa, nikutto です.

5泊7日バンコク旅行となりましたが, とりあえずこの記事ではコンテストについて書きます.

結果は 14問中8完で12位でした. WF行くには11完は必要そうで, つらい.

コンテスト

大体時系列順.

-20分(09:30)

・09:30 から開始のはずだが当然のように遅延する. ボランティアの学生っぽい人も困惑.

-10秒

・突如人力カウントダウンが始まる.

0分

・いきなりコンテストのポータルサイトが落ちていてプリンターと scoreboard が使用不能. どうなってんねん.
・問題文は印刷したものが渡されたが, 14問ある. 多くない?
・とりあえずどれから解けばいいか全く分からないので nikutto が環境設定している間に読むことにする.

10分

・A問題が解ける気がしたのでちょっと書きかけて全然解けてないことに気付く. 後回しに.
・Hが自明らしく eto と nikutto がペアプロを始める.
・依然 scoreboard は壊れているので問題を読み進める.

69分

・Hの実装が全然自明でなくて出力形式もカスだったっぽくて二人が大変そうだった. HをAC(69分).
・ここで scoreboard が復活して他のチームが何を解いてるか問題番号付きで見える. randomized とは何だったのか...
・A, D, F あたりが若干通っていたか.

・K, M がすぐ解けそうだったので nikutto に渡して, eto と D のペアプロを始める.

108 分

・eps の位置が間違っていて 1WA 出したが D を AC.

114分

・nikutto が M を AC.
・A が2秒考え直したら明らかだったのでコンピュータが空いてる間に BIT を写経したりする.

・F がすぐ書けるらしいので eto, nikutto がペアプロする.
・この辺で scoreboard 見たがいつの間にか randomized されていた. ワクワクしちゃうな.

139分

・F, AC.

142分

・A, AC.
・ここで nikutto が K を書き始めるもライブラリの LCA を写そうとしたところで誤って SCC のコードが書かれていたことに気付く.(???)
・B が解けそうな構築だったので eto と考える.

162分

・nikutto がその場で LCA を錬成して K, AC. ゴリラ.
・nikutto に N を伝えた後, B が gray code っぽくできるということになり eto と書き始める.

191分

・B, AC.
・N を nikutto が書き始める.
・問題ストックが無くなってきたのでこの間に eto と問題共有をする. C, E, L は不可能そう. G, J はまだ人間に解ける見た目をしているのでちょっと考えることにする.

240分ぐらい

・nikutto が N で WA.
・ここで順位表を見ると Cafe Mountain しか通してないことが分かる. (提出すろとペナで問題と順位表の対応関係が分かる) 他のチームも無限に WA を出していてヤバなので一旦諦めて I を書くことにする.

・I は nikutto によると遅延セグ木に(2次)多項式を載せるらしい. ペアプロを始める.
・実装方針の不一致により揉める.
・サンプルが一発で合ってしまったので提出. WA.
・この問題, 問題文には書かれていないが実は mod を取って出力する問題. どういうことやねん. eto も呼んでデバッグ.

282分

・I, AC.
・N を eto, nikutto のペアプロに切り替える.
・残り時間はほとんど無いが, 自分は G, J を考えることにする.

300分

・コンテスト終了. N は通らなかった.
・終了3秒後にオーバーフローが見つかる. 悲しい.

コンテスト後

・girigiri と同じ部屋だったので話を聞くと F のジャッジが壊れていたらしい. かわいそう.
・秒速で yes/no が進む. Cafe Mountain はずっと1位だった. やべ〜.

反省

・序盤に H を選んだのは仕方ないか? 考察自体は一番簡単だったらしい.
・B を通した後の動きが悪かった. I を先に書き切るか, N をペアプロすべきだった.

・サンプルをちゃんと読むようになった. 誤読が無かったのは進歩か. (???)

・とはいえ, 理想ムーブでも N に加えて G or J を通せたかというと微妙. 単純に弱いね.

感想

・上位に入るには10完が必須で, 参加者のレベルが高いコンテストだったように思う.
・運営は全てがガバガバのワクワクコンテストなのに問題がまともすぎてびっくりしてしまった.
・会場で常にガイド役の学生(日本語めっちゃ上手い)が付いてくれて助かった.
・ところで横浜まで2週間を切ってるらしい.

問題概要

多分問題が公開されていないので説明.

A

次のクエリに $T (\le 100000)$ 回答えよ.
$N (\le 10000) , M (\le 1e7)$ が与えられた時, $N$ 以下の整数の積で表される $M$ 以下の数の種類数.

B

$N (\le 8), M (\le 8)$ と $N + M$ 個の整数の集合 $S$ が与えられる.
$2^N * 2^M$ のグリッドで, $2^{(N+M)} - 1$ 以下の正整数を一つずつ含み, 隣接するグリッドに書かれた整数の XOR が必ず $S$ に含まれているようなものを構築せよ.

C

$N (\le 100000)$ 頂点の木があり, 各頂点に整数が書かれている. 頂点に書かれた値を $1$ 変更するにはコスト $1$ がかかる.
隣接頂点の値の差の絶対値を $K (\le 1e9)$ 以下にする最小コストを求めよ.
無理そう.

D

$X (\le 100), K (\le 100)$ に対し, $N^{16} \le X^K$ となる最大の $N^{16}$ を答えよ. 存在しなければ "Impossible", $10^{100}$ を超えるなら "too big" を出力.

E

$N (\le 8) * M (\le 8)$ のグリッド型迷路がある. 迷路に入る前に4方向の移動確率を定め, ゴールに必要な移動回数の期待値を最小化せよ.
無理.

F

読んでない

G

長さ $N$ の 'T', 'H' からなる文字列がある.'H' の個数番目 (1-indexed) の文字を flip する, という操作を繰り返す.
全て 'T' にするのに必要な操作回数を答えよ.
難しい.

H

読んでない.

I

長さ $N (\le 100000)$ の数列 $A$ (初期値は全て $0$ ) に対し以下のクエリを $Q (\le 100000)$ 回投げる.
1. $[L, R]$ の要素に対し順に $1^2, 2^2,..., (R-L+1)^2$ を加える.
2. $[L, R]$ の要素の和を答える.