(Yi<K かつ Yj≥K) ならば i<j が成り立つ」という型の命題は、前提が成り立たないときは常に真だよね、誰か質問しないかなと考えていた。そのうちに問題文を何回目かに読み返していたときに気がついたんだけど、累積和の初項が必ず０だから、その時点で K 以上の値が出現してしまっている場合があるのだね。K が０以下の場合とそれ以外で場合分け。ここではあっさり書いたけど、境界値が 0 なのか -1 なのか 1 なのかでもじっくり考え込んでしまった。基本的には Yes でソート列が答えになる。判断が分かれるときは正の和と負の和の絶対値の差と K を比較する。ここでも不等号にイコールが付くかどうかをじっくり考えてしまった。なんなら最初に戻って場合分けの条件から考え直している。これが自分の脳みそに収まるぎりぎりのサイズの問題です。■B 問題「Between B and B」。ある文字が要求されているいないの状態が 1<<M あって、これを N 文字分繰り返す DP をするのだと思った。実は最後の文字が何であったかを区別しようとしていて、そうすると１億ステップの処理になって TLE なのではないかと思ったけど、区別しないなら 1000 万なので間に合いそう。どちらにしろ数字合わせができなくて TLE かどうか以前の問題だった。■C 問題「Beware of Overflow」。個別の値の絶対値が R 以下ですよ、値の合計の絶対値も R 以下ですよ、二項間の比較と加算を駆使してどの瞬間どの値も絶対値が R を超えないようにうまい順番で全体を１つの値にまとめましょうね、という問題。最初はソートしてから先頭と末尾の加算を繰り返せばいいかと思った。ソート列を真ん中で折り返して加算するので、１回のイテレーションで全長がおよそ半分になる。だいたい答えは合っていたけど、３ケースだけ WA だった(#54171399)。どういうケースで良くないかというと、
-R,-R,-R,2,2,R-1,R-1,R-1 みたいな場合？ R=3 だとすると 2+2 をしてはいけない。改良版では、加算した結果を二分探索で適切な位置に挿入することで常にソート済みの状態を保ちながら、最大値と最小値の加算を繰り返すことにした。提出 #54175146 (AC / 442 Byte / 177 ms)。■水パフォで喜べないって悲しいね。わざわざ確かめないけどね。自分の想像では ARC、ABC、ABC、ARC と下げが続いている。■■■D 問題「Portable Gate」。Ruby で挑戦している人がいたのでまずは問題を読んでみた。全方位木 DP？ ゲートを置く場合と置かない場合のコストを積み上げていくのかと思って実装を始めたけど、どうもそれではいけない。始点に帰ってくる必要がないのだ。最後に選んだ辺へは行きっぱなしでいい。そうすると、ゲートを置かずに帰還する場合のコスト、ゲートを置いて帰還する場合のコスト、帰還しない場合のコスト(※ゲートを置く置かないは呼び出し元に影響しないので置けばよい)の３つを考える必要があるのかなと考えたところでギブアップ。知力を振り絞るためには頭の良さだけではダメで外国で冬の海に飛び込めるくらいの体力が必要らしいですよ(もちろんそんな体力もエネルギーもないのでさっさと投げ出しちゃいます)。■通った！！！ 提出 #54283484 (AC / 1521 Byte / 1758 ms)。びっくりマークを３つ付けてもいいでしょう。たいへんだった。寝る前に数時間がかりで慎重にコーディングをしたら、ちょっとしたシンタックスエラーを２つ直しただけでサンプルが通って、あとのミスは親方向の深さを計算するときに +1 するのを忘れていたことだけだった(37 行目と 50 行目。子供から見て兄弟は最も近くに見えて２親等だという話)。結局考えるべきは先に挙げた３つに加えて、(ゲートを使わないで)帰還する場合と帰還しない場合の差分として最も遠い子孫との距離を記録した。この問題ならではのフックがありました。全方位木 DP の手順として、全体から子を引いてそれを親方向のパラメータとして子に与える必要があるんだけど、パラメータの計算に最大値(最小値)を使っている部分がある。つまり、複数の子があるときに、１つの子については帰還する必要がないけど、他の子についてはすべてを黒に塗ったあとで戻ってくる必要があって、その選択に最大値(最小値)を使っているんだけど、子の影響を全体から差し引くときに最大値(最小値)が利用できなくなる場合がある(その子がまさしく最大値(最小値)だった場合)。こういうときのトップ２戦略は過去２回の経験がある(20240302)。どうですかね、もっとシンプルに解ける考え方があるんですかね。選び方次第でパラメータが減らせる可能性はあるかな。全方位木 DP というだけでたいへんなのに、それに輪をかけてたいへんだった。パラメータが４つあってそのうち２つでトップ２戦略を使った。最後に補足。ゲートを使う使わないを辺ごとに独立に選んでいい理由は、ゲートを使わずに網羅して帰還する辺を、ゲートを使って網羅して帰還する辺より先に選んだことにすればいいから(そして最後が帰還しない辺)。■■■B 問題。提出 #54413597 (AC / 433 Byte / 1544 ms)。すでに散々悩んだあとで頭の中が整理されていたからか、フツーに普通の DP だった。日記に「ある文字が要求されているいないの状態が 1<<M あって、これを N 文字分繰り返す DP をするのだと思った」と書いたことは忘れていて、ブロックされている文字にビットを立てる DP をした。それで良かったけれど時間が厳しい。３重ループになるのだけど、N のループの中で 1<<M のループの中で M のループを回すとコードテストで 10 秒弱かかった。制限は特に長めでもない２秒。ここで ABC356-D Masked Popcount の解法のひとつ、ビットごとに 0 と 1 の出現サイクルを利用するものを思い出した。ビットごとに 0 または 1 だとわかっている数についてだけループを回すなら、３重ループの最奧でビットが立っているかどうかの判定をしなくて済むし、ループの回数も半分になる。そのためにはループの順番を変えて、N のループの中で M のループの中で 1<<M のループを回す。遷移はビット演算が２つ。ある文字を置いた結果その文字自身をブロックし、そののちいくつかの文字のブロックを解除する。■同じく B 問題。提出 #54414039 (AC / 796 Byte / 1628 ms)。Ruby による B 問題へのすべての提出を見ると Akiyah さんが 2047 ms で AC まで一番近づいていた>#54319004。お楽しみを奪ってしまったとしたら申し訳ないのだけど、速くなりそうな部分があったのでそこを修正したものが冒頭の提出。具体的には ns.sum{|n| dp[n] } を dp.values_at(*ns).sum に変更したら 20 % くらい速くなって AC になった。インタープリタ型の言語は、できるだけ短い指示で多くの仕事をコンパイル済みのネイティブコードにやってもらうのが良い。ちなみに TLE を避ける工夫は自分のものとは異なっていて、1<<M 通りの遷移先をビット演算で N×M 回求める代わりに前計算をして、遷移先ごとに遷移元の集合を用意している。それがさっき出てきた ns。そういう準備があったからこそ dp.values_at(*ns).sum という効率的な遷移を書くことができた。遷移を１行で済ませることができていた。■■■D 問題。解説を読むと、読むのもたいへんなので８割読み飛ばしちゃうんだけど、移動コストの上限は 2(N-1) で固定だから、ゲートを使って帰還コストをどれだけ節約できるかだよと書いてある……ような気がする。提出 #54485687 (AC / 989 Byte / 1765 ms)。パラメータが１つ減って３つになった。解説の最後にリストされている３項目に３つのパラメータを対応付けるなら、順番に R、G+L、G になるのではないかな。最後が一致しているのでヨシ！