(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 になるのではないかな。最後が一致しているのでヨシ！与えられるテスト結果が誤っており上記の条件を満たす組み合わせが存在しない場合もあります。その場合は 0 通りと解答してください」の意味がよくわからなかった。信頼できない入力が混じっていて、それを見抜いて何らかの対処が求められているのかと思った。実際は単純に矛盾するテストによって答えが０通りの場合があるよということを言っているだけだった。たしかに、複数のテストを照合した結果矛盾が生じて答えが存在しない場合、じゃあ、個々のテストにおいて「開いた(開くはずがない)」「開かなかった(開かないはずがない)」という結果をどう扱えばいいかという疑問が生じる。それは誤りであるという断り書きだった。■D 問題「Masked Popcount」。かつてよく見られた数え上げ問題。苦手だよ。でも精進によってなんとなくの型みたいなものは持っている。上限が N で与えられてるのがやっかいなんだよね。たとえば N=2**60 ならこれは主客転倒で寄与を簡単に数えられる。じゃあどのようにしてそういう状況を作るかというと、与えられた N のビットのうち、最も左にあって最初に倒されるビットを決め打つことによって N を複数の区間に分割する。N のプリフィックスと自由に {0,1} が選べるサフィックスとで構成される区間について問題を解く。たとえば N=0b10101 ならプリフィックスは１のビットの数と同じ次の３つ(0b10100、0b100xx、0b0xxxx)。 もちろん１つもビットを倒さない場合も忘れない。■E 問題「Max/Min」。よくわからない問題。N の上限は 20 万。これは O(N) もしくは O(NlogN) が解法となるよくある制約で、N の制約としてはほぼ上限。そして A が取り得る値が 100 万以下。これは N と比較すると大きい数字だけど、処理すべき区間が 100 万以下であってそれ以上は考えなくてもいいと思うと、そんなに大きい数字には思えない不思議。結局これは調和級数の上限がどうのという問題だったんだろうか。特別な道具を使わずに配列を操作すると決めたあとでも答えを合わせるのに苦労して、結局１時間近くかけてしまった。やるべきことはひと目でわかるんですよ。すべての組み合わせについて足し合わせるに当たって、予めソートして Ai と Aj の大小関係を固定してしまえば考えるべきは分子が分母の１倍か２倍か３倍か……。時間が厳しいので(そこが問われている問題なので)同じ値はまとめて計算しますよ。そうするとどんな入力が嫌かというと、小さい数字が順番に並んでると、処理をまとめることができず、区間を大きくスキップして処理することもできないのが困るなと。だけどね、100 番目、1000 番目の値はすでに十分大きいわけです。100 万割る 100 は１万だし、100 万割る 1000 は 1000 なので、個々の処理量は無に等しい。もちろん１万が１万集まれば馬鹿にならないんだけど、全体で見ても処理可能な範囲に収まることは知っている。名前は出て来なかったけど高３の演習問題でいつの間にか不等号を証明させられていたような気がする。■F 問題「Distance Component Size Query」。解けなかった。セグメント木とか平方分割とか、うまく区間を分割して効率良く数えられないかと考えたけど、できそうでできなかった。でもできるのかなと思ってる。自分にはできないけど。K=0 と K=1、それと K がすごく大きいときでだいぶ様子が違ってくるなとも思った。でも、じゃあ K=1 の場合に限れば問題が解けるかというと、そうでもなかった。■■■D 問題。桁ごとにサイクルを考えるという解法を仕入れてきた☞。LSB から見ていくと、サイクルは２、４、８と倍々になっていく。その中身だけど、前半が０で後半が１という単純なもの。だから 0 から N までの N+1 個の数をサイクルと半端に分けて１の数を数えるのも簡単。提出 #54162917 (AC / 165 Byte / 42 ms)。この考え方だとずるいぐらいに実装が簡単だった。自分は自分の考え方で実装したとき式を間違えて１回 WA を出してるからね>提出 #54107427 (WA)。
w を足し、それまでに採用されていたが不要になった辺のコストを w+1..10 の範囲で探して引くというもの。単純明快でしょ。しかも、コスト１の辺を使うグラフ、コスト１から２の辺を使うグラフ、……という 10 種類のグラフを維持管理する処理と、辺を追加したことで不要になった辺のコストを特定する処理が一体となっているところが美しいと思うんだ。これは解答というより問題の力だとは思うけども。■■■E 問題。kotatsugame さんの動画(【競技プログラミング】ABC355【実況】)でグラフとしての見かたを知ったので、新規に実装して提出した>#53993734 (AC / 1045 Byte / 402 ms)。変数の取り違えで RE を出し、off-by-one エラーで WA を出し、デバッグ版を提出して WA を出したあとでの AC だった。やっぱり難しいね、この問題。ミスのしやすさも問題の難しさのうちだとすればね。やっていることは辺が陽に与えられないだけの BFS。グリッド問題みたいなもんだ。■C 問題。行や列をスキャンする O(N^2) 解が 455 ms (#53855978) だったところ、カウンターを使う O(T) 解が 132 ms (#53993977) だった。制約がちょっと変則的で、1≤T≤min(N^2,200000) かつ 2≤N≤2000 なので、T の上限が 20 万なのに対して N^2 の上限が 400 万。N^2 解を許容するためにあえて制約の桁を減らしていることが窺える。C 問題だしね。まんまと甘えさせてもらいました。answer += a*A.size+A.sum while a = A.shift なんだけど、２要素の和が 10^8 を超えるときは 10^8 を引かなければいけない。A 数列の順番には意味がないので、予め A 数列をソートしておいて、何個の要素が 10^8 を超えるかを効率良く数えられるようにする。二分探索なら log が付くけど間に合うし、尺取りっぽい操作をするなら log は付かない。あっ。自分の提出 #53343786 で 10**8 に付けた名前が P(rime number) というのは嘘だ。■D 問題「Another Sigma Problem」。今度は２要素を文字列として連結してから数値として評価をする。順番に意味があるので並べ替えてはいけない。右側にある要素について、数の和と、下駄の和がわかればいい。下駄というのは、３桁の数字であれば 1000、４桁の数字であれば 10000 を計上する。これを全要素について数え上げておいて、更新しながら答えの計算に利用する。■E 問題「Yet Another Sigma Problem」。かかった時間だけ見れば C 問題と同じなんだけど、配点通り CD より難しかったと思う。自分は Ruby の記述力におんぶにだっこで効率の悪い解答を書いた。まず、N 個の要素について、先頭の文字を見ます。同じ文字だったもの同士をグループにして再帰的に次の文字を見ます。その過程で、グループの大きさを見ます。大きさが Z なら、作れるペアの数(Z*(Z-1)/2)がそのまま答えに寄与します。■F 問題「Tile Distance」。わかりやすい図が付いていてたいへん助かります。K=1 は簡単。マンハッタン距離が答え。それ以外はどうしましょう。最初はフラクタル的に考えてみようとした。スタート地点とゴール地点が隣接していると見なせるまで K を定数倍してみる。で、視点をズームインしながら移動コストを足していけないかと。できなかった。次は大きいタイルと大きいタイルのあいだの移動コストを数えようとした。横方向の移動コストだけを考えてみる。K が大きいなら、上下にあって頂点で接している大きいタイルを経由することで、必ずコスト４で真右にある大きいタイルへ移動できる。K=1 のケースはさっき除外した。K=2 の場合は小さいタイルをそのまま突っ切って移動する方がコスト３なので安い。そういう計算をしているうちに、斜めの移動コストが特に安いと気がついた。K マスを１と数える大きいタイルの座標系で考えてるよ。例えば右に２、下に２の位置にある大きいタイルに移動したいとする。右に移動してから下に移動するなら、さっき計算したコストを使って 3+3 (K=2 のとき) か 4+4 (K>2 のとき) になるけど、ありがたい図を使って数えてみると、たったの４で右下の右下にある大きいタイルに移動できることがわかる。というわけで、まずは斜めに移動して、それから縦もしくは横に移動すると考えると、最適な大きいタイル間の移動コストが求められる。あとは１または４通りと、１または４通りの総当たり(1x1 または 1x4 または 4x1 または 4x4 通り)でほぼ答えが出る。１と４が何かというと、スタート地点ゴール地点から最寄りの大きいタイルの数。「ほぼ」が何かっていうと、スタートとゴールが小さいマスにあってすぐ近くにある場合。これは K=1 の場合のマンハッタン距離と同じだから、提出 #53370051 では K=1 の場合を分けるのをやめて雑に一体化した。全部混ぜ混ぜして最小値を取れば自ずと答えが出てくる。■G 問題「Merchant Takahashi」。今日の G 問題は F 問題と配点が同じ。F 問題を通してから G 問題を読んで、することがなくなったので順位表を見たら F より G の方が通されていたね。自分は G 問題がさっぱりだったけど、データ構造で一発なぐるだけの典型だと仮定して眺めてみれば、移動コストによる報酬の減殺が組み込めるなら、セグメント木が使いたい形だと思った。もちろん組み込めないのだけど。■Highest を更新したけど、明日の ARC の参加費は何レートかな。何レート吸われるんだろう。3-4-5-(略) という配点は水色の自分向けド真ん中なので出ないわけにはいかないんだよな。■■■精進。G 問題。セグメント木を２つ持つんだと２か所で読んだ。それでどうやって距離による減殺を組み込めるかを考えた。左右の端、頂点１と頂点 N にいると仮定したときの所持金のポテンシャルをセグメント木の各要素の値とすると、イーブンな条件で大小比較ができて最大値が取り出せる。提出 #53408933 (AC / 849 Byte / 1999 ms)。２秒制限で 1999 ms は神がかっている。だめだったらセグメント木にブロックを渡す代わりに max メソッドの呼び出しを直に埋め込むだけ(手動インライン展開)。■実際の値の代わりにイコール条件のポテンシャルを扱うのは ARC120-C Swaps 2 でやったことがある。20211022p01。なんでそんな名前で呼んでるのかは自分でもわからない。なんとなくふさわしいような気がしただけ。10101 で表せる。全部で５人なら、これは 1-3-5 位しか考えられないが、全部で 10 人なら 2-4-6 位もありうる。しかし全部で 10 人いて他に 101011111 というピースがあるなら、やはり 1-3-5 位しか考えられない(※ MSB を１位としました)。こうなってくるととりあえず全部を試してみるしか答えを出す方法はないよね、という気持ちになる。１階層ごとに特定の１ピースを埋める DFS をやるんだけど、DFS の呼び出し経路には関心がない。どういうことか。１階層目と２階層目が受け持つピースがどちらも 1 と 1 という形だったとする。３階層目のピースにとって関心があるのは、そして結果に影響するのは、どのビットが空いているかということだけなので、同じ２ビットのどちらとどちらを１ピース目と２ピース目が埋めているかという情報には関心がない。むしろ積極的にその区別を捨てて結果の使い回しをしたい。メモ化です。というわけで、前半ではピースの形を確定する UnionFind を、後半ではピースを N ビットに隙間なく埋めるメモ化再帰をする２段構えの問題だった。要素技術は F 問題までで身につけているはずで、組み合わさったことで F 問題だったのかなと。G 問題ではないなと。ならこれも実装問題だったのか。突破できませんでした。腕力が足りない。■他所で見かけたのでここでも書くんだけど、置きにくいピース(※)から置くような小細工を WA だった最初の提出から行っている。これをやらなくても TLE にはならないだろうけど、とにかく答えを見つければいいという DFS の場合、優先順位を付けて早期に判定ができると劇的に実行時間が縮まることがあって気持ちがいいので、とりあえずやってみて沼にはまるのがいいと思う。その先にヒューリスティック沼があるかは知らない。この問題では、再帰を深く潜ってからやっぱりだめでしたーと判定されていたかもしれないものが、比較的浅い階層で無理だと判断できるようになる効果があったと思う。※置きにくいピースを短絡的にビット長の長いものとしたけど、ポップカウントもいい指標になりそうだと気がついた。1000001 と 1111 のどちらが置きにくいかという話。自分が明確に誤っていたのは、ビット長が同じでポップカウントが異なる 110001 と 101111 の比較で、単純に数値比較で大きい方(最初の方)を置きにくいと判断したところ。小細工だしフレイバーなので許される手抜きだとは思うけど。