potato167, noshi91, tatyam で参加しました。
tatyam 視点 → ICPC 2022/23 国内予選参加記 (tatyam 視点) | 東京工業大学デジタル創作同好会traP
初手
A: potato, B: tatyam, C: noshi で担当。noshi は実装が遅いので序盤の速度ゲーに触りたくないため、この位置に入れてもらった。
C
休息と練習を連長圧縮したときにどうなるかで場合分けして書こうとするが、始まりと終わりがそれぞれ休息/練習のパターンを全て考慮するとうんざりするため手が止まる。 練習をいくつに分割するかを固定すればサクッと解けることに気付き、通す。
D
C を通して状況を聞くと、potato が D を読んでとりあえず飛ばして E を読んでいるらしいので D を見る。 作りたい列の部分列が 1 本の列として成立するかどうかの必要条件を列挙するといかにも十分条件になっていそうで、証明できた。 これをもとに DP を書き始めるのだが、素朴にやると 3 乗なので逆から読んで累積和を使うと 2 乗になり、通る。 後で解説を読むとあまりにも簡潔で反省。
F
tatyam が E と格闘しているらしいので、F を見る。 構文解析した後は木 DP するしかないように見え、先頭から l 文字末尾から r 文字追加で t 文字消すみたいな DP で計算は出来そう。 落ち着いて考えると t は持たない方が良い。 あまり詰めてなくて正当性も時間計算量も怪しいが、noshi は後半の問題の方が得意そうなので F を potato に任せて逃げる。
H
読んで 1 分くらいで考察が終わる。体感時間なのでもっと掛かってるかも、とりあえず考察で詰まる場所は無し。 実装も結構軽そうなので F に戻らずに実装開始を宣言。通る。
G
まず、後戻りが必要な場合が存在するかを考え始める。 すると普通に必要そうということになり、状況が複雑すぎるので解法の選択肢があまり多くないように思える。 とりあえず二分探索することにすると、エージェント A が進んだ距離と B が進んだ距離を 2 軸とする平面において、距離 D 以下の点を考える。 これで (1, 1) と (n, m) が連結になっていればよい。 平面を格子状に細切れにして、双方のエージェントが線分上を移動するような長方形領域に分ける。 すると距離 D 以下の点は楕円になり、特に凸集合なので連結。 後は隣り合う長方形に移動できるか調べて連結性を判定すればよい。
ここまで考えたあたりで tatyam が E を通していた気がする。 tatyam に G を説明しつつ、そもそも二分探索しない方が 100 倍簡潔であることに気付き説明し直したりグダっている間に tatyam が理解。 G を通せば勝てると思ったので、2 人で並列実装して出力をそろえてから提出することにする。
ほとんど同時に書き終わるが、出力が合わない。 合わないケースにおいて常に noshi の方が出力が大きいことから、始点と終点の処理を忘れているだろうとエスパーしたところ、成功。 tatyam が修正をして AC。
F
この時点で残り 30 分くらいだったと思う。 potato が F で苦戦していて WA が出ていた。 とりあえず説明してもらいながらコードを眺めるが、そもそも構文解析の時点で読解に苦戦。 tatyam にデバッグしてもらいつつ、noshi は新たに書き始めることにする。
とりあえず構文解析を書こうとして、LL(k) でないことに気付く。 こういうときどうすればいいか分からず構文解析のコードが滅茶苦茶になり (反省)、時間を浪費。 のこり 10 分ほどになりこちらは無理ですと謝罪していたら、バグが直ったらしく通る。
全体の感想
今日は解法がすぐに出てきた。 多少裏目に出た部分はあったが、立ち回りは悪くなかった気がする。 勝って非常に気分が良いので、何でもいい (本音)
