SuperCon 2024 参加記

去年はチーム Takenoko (17 + ytqm3 + Cyanmond) で出たが、今年はチーム Calamari (17 + Cyanmond + shiomusubi496) で出た。この名前は、使うスパコンが SQUID という名前でこれはイカの意味があるらしいので、英語でイカ料理を表す Calamari を提案したところ他に案がなく決まった。

1 日目

この日は鉄緑会の校内模試があったようなので、後半は自分が回収した。どちらにせよ初日はスパコンまで到達しないので、深夜労働などをしてもらった。

問題概要を把握した。問題としては、

  • 森林火災のモデルがある
  • 初期状態が与えられる。具体的には島があって 10 箇所で火災が発生し始める
  • 10 単位時間後に、燃えている木の半分まで木を切ることができる

という条件で、 500 単位時間後まで残る木の本数を最小化するというタスクだった。

なんとなく方針を考えた。焼きなましくらいしかないのではないか、という結論になった。

2 日目

まだ並列化にはたどり着きそうになかったので、競技時間に限らずだらだらと進めていた。

Visualiser を GPT に書いてもらった。火災の広がり方だけ見たかったので、変なツールを作るのはやめて maplotlib で 10 単位時間ごとに画像を出力させるスクリプトを書いた。他のチームを見るに、少し雑すぎたかもしれない。Visualiser を見たことで、結局それぞれの火災は消せない限り大きく広がることがわかった。そのため、まずいくつの火種を消せるか、そして全てを消せないならどれを選んで消すかの勝負になると判断した。

火が存在するマスやその周辺のマスにある木を割合に応じて雑に切るルールベースの戦略を実装したが、全然消えなかった。木を切るコストの制約がだいぶ厳しいと判断して、以下の方針に決めて実装を始めた。

  • 各火種はほぼ独立と考えられるので、各火種についてそれを消すために必要な最小のコストを求める。
  • 消す火種を bit 全探索などして、最終スコアが一番良い選び方を求める。

前半の、火種を消す最小コストを求める焼きなまし法を、深夜まで書いていた。

3 日目

思ったより火が消せることがわかったので、全ての火種を消すのがスタートラインと考えた。上の焼きなましの近傍を追加するなどしたところ、 8/10 ほどのケースで全ての火種を消せるようになった。

そろそろ並列化をしたかったので、午後は SQUID 上で実行を始めた。ところが全然コードが動かないハプニング発生。チューターの方のヘルプを頂いて 1 時間ほど格闘していたら、特に何もしていないのに動くようになった。原因不明。兎にも角にも色々とバグがあったので、それらを直していたら、あっという間に 17:00 になってしまう。まだ何も並列化できていなかった。

方針上細かい計算が多くなり、並列化が難しかった。焼きなましにおけるシミュレーションに並列化を試したが、 OpenMP のスレッド起動がボトルネックとなり遅くなるだけで終わってしまった。MPI で SQUID VE 1 ノードの 8 procs に 10 の問題を分配 (事実上 5 procs)、 10 コアは単に焼きなましの初期解 30 個ほどを試すのに使った。実はこの初期解をひたすら変えて実行するのが割と効いた。あまり洗練されていない焼きなまし法だったということかもしれない。手元環境に MPI を入れて動かしたところうまく動いたので、これがきちんと動くことを祈っておいた。

並列して、火種を消した後の微妙なスコアの最適化が勝負を分ける可能性を考えて、そのために別で焼きなまし法を使うことにした。初期解を上の最小コストの方法、近傍を雑に定めて動かした。終わってから聞いてみると、これが実はあまり上手に書けておらず、一部チームはもっとうまく最適化したようだった。(残念ながら、そこは本番うまくコードが動かなかったらしい。)

ちなみに、バグ取りではスパコン上で動かすと勝手が違って難しいので、手元で gcc のデバッグ用オプションを付けて動かすのがよかった。最適化で Runtime Error にならないようなバグを拾ってくれたことが 2 回ほどあった。

4 日目

