JAG 夏合宿 2023 参加記 - miscalc のブログ

JAG 夏合宿 2023 に参加した。

ICPC のチームは Magical Fish で、メンバーは自分と magsta, confeito の 3 人。今回 confeito 君に合宿に誘われたので行くことにした。（本当は 3 人で行きたかったけど magsta 君が来れなかったみたいで残念）

1 日目

コンテスト

ぎりぎりに家を出たら電車が遅延して 10 分遅刻（すみません……）。

チームのもう 1 人として kumakuma さんに加わっていただいた。戦略としては、kumakuma さんは英語がかなり得意らしいので長めの問題文担当 + US 配列使いらしいので基本的に実装はしないで自分か confeito 君がやる、という感じになった。

confeito 君が A を読む。自分は B を読もうとしたが長そうだったので、kumakuma さんと交代して C を読むことにした。C を読むと一瞬で解けた（というか ABC で既出なのを思い出した）ので書いてすぐ通る。A も簡単らしいので書いてもらい、すぐ通る。

B は大変らしいということで、シンプルそうな E を読む。一瞬むずそうに見えたけど最適戦略が貪欲っぽい？ということで 2 人に相談、正しそうということになる。細かい解法がすぐに出てこなかったが kumakuma さんが二分探索でできるというのを出してくれて、たしかにとなる。実装して AC。後で考えたら（ソート後は）差分更新で線形でいけるけど、にぶたんのほうがバグらせにくそう。

その後は F ができそうという話になる。DAG の最大パスは EDPC にあって、一般の有向グラフだと最大パスは解けないけど今回の問題は「ウォークを取ってきてそこに含まれる distinct な頂点の数」という解釈になる（はず）なので強連結成分の中を好きなだけぐるぐる回れるから、SCC して頂点に重みがついた DAG とみなした後同様の DP で解ける。とすると出次数が $1$ 以下という制約は何に使うんだ？と一瞬疑ったけどそのまま書き始めてしまった（これがよくなかった）。kumakuma さんの蟻本から SCC を写経（蟻本が昔の本すぎて範囲 for すら使ってなくてやや困った）、DP はメモ化再帰が楽そうだからそれをすることにして書き終えた。サンプルも試して提出すると TLE、よく見たらメモ化になっていない。提出、TLE。この辺で $N \leq 10 ^ 6$ と TL 1 sec に気づく。やめてくれ〜　入力を scanf にしたけどだめで、そもそも SCC で再帰 2 回するのが重くて出次数 $1$ 以下を活かした定数倍がより高速な解法が必要なのでは？という話になって一旦後回しに。

K が解けるらしい。問題概要と解法（DP）を kumakuma さんから聞く。えそれ DP じゃだめでダイクストラでは？と一瞬なったけど話し合ったところ自分が勘違いしていて、DP であっている。サッと実装して AC。

confeito 君が G 解けたというので実装を任せて、kumakuma さんと 2 人で F を詰める。出次数 $1$ 以下なことからサイクルから辺が出ていくことはない、よって普通に DP した後サイクルだったらサイクル長を足した値を考えればよさそうで、queue を使うサイクル検出を DP しながらやる、という解法が生えた。定数倍がまだ不安だが、これ以上のものは出なかった。G の実装がまだ終わらないらしいので順位表で解かれている J も見る。既視感があって、ABC に $O(N ^ 2 \log N)$ 想定で既出 + 誰かが $O(N \sqrt{N})$ で解ける旨を言っていたような気がするところまで思い出したけど、肝心の $O(N \sqrt{N})$ 解法を知らず、ちょっと考えたけどよくわからず、諦めた。

G サンプルが合わないらしい。問題概要と解法を聞くとかなり茨の道なことをやっていて、さらに勘違いがあったらしく MLE しそう。一旦諦めて F をやることに。実装して出したけど TLE、グラフを持つのが vector<vector<int>> ではなく vector<int> でいい、とかもやったけどだめだった。結局 ACEK の 4 完で 17 位、激冷え。

コンテスト後

G は DP の値に First / Second / Draw を持たせることばかり考えていたけど、実は普通に得点の差を評価値にしてよくてこれで状態数が削れる。これは気づくべきだった……。

F は confeito 君によると JOI 典型らしく、じゃあ F と G の担当逆にすべきだったねという話になった。サイクルが高々 1 個なのを利用するの、なるほどね。（しかしそこまでの定数倍高速化を要求するのはちょっと不快だなあという気持ちもあり）

夕食をとったり解説を聞いたりした後は部屋で交流した。入浴を済ませた後談話室で ABC に出た。机が低かったり他の団体の声が響いたりしてあまり集中できなかった。SSRS さんのタイピングが速すぎてびびっていた。

部屋に戻って、作問の話とかをしつつ就寝。

2 日目

コンテスト

1 日目チームを組んでいただいた kumakuma さんは 2 日目からソロ参加（元々ソロ参加の予定だったが 1 日目 PC を忘れたらしい）ということで、2 日目は漁師さんとチームを組んでいただいた。

昨日の反省を活かして、ある程度難しい問題は実装を始める前に人に相談しようということにした。

A を見るといかにも FPS 使いそうな 998 で、自分がやることに。ざっと眺めると他にも 998 がいっぱいあって、これは modint 書いたほうがよさそうという話になる。漁師さんに modint を写経してもらっている間に A が解けて AC。

順位表で解かれている C を見る。簡単。confeito 君と 2 人で詰めて AC。

confeito 君が B を、漁師さんが D, E を読んでいて、両方からいろいろ聞いた。confeito 君によると B はいけそうらしいので D, E を考えるけどよくわからず。

順位表で解かれている H を読んで問題概要を伝えると confeito 君から天才考察が返ってくる。コンビネーションを H でも B でも使うっぽいので H の実装ついでに写経する。あとは和が $s$ で積が $p$ な 2 数のパートだけちょっと詰めて実装、AC。

confeito 君が B を実装している間に順位表で解かれている K を漁師さんと 2 人で考える。超頂点作ってダイクストラかなーとかいろいろ考えたけどよくわからず。B を通して戻ってきた confeito 君（FA、すごい！）に助けを求めると、値に $(\mathrm{cost}, \mathrm{from})$ の配列を持つ DP をすると遷移回数がいい感じに抑えられるらしい。たしかにじゃん。実装してもらって AC。この人天才か？

このあたりで順位がだいぶよかった。順位がいいということは逆に解く問題の見極めを順位表に頼れないということでもある。残っている問題で唯一 AC が出ている F を考える。括弧列まではすぐ言い換えられて、カタラン数の証明が思い出せればちょっと進展がありそうだと思ったけど思い出せなくて苦しんでいた。（実際はこれがわかっても解けなかった気がする）

J に AC が出る。読むとゲーム。通したのは上位チームではない。とすると実験エスパーで解けるやつじゃねということになって、漁師さんが実験を書いてくれた。自分は F を考え続けるけど進展なし。

実験が書けたらしいので結果を見にいく。長方形に A, B をプロットすると見やすいという話になって（ここ地味に偉い）、見ると大きいところでは規則性がありそう。 $3 \times 3$ と $3 \times 5$ がコーナーなので $H,W \leq 5$ なら愚直、そうでなければ規則性、のコードを漁師さんが書いて提出。WA。実験結果を $H,W \leq 7$ とかじゃなくて $H \times W \leq 50$ とかで表示すると、 $2 \times \mathrm{BIG}$ のケースが処理できていないことに気づく。ここを自分が詰めて書いてもらって AC。

F を考え続けるけど進展がない。

confeito 君が L 解けた気がするらしい。聞くと MCF でできそうとのこと。これを正しいと思ってしまった（実際は嘘だったけど、指摘できなかった。とてもよくない）。漁師さんに kactl の MCF を写経してもらうと、謎の機能を使っていてコンパイルが通らない。こうならないように持ち込むライブラリはちゃんと把握しておくべきですね。Gifted Infants の MCF を見ると変なことはしていなさそうでコンパイルが通った。いざ実装、というところで confeito 君が解法の誤りに気づく。聞くとたしかに嘘だ。残り 10 分くらい、ここから立て直すのは厳しい。結局 ABCHJK の 6 完で 5 位。だいぶいい順位。この日は confeito 君がかなり強かったという印象。

コンテスト後

解説を聞くと F も L も激ヤバでびっくり。チャンスがあったとしたら D, E なのかなあ。まあ今の実力だとこの 6 完が限度という気もする。

談話室でボドゲをした後、部屋で ARC に出た。B が通せなくて激冷え・青落ちで険しい気持ちになった。

その後談話室で Kite_kuma さんと将棋を指した。tokusakurai さんとも指したかったが時間がなくて残念。また機会があればよろしくお願いします。

部屋では 1 行ずつ作問をして遊んだ。滅茶苦茶な問題になっても面白いし、それに混じってたまに良さげな雰囲気の問題が生えても面白いので、レクとしていいかもしれない。nonon さんの参加記に問題が載っているのでよければ考えてみてください。

3 日目

コンテスト

3 日目はチームが組めず、2 人でやることになった。

confeito 君が A を、自分が B を読む。A は簡単ですぐ通る。B も簡単なはずだが、実装にちょっと手間取ってしまった。

C の概要を聞く。「過半数が同じ」が条件ということの正当性を 2 人で確認。confeito 君曰くこういう数え上げは自信ないらしいので自分が考えることに。その間 I を考えてもらう。

C を立式すると解けた気になる。998 が他にもあるので modint とコンビネーションを写経して（結果的には modint 書くべきだったかは怪しい）、実装。この modint を普段使いしていないせいでなぜかコンパイルが通らなかったりして手間取る。実装すると合わない。よく確認すると立式が間違っていることに気づく。この式だと今の解法では解けないので一旦後回しに。

I を考える。いろいろ議論すると ( を prique にためて ) がきたら「まだペアになっていない ( と組ませる」「もうペアになった ) と交代」のどっちかをやるという感じになりそう。たぶん正しいとは思ったがちょっと自信がなかった。confeito 君が実装。

その間に順位表で解かれている J を見るとド典型。C とか I より先にこっちやればよかった。

I を提出、WA。実装に細かいミスがあるのか方針がそもそも嘘なのかよくわからないので、コードを印刷してリカバリしてもらっている間に J を実装。実装中に DP だとうまくいかなくて 01BFS にする必要があることに気づく。実装重くないか心配されたけど、B でも BFS をやったこともあり大丈夫だった。AC。この間に I のバグに気づいてもらって I もすぐ AC。

あとは C, E と心中するしかないかなという感じ。C はあれから進展がなく、E を 2 人で考える。valid な順番だと区間を広げていく感じになることに confeito 君が気づいて、それを逆から見て立式すると $\mathrm{dp}(i, j) :=$ 左から $i$ 個、右から $j$ 個取ったときのなんかの積の総和という感じになりそう。あとはこれが線形になればいいんだけど、わからない。自分は C と E を行ったり来たりしたが、最後までわからなかった。結局 ABIJ の 4 完で 14 位、激冷え 2。