チーム編成

• simasima : 考察・東方担当
• noya2 : 東方以外のすべてを担当
• ponjuice : くねくねしながら実装を担当

結果

全体 5 位（現役内 3 位・科学大内 1 位）でした！

開始前

会場が使えない & 印刷ができない !

A noya2

sort(all(a)); out(a[1]);

AC (0:02)

B Ponjuice

すべて同じ文字列じゃなければ作れるなとか二つ異なる文字列作ったらいいかなぁとか考えている隙に、ソートとリバースすればいいよと横で一緒に問題を見ている simasima に言われる。そのまま実装してAC (0:04)

C noya2

simasima の担当だが、考察もなにもないので noya2 が実装する。

xを含めていいと勘違いしていて（え？）変な実装をしたが、修正できた気になり提出、WA（おわった）

答えが 0 のケースで 1 を出力していた。頭がまわっていないことが判明したので、x で文字列を分割する方針に切り替えて、実家のような安心感を取り戻し AC (0:14 +1)

D Ponjuice

立方体の向きを全探索するやつ
simasima に普通に全探索をすると $O(24^n)$ になるが、毎回ちゃんと範囲が被ってないかチェックすると $O(3^n)$ になるよと言われる。手元に問題文が存在しないため、何を求めるのかを確認していなかったので、全て使えるかどうかの YesNo 判定と考えていたが、実装前に読むと、積むことのできる最大段数だったので、$n!$ 回の探索をするコードを書く
rotate関数の使い方を覚えていなかったのでうろ覚えで書いたらエラーを出してしまった
このエラーを探すのにちょっと時間をかけてしまい反省だがなんとかAC (0:46)

E simasima & noya2

制約を$10^{18}$と勘違いしていた。$2$の倍数で特定するのは$2^{33}$までしか特定できない。$3,5$ を使って、CRTで同時に特定して、CRTで復元すると$2^{33}\times 3^{12}\times 5^4>10^{18}$ で出来るのでnoya2に渡す。

並列でやる部分を実装に反映させるときの制御が難しいがまあできることが分かる。そこそこ実装をしていると、ふと $a,b\le 10^9$ であることに気づく。これなら $\mathrm{mod}{2}^k$ のみ特定する方針でよく、3 並列が 1 並列になった。これまでの実装の半分くらいが無駄になったが、実装自体は難しくない。3 並列用に書いておいた部分が壊れていてデバッグが必要になったが、F をやってもらっている間にいろいろ改善して AC (1:16)

F simasima

区間DPっぽいので区間DPで考察するも、$O(N^3)$から落ちない。素直に前からDPしようとすると、後ろにCPCPCPCをどれだけ付ければ良いかだけ持てば良いことが分かる。実装はめっちゃ簡単だったので自分でやった。(1:06)

G Ponjuice

半分全探索がみえるが、Binary trie が必要そうに見え、ちょっと面倒そうに見えるので、noya2 にライブラリをもらう。
最初、$K<10^6$ と勘違いをしていたため、答えを求める部分で $\tilde{O}(K)$ time の解法を書き 1ペナ。(バカ)
誤読に気づき、二分探索で log 二つの解法を書くがTLE が出てしまう。
ちゃんと丁寧に log を一つに落とすことで、AC (2:45)

H simasima & noya2

頂点ごとに $0,1$ が付けられていると誤読。列でも解けない。誤読に気付いた後はすぐ解けた。石の個数が$0,1$ に帰着できるのは自明。$0$ の場合は石の数の偶奇、$1$ の場合は連結成分の偶奇が一定なので石の数-連結成分の個数の偶奇で決まる。ここまで来たらあとはアルゴなのでnoya2に渡す。

ある頂点の隣接頂点の値の総和が分かればよい。何も考えずに bfs order 順に並べて区間クエリに言い換えてしまった。終わったあとに子の総和を管理することにすると、更新は親を書き換えるだけで良いので定数時間で更新できると気づく。もったいない。実装は実家なのですぐ終わりすぐ通ってよかった (2:06)

I simasima & noya2 (not AC)

逆から見た方が見通しが良さそうで、貪欲にロボットを取れば正当そう。最初は確信を持っていなかったが、noya2が実装している間に証明できた。あとはアルゴっぽいのでnoya2にお任せ。

全部ができる専用の beats! （LC の問題）を持っているので貼る、すると勘違いしていることが判明。beats! で処理できはするが、beats! 自体を持っているわけではないので、頭を抱えてしまう。lazy_segtree に 1 行追加するだけでできるはずだが、覚えていない（はぁ）。雑な理解をもとに雑に追加して、なんちゃって beats! を作る。重要なのは mapping で、適用できる場合は適用する、ということが必要である。今回は clamp があるが、clamp しなくても変わらないときはそのまま適用してしまえる。また、1 要素にも自明に適用できる。これを全部正しく書くのに時間を消費してしまい、時間切れ。最後まで正しい beats! の書き方が分からなかった。

コンテスト終了後、まず正しい beats! を窃盗し、投げる。TLE らしい。ふと、mapping が失敗しないケースとして、全部外側にあるケース（区間 max が clamp の左端以下である場合）も諦めずに適用できること（そして、それがないと計算量が壊れること）を思い出す。区間 max も持つことにして実装を少し改善するだけで、今度は AC になった。自分が悪いです。

おわり

noya2 : 誤読指摘・実装失敗担当になった。H をまともな速度で書いたのだけ偉い。最後 I が通っていても ucchan_nanchan_honoono_challenger_korega_dekitara_100man_yen_super_denryu_irairabou_and_sounansya_and_seekworser を抜かしていただけで、順位にほとんど結果がないのだけが救い（だからと言って...）

Ponjuice : いろいろと変なミスが目立った回だった。誤読しまくりでヤバい！！
今回は実装担当的な感じでほとんど考察をしていないが、本番はちゃんと考察でも貢献できるように頑張ります。

simasima : 誤読・考察担当になった。FHを解いたので最低限の仕事はしたと思う。

😱😱😱問題文がない&印刷デバッグができないのが悪い😱😱😱