脳log[20220622]

2022年06月22日 (水) [AtCoder] 精進。ABC169-E「Count Median」(水 diff)。コンテスト当日に 23 分で D まで解いていながら残り 77 分で解けなかった問題。当日と後日を合わせて 6 WA している。■提出 #32668994 (AC / 210 Byte / 316 ms)。秒で考察が終了して実装量もご覧の通り。むしろどこでどう迷っていたのかがわからない。コンテストで安定した成績を残したいなあ。■考えたこと。中央値を最大化したいとき、数列の半分を上限(B 数列)に張り付かせればいい。反対に中央値を最小化したいとき、数列の半分を下限(A 数列)に張り付かせればいい。N が奇数のときは単純に N/2+1 番目の上限と下限のあいだが中央値として可能な範囲。N が偶数の時は、N/2 番目の上限下限と N/2+1 番目の上限下限を同じように求めて、その和(下限+下限と上限+上限)が取り得る範囲を定める。■どこで迷っていたのか思い出した。各要素が取り得る範囲が Ai 以上 Bi 以下という形で制約されているので作れる中央値の範囲(上限と下限のあいだ)に抜けがあるのではないかと考えたのだった。その不安はわかる。わかるけど、問題設定の理解が足りないせいで書かれていない制約を自分で作り出していませんか、と今となっては思う。望みの中央値を作るに際してどういう操作が可能か限界がどこにあるかよくよく具体的に考えてみれば。