脳log[20211013]

2021年10月13日 (水) [AtCoder] 精進。ARC089-D「Checker」(青 diff)。大きさが 2K×2K で黒白２マスずつの最小市松模様に 2N 個の点をプロットしておいて、K×K の枠内に最大でいくつの点が含まれるかを二次元累積和で求めるのだと思った。概ね正しかったのだけど、二次元累積和のサイズは 2K×2K ではなくて 4K×4K が必要らしかった。わからないが言われたように修正してみる。提出 #26544471 (TLE×8)。定数倍がたいへん厳しい。提出 #26544665 (AC / 956 ms)。元データが 2K×2K なのだから愚直にデータを展開せずとも計算で仮想的に 4K×4K を存在させられる。ところでこの人の提出>#2789430。すごく短いのと、累積和のサイズが 2K×2K だ。c と N-c を同時に答えの候補にしている部分がよくわからない。わからなくはないか。黒く塗るか白く塗るかだ。そうすると 4K×4K が必要というのも、K×K の枠内が■□■□になる場合と□■□■になる場合を網羅するためだったか。じゃあ 3K×3K でも？ そもそもさっきの仮想累積和の提出(#26544665)が、3K×3K の累積和上を K×K の枠が移動する 2K×2K 通りの探索になってたっぽい。わかってやってるんじゃあないんだよなあ。