ここまでのコードを全部合わせて SQUID 上で動かしたところうまく動いた。提出は 13:00 で 3 時間ほど余裕があったので、一応配布の Evaluation プログラムを動かして出力が正しい形式かどうか確認するなどしていた。結局 19/20 くらいのケースで火が全て消えるようになった。地味なパラメータ調整をして、おそらく最終提出が 12:00 くらいだったと思う。

閉会式

他の強いチームが出力形式を間違えた？こともあったのか、全問題で 5 点 (順位に応じて各問題のスコアが 1, 2, 3, 4, 5 位に 5, 4, 3, 2, 1 とつく) を取ることができて 1 位で文部科学大臣賞をもらえた。レポートをちゃんと書いたからか、学会からの賞などももらえた。去年は 2 位相当のスコアを出していながら非本質部分でバグを埋め込んで 0 点だったので、リベンジができてかなりうれしかった。

その他雑多

去年は速度競技だったのに対して今年はスコア競技だった。スコア競技のほうが単純にやるべきことが増え、去年より環境が扱いづらいこともあって、コンテスト期間の時間管理がシビアだったと思う。個人的には速度競技の方がスパコンで感動できて楽しかったが、スコア競技で色々アイデアを試すのもなかなか面白かった。

まだ賞品類諸々が学校にあるようなので、日本に帰ったときに回収したい。

自分はもう出られないのですがとても面白いコンテストなので、いま中学生の人は今後ぜひ挑戦してみてほしいです！

APIO 2024 参加記

なんと 2 年連続中国ホストでの開催。決め方がよくわからないが、候補がいなかったのだろうか。IOI China 開催の布石だったりする？

問題は (去年と同じく) 微妙だった。これは別に中国が悪いわけではないが。。

問題はこちらから

A : September

特に書くことがない。shiomusubi496 とかは即満点を書いて 10 分ほどで終わらせたと言っていたが、自分は春のトラウマで全問題読んで並列に考えていた。「こういう雰囲気」の中国原産問題は解けることが本当にないという経験もあった。ただどう見てもこれが解けそうなのでとりあえず部分点を書くと普通に通り、拡張した満点も通った。30 分くらい。(この問題に使ったのは 15 分くらい)

この問題だけ部分点が豊富なのも面白い。ここで差をつけるつもりだったのだろうか？

C : Show

この問題は、終わった後に ytqm3 から聞いた解法は面白かった。(面白いので詳細は書かないが cf blog の discussion にも載っています)

ただ制約がゆるすぎて、ジャッジが hack できなさそうな雑な乱択を書けばなんでも満点がもらえる。疑心暗鬼になりながら書いて満点。90 分くらい。(この問題に使ったのは 40 分くらい)

B : Train

得意分野 + 好きな問題だが満点を取れず残念。

10 点までは雑に考えるとわかるのですぐに書いた。30 点は実装が面倒だがあまり変わらない。

5 点の解法は頂点ごとに並列にコストが Monge の DP をする形となっており、コストは rectangle sum の形で表される。並列に Larsch を進めると O(N \log ^{2} N) で解けることがわかった。この時点で残り 150 分ほどあった。 N = 100000 で Larsch + 2d segtree の TL 1 sec が間に合う気がせず、この解法を保留にしたまま改善を考えていた。

CHT + 平方分割で O(N \sqrt N) や、コストにもう少し良い性質を見つけることを目標に色々考えていたが、特に進展はなかった。(前者は sqrt log 止まりだった)

残り 1 時間くらいになってそろそろまずいと思い、 30 点確保を始めた。これは結構実装に時間がかかった。

終わった後に shiomusubi496 と話していると、自分が wavelet matrix をすっかり忘れていたことがわかった。この問題は WM で十分で、これを忘れていなければ O(N \log N) 解法だったので迷わず書けたし多分速度も大丈夫。悲しい。

cf blog を見ていると実はだいぶゆるい計算量でも通ったようで、勘弁してくれとなった。

その他

解析モードで自分の提出を見ることができない。終了間際に提出した人は自分の点数すらわからないと聞いた。アピールの連絡も、 3 日後くらいに突然きて 12 時間すこしで締め切りだった。QOJ は CMS よりも操作しやすかったが、これは残念だった。

総評

100-40-100 だった。まだ点数を知らない人も多いが、これより上は事実上 300 しかあり得なさそうで代表落ちはなさそう。

正直満点を取れたセットではあったと思う。210 点を取った時点で考えることに重点を置きすぎていたのかもしれない。また、春合宿での反省から戦略をしっかり立てていたが、正直 2 問が簡単すぎて実運転をできた感覚はなかった。

追記

Gold Medal 取れました。

JOI 2023/2024 春合宿 参加記

そろそろ傷が癒えてきたので書きます。(5/27)

あまり詳細を覚えていないのは勘弁してください。

1 日目

0-0-9

最後の 270 分くらい得点が変わらなかった気がする。

Fish 3

最初に見て、確か 30 分くらい考えて満点解法らしきものがわかった。これは実装の重さの点でハズれ方針で、同じ方針を引いた 2 人の橙が揃って爆死していた。終わって解説を見て 1 ヶ月後くらいに解き直しても 2 時間以上かかったので勝ち目はなかったのだと思う。

Spy 3

12 問の中で 1 番好き。3, 40 分くらい考えたかな？Virtual Tree を送る方針で 90 点くらいまでの解法は思いついた。実装終わってから 1 時間くらいデバッグしたが 0 点だった。

Ski 2

最初の方に自明を取った。9 点

2 日目

36-0-30

Board Game

12 問の中で 2 番目くらいに好き。36 点。食堂で満点が浮かんであと一歩だったので悔しかった。時間を結構使ったが、結果は微妙だが悪い選択ではなかったと思う。

Tricolor

何をすればこういう問題が解けるようになるんですか？0 点。

Vegetables 5

自明の 30 点。これは戦略をちゃんと練っていれば log を外す作業の時間を取れたかもしれない。

3 日目

49-36-5

Card Collection

想定解法は天才。手詰まりになった時間に適当な嘘解法を投げて、ついでに DP の遷移をサボる (kaage 法 ??) テクをしたら 49 点まで通った。

JOI Tour

52 まではちまちま各小課題を解けば取れる。16 点思い浮かばなかったのはよくなかった。

Open Contest ではめちゃめちゃ満点が出ていたが、これライブラリなしでも中国勢は大量満点だしてくるものなのだろうか？

Tower

苦手。43 点くらいまで解けたと思っているが通らず 5 点。満点が割と多いの本当に意味がわからない。

4 日目

0-72-9

Escape Route 2

自明以外が思い浮かばず代表は諦めムードだったので書かなかったが、満点解法を聞いたらかなり反省した。そりゃ 7 人 90 点以上取るわ。。。

Island

ちまちま改善していくと 72 は取れたしそこからは取れなかった。fact493 が一瞬で解けたらしくてすごいと思った。解法を聞いたら確かにそのアイデアを試していないのはよくないなあとなった。

Table Tennis

山登りでそこそこの点を取る人 (数人) 、賢い解法を出す人 (妥当な 2 人) がいたが自分は山登りのアイデアは思い浮かばず自明部分点しか取っていなかった。そもそもこれ嘘解法に 1.5h くらい引っかかっていた。

まとめ

4 日合計 18 位、得点としては 246 点。代表ボーダーの 0.4 倍くらい。周りからも色々驚かれたが自分が一番驚いたし本当にメンタルがぐちゃぐちゃになっていた。

振り返ってみると戦略が雑で自分の力を過信していたので、 OI 5h の戦略をちゃんと考え直した。問題も全体的に相性が悪かったような気がする。来年こそリベンジしたいと思う。

終わった後先輩方から激励とアドバイスを頂きました、本当に助かりました。ありがとうございます。

JOI 本選 2023/2024 参加記


前座

二次予選

最終問題だけ見れば易化だが全体的に難しかったと思う。ボーダーは思っていたより高くて、確か 225 くらいを予想していたが 240 もあった。そして体感難易度以上に多くの人が満点を取っていたので危機感を抱いた。この最終問題は 12 人に解かれる問題ではないと思う。。。

一日目

自己紹介動画は 5 秒程度という制限があった。ほとんど何もできないと思う。二次予選の得点 / 50 秒自己紹介できるというのはどうだろうか😀 結局いつものかえるのぬいぐるみを登場させた。秀逸な 5 秒芸がたくさんあってよかった。去年やったずんだもんが今年は二人いたので、使い回さなくてよかったと安堵した。

交流会は、暗号化された問題文を解読して問題を解くというものだった。うちのチームは弊校 3 人と Yukkku さんだったので、あまり新しい人と交流をした感じはしなかったが、内容はとても面白かった。準備ありがとうございます！

チームメイトの暗号解読が強かった上にプログラミングパートは軽かったので、あまり貢献できなかった。直前にチームメイトが最終問題を解読していてお見事だった。なんと 3 人チームが優勝するという結末でびっくりした。

欲を言うと昔みたいな宿泊形式で競技してみたいと思う。昔は JOI も SuperCon も宿泊のオンサイトだったけれど、今は東京住みだと IOI まで行かないとそういうものがないので、その点では上の人が羨ましい。

二日目

昔と違って、午後開始という都合上寝坊のしようがない。

開始直前にコードテストの調子が悪くなっていたようなので、かわいそうだと思った。内心でガッツポーズをした。

戦略

落ちはしないだろう、本当にまずかったらそのとき考えようということで、賞の可能性の最大化の気持ちでやった。D までの (ほぼ) 満点が最低条件だということで、結局順番に解く以上の戦略ではなかった。E の部分点は先に考察し切ってから一気に取るつもりだった。

A 問題

例年より簡単だったと思う。見たら方針がわかったので、少し心配になって正当性を確認しながら実装した。結局 AC だった。

経過時間 : 0:04:17

B 問題

こちらも例年より簡単だと感じた。とりあえず両側から最短経路を求めて、そこからどうしようかと考えたが特に突飛な考察もなく解けた。強いて言えば N(N-1)/2 の計算をうっかり int でやりかけたのでヒヤッとした。実際これで大変なことになった人がいたらしい。

経過時間 : 0:14:22

C 問題

いきなり難しくなった。最初に思ったこととしては、

  • $T < 500000$ という制約が怪しい。判定問題を解くというのも珍しい。
  • 外側のボールから優先して取るとよさそう。

折返しを 3 回しかしないという嘘の貪欲法を思いついたが、流石に違うと思って反例を考えた。すると、ゴール付近にたくさんボールが集まっている場合などが怪しいことがわかった。$O(N^{2})$ の区間 DP が正当だとわかったので、最後の小課題では結局二乗を落とさないといけないんだよなあと思いつつ実装をした。

実装しながら、座標圧縮したあとも $L$ が十分に大きかったらまずそうだということがわかり、本質的には解法がわかった。

DP をしたあとの結果の集計の高速化をサボったものを提出したが、 62 点しか入らなかった。経過時間 : 1:09:17

本質的な改善をした。最後の小課題で WA が出て 84 点。直して満点。経過時間 : 1:27:05

正直かなり難しくて時間もかかったので焦った。

D 問題

こんな問題がクエリで高速に解けるわけないだろ！というのが初見の感想。$Q \leq 10$ に 50 点の配点がつけられているのでそれを考えた。

マッチングくらいしか考察の道具がなかったので Hall の定理を適用したら、本質的な考察が生まれた。とりあえず実装をして 50 点。経過時間 : 1:45:20

この条件を素直に扱っても難しいと思ったので、いわゆる逆の視点から見るみたいな ? 考察をしたら、これがうまくいきそうだった。log 1 つなのでそのまま満点が取れた。segtree, 平面走査、全て自力実装をしていなくて、春合宿ならあと 20 分はかかっていた。経過時間 : 2:17:04

私は C よりこちらが楽だった。人によるらしい。去年もそうだったのでそういうジンクスを疑う。

E 問題

こんな問題がクエリで高速に解けるわけないだろ！枠の二つ目だった。この時点でとりあえず春合宿落ちはしなさそうだったので、メンタル的にはのびのびと考えられた。

ネチネチ考えていくと、 $T_k = 2, C_i = 1$ かつ愚直が許される前半の 16 点は案外簡単なことがわかった。$T_k = 2$ を取り除いた小課題があったので、そこまで一気に取りたいと思った。解説に書かれている条件はとてもきれいだが、そこまできれいではない条件しか思い浮かばず、ひたすら連結成分の情報を保持するコードを書いた。31 点取れた。経過時間 : 3:06:59

$C_i \neq 1$ は検討がつかなかったが、 431 点は割といそうなのでもう少し点は取りたいと思った。残り 40 分くらいの段階で覚悟を決めて、 $C_i=1$ までの小課題 4, 5 を取る 48 点を目標にした。どちらもダブリングで解けそうなので実装を始めたが、先程の考察が不完全だったので持つべき情報がひどいことになってしまった。

残り 30 分段階くらいで、とりあえず一般の実装を諦めて $T_k=2$ の方、小課題 4 を取ろうということにした。こちらは通って 42 点。経過時間 : 3:53:24

結局一般の場合の実装は終わらなかった。最終結果は 100-100-100-100-42 の 442 点。

コンテスト後

D までどれくらいの人が解いてくるのか分からなかったので不安だったが、結局ここまで満点を取った人はほとんど居なかった。多くの人が誤読と制約の読み落としに引っかかっていたので、そういう幸運も大きいと思う。

公式 discord サーバの得点自己申告では全員に勝っていたのでこれはあるか ? と思っていたが、 Forested 様がなんの言及もしないので嫌な予感がしていた。E の解説スライドの得点分布に 48 点がいたので、全てを察した。Forested orz.

Open Contest では rainboy が満点を取っていてびっくりした。解くの速すぎる。errorgorn が 448 だったのでやはりそこからは茨の道で、 rainboy がおかしいだけだと信じたい。

結局銀賞だった。JOI の本選でメダルを取れたのは初。金銀銅が全員うちの学校だった。快挙というかなんというか...。抜ける人と残る人的に、来年も Paken で金銀銅が十分有り得そう。

感想としては、もちろん反省点がないということはないがコンテストはそういうものなので、全ての問題で大きなミスなくよい結果を取れたことを喜びたいと思う。望外の順位ではあったがその分あと一歩の悔しさもある。来年は金賞を取りたい。

抱負

春合宿も同じ調子でいけることを祈ります。色々忙しいんですが、最善を出せるように精進します。

今年もとても楽しかったです。事務局の方々、チューターの方々、ありがとうございました。

Monge / anti-Monge な行列と CHT / Li Chao Tree の関係

導入

N \times M 行列 A が Monge であるとは、以下の条件が成り立つことをいう。

  • 1 \leq i_1 \lt i_2 \leq N 及び 1 \leq j_1 \lt j_2 \leq M を満たす全ての整数の組 (i_1, i_2, j_1, j_2) について、 A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_1, j_2} + A_{i_2, j_1} が成り立つ。

また、 A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_1, j_2} + A_{i_2, j_1} \leftrightarrow A_{i_2, j_2} - A_{i_1, j_2} \leq A_{i_2, j_1} - A_{i_1, j_1} なので、 A_{i_2, j_2} \geq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \geq A_{i_1, j_1} である。

N \times M 行列 A が anti-Monge であるとは、以下の条件が成り立つことをいう。

  • 1 \leq i_1 \lt i_2 \leq N 及び 1 \leq j_1 \lt j_2 \leq M を満たす全ての整数の組 (i_1, i_2, j_1, j_2) について、 A_{i_1, j_1} + A_{i_2, j_2} \geq A_{i_1, j_2} + A_{i_2, j_1} が成り立つ。

また同じように、 A_{i_1, j_1} + A_{i_2, j_2} \geq A_{i_1, j_2} + A_{i_2, j_1} \leftrightarrow A_{i_2, j_2} - A_{i_1, j_2} \geq A_{i_2, j_1} - A_{i_1, j_1} なので、 A_{i_2, j_2} \leq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \leq A_{i_1, j_1} である。

アルゴリズム

Monge でも anti-Monge でも本質的には変わらないので、なんとなく後者について説明します。

A_{i_2, j_2} \leq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \leq A_{i_1, j_1} \ (i_1 \lt i_2 \land j_1 \lt j_2) より、全ての整数の組 i_1, i_2 \ (1 \leq i_1 \lt i_2 \leq N) について、 A_{i_2, k + 1} \gt A_{i_1, k + 1} かつ A_{i_2, k} \leq A_{i_1, k} を満たす k \ (1 \leq k \lt M) が高々 1 つ存在します。存在しない場合は k = M とすると、 1 \leq x \leq k について A_{i_2, x} \gt A_{i_1, x} を満たし、 k \lt x \leq M について A_{i_2, x} \leq A_{i_1, x} を満たします。

Li Chao Tree

A_{i, j} = f_i(j) とおくと、先程の式は以下のようになります。

  • 1 \leq x \leq k について f_{i_2}(k) \gt f_{i_1}(k) を満たし、 k \lt x \leq M について f_{i_2}(k) \leq f_{i_1}(k) を満たす

任意のペアについてこのような k が存在するような関数群には Li Chao Tree が使えます。証明を求められるとどう書けばいいのか困るのですが (できると思う) 、ここに書いてあるということで許してください。

codeforces.com

DAG の dp で使う場合

下三角行列なので定義域が怪しい感じになるのですが、結局 (最小値 / 最大値) クエリは定義域の中にしか飛ばさないので、適切な値で埋めれば大丈夫です。

嬉しい場合

  • オンライン dp において Monge の最大値 / anti-Monge の最小値を求めるのには LARSCH が使えなくて、その場合オンライン - オフライン変換 + SMAWK よりも定数倍が速いと思う。
  • SMAWK の書き方を忘れてしまったとき。
  • Monge な行列の列がランダムな順番で追加されるので (!?!?!?!?) min / max を求めたいとき。
  • 変なタイミングで謎の位置での最小値を求めたいとき。これは辺の重み関数が Monge かつ別のいい感じの、例えば極値が高々 1 つみたいな性質を持っている (DAG ではない) 一般の完全グラフの最短経路を求めるときに使える場合があると思っている。

Convex Hull Trick のアイデアの適用

なんだか上で満足してしまったような気分ですが、一応。

No.1867 Partitions and Inversions - yukicoder の解説はこれの特殊ケースです。

Li Chao Tree と同じく、 Monge / anti-Monge の場合ではほとんど Convex Hull Trick のロジックがそのまま使えるのですが、いくつか問題点があります。

連続する 3 つの関数のうち中央がいらない場合の判定

一次関数だとこれは定数時間でできるのですが、一般に Monge / anti-Monge となると困ります。二分探索をすればなんとかなります。なので、いわゆる「追加と質問がどちらも単調な場合」にもならし定数時間にはならない、と思っています。(特に anti-Monge でなったら LARSCH と同じ線形時間が達成できることになって、そんなことはなさそう)

追加クエリが (元の CHT でいう) 単調でない場合

こんな場合ある ??? という気持ちですが......。

CHT の場合、傾きで二分探索をして挿入するべき位置を特定していました。一般に Monge だと困ります。

N \times M 行列 A が Monge であり、その i_1, i_2 行目の任意の要素にアクセスできるので、 i_1, i_2 の大小を比較したい、という問題を考えます。これは、 i_1, i_2 行目かつ 1, M列目である A_{i_1, 1},A_{i_1, M},A_{i_2, 1},A_{i_2, M} にアクセスできればよいです。この 4 要素からなる部分行列が Monge かつ anti-Monge である場合は決定できないのですが、その場合決定しないでも問題ないです。

これで比較ができるようになったので、結局 std::map などで二分探索を用いることができます。

うれしい場合

  • 書きやすい ?
  • 条件によっては定数倍がいい気がする。