脳log[20250906]

2025年09月06日 (土) [AtCoder] 今日は AtCoder Regular Contest 205 (Div. 2) があった。div.2 に Rated でいつまで参加できるのか先行きが怪しいこの頃ですが、まだ Rated です。■A 問題「2x2 Erasing」。与えられた矩形の中の白４マス四角の数を素早く数えたい。右、下、右下がすべて白マスである白マスを１と数える２次元累積和で数えられそう。提出 #69078973 (AC / 640 Byte)。枠で区切られた部分の調整で無駄なことをしてる気がする。SR と SC は不要で、i1,j1 をそれぞれ -1 するだけでよかったのではないか。■B 問題「Triangle Toggle」。解けない B 問題に残り時間をすべて奪われました。時間さえかければ解けた C 問題、D 問題に着手したかった。■C 問題「No Collision Moves」。制限時間が３秒と長めなんだけど、何が難しいのかわからなくてなんの罠を見落としているのかと疑心暗鬼だった。S に基づいた人の並びと T に基づいた人の並びが異なっていれば、必ずどこかで移動の交差が起きるので答えは No。じゃあ Yes のときは端から整列させていけばいいんちゃうの？ その通りなんだけど、端の人を移動させる前にその先の人を移動させる玉突きを処理する必要があった。サンプルがその例。でもそれだけだった。提出 #69089475 (AC / 486 Byte / 550 ms)。■D 問題「Non-Ancestor Matching」。全方位ではない木 DP。どうしても残ってしまう白色頂点の数を子を頂点とする部分木ごとに数えたら、それをうまくマージして白色頂点を最小化する。提出 #69091151 (AC / 670 Byte / 1192 ms)。うまくない場合というのは、１つの子の下にペアを作れない白色が大量にぶら下がっていて、他のすべての子の下にある白色の頂点と黒色のペアを解消して用意した頂点を使い尽くしても余ってしまう場合のこと。■5×10^5 の制約はまじで良くないよ。ARC はもちろん ABC でも見たくないよ。■日曜の昼は毎週ほぼ確実に時間がとれないので明日の ABC はお休み。