Array#count■B 問題「Minimize Abs 1」。問題文が難しすぎる。数分かけてじっくり根気よく投げ出しそうになる気持ちを抑えながら理解する必要があった。要するに、ある範囲(L-R)に含まれる整数のうち最も A[i] に近い数を、A[1] から A[N] について答えよ、という問題だった。ループと配列はいらなかった。繰り返しなしでも十分に B 問題だったのに、ループがさらにややこしくしていた。答えの候補は {L,R,A[i]} に限られるんだけど、謎に {L,R,A[i]-1,A[i]+1} を候補にしてペナルティ５分。根気が尽きていた。■C 問題「Minimize Abs 2」。平方数を２つ足してある数 D にどれだけ近づけられますかという問題。図形的な意味があるかは知らない。大きくなりすぎない範囲の平方数を列挙して調べた。■D 問題「Counting Ls」。ちょっと方針に迷った。グリッドをスキャンしながら２種類の累積和を更新しつつ数えていけるかと思ったけど、欲しい数が足りていないことに気がついて頓挫した。正解方針はこう。最初にある行またはある列にある o の数を数えておく。その後もういちどグリッドをスキャンして、ある点が L 字の角にあたる場合の数を数えて足し合わせて答えにする。ところで、@kyopro_friends さんは頓挫せずに解ききってしまったようですよ。「フェネック「アライさんは最初このことに気づかずに、L字を置く向きを4通り試す実装をしてるんだけどねー」 アライグマ「そのことは秘密なのだ！」」■E 問題「Mex and Update」。デバッグ時間が１分14秒足りなかったせいでこれは精進です。こいつ先々週も似たようなこと言ってたな(「なんてことのない F 問題を通すのに２分６秒ぽっち足りなかったのがくやしい」)。セグメント木を使って該当する数のうち最も小さいものを探す。値の上限が 10^9 だということで座圧したのだけど、そのせいでバグらせたケースが 3 1／0 2／1 0 みたいなの。クエリでは数列を書き換えていないので {0,2} の MEX である１が答えなのだけど、座圧しているせいで１番小さい値(0)と２番目に小さい値(2)のあいだに隙間があることに気付けなかった。+1 した値を加えておおよそ２倍の数の数字を扱うことで AC になったのだけど、バグの原因を見つけるのに手間取って時間が過ぎてしまっていた。Ruby での他の提出より倍くらい遅いみたいだから、もう少しスマートな解決法があるかも。■F 問題「Minimize Bounding Square」。終了後に問題を読んで、根を詰めずに休み休み考えてだいたい１時間とちょっとで AC になった。時間内に解けた可能性はゼロなので悔しさはなく解けた喜びだけがある。まず X 座標と Y 座標に問題を分ける。X 座標(Y 座標)の幅をどれだけ狭められるかは左からの累積和と右からの累積和でわかる。Sandwiches (20230902) と同じ要領で、座標の和と個数から操作回数が求まる。ところで、全部でいくつ狭めるかが決まっているときに、右からいくつ狭めるかと左からいくつ狭めるかは貪欲にステップを刻んで決めることができない。１狭めるだけなら左から狭めた方が得なケースでも、３狭めるときにはすべて右から狭めた方が良くなるケースというものが考えられる(※)。N≦20万なので答えを二分探索する中で線形時間のスキャンをしても大丈夫。２秒を 67 ms 超えたけど(#47948117)、制限時間が３秒だったのでセーフ。■Twitter の成れの果ての何かを眺めているとギリギリで E が通っていても緑パフォだったらしいとわかる。じゃあなんにも惜しくねーな。そのラインは伸るか反るかの最前線よりずっと下だ。■F 問題についてすごいツイートを見かけた。「FのC++の最短コードを見てる atcoder.jp/contests/abc33… X/Y座標を長さLの中に包含させる最小の操作回数は外側から順にペアを作ったときに max(ペアの長さ-L,0)の総和になる ってことだと思うけど頭いい」。なんでそれが答えになるのか全然わかんない。■※ 嘘を書いていたっぽい。貪欲に狭めて良い……らしい。「アライグマ「いま左右の端にある点のうち少ない方を全部1個となりに詰めるのが最適なのだ。ということは答えの関数は、こういう感じの折れ線になるのだ。元の2次元の問題なら、x方向とy方向で解いて足せばいいのだ！」」。考慮してその結論が間違ってるなら何を頼りにして答えが導き出せるというのだ。■■■E 問題。座圧したときの値の抜けは落とし穴というよりも答えへのショートカットだ。A 数列に存在せずクエリで設定されることもない値は常に MEX として選ばれる可能性がある。そういう値の最小値が答えの上限になる。問題に対する総合的な理解が足りていないから見落としてバグらせる。提出 #47966425 (AC / 1211 Byte / 642 ms)。BIT で MEX 候補の上限までを座圧なしで管理したら 1973 ms だったのが 642 ms まで早くなった。■F 問題。ゴルファーの理解できない解法はさておき貪欲に四辺を内へ寄せる解法を実装してみた。提出 #47975884 (AC / 976 Byte / 642 ms)。2067 ms だったのが 642 ms まで縮んだ。クラスを使ってコードの重複をできる限り省いたつもりだけど、それでもかなーり面倒くさい実装になっている。