まず思うこと ソートしても題意が変わらないので，ソートします．(頻出中の頻出なので普通やる．) ついでに座標圧縮もしちゃいましょう． これで，問題が次のように変わりました． 爆弾が N 個あり，i 番目の爆弾は座標 i にある．各爆弾のオンオフ状態は s[…

まず，f(r, c) を表形式で図示します．数字が大きすぎて省略されてしまっている部分がありますが，無視してください． f(r, c) を表形式で表したもの ところで，この値は パスカルの三角形 (のちょっと内側) と一致しています．ゆえに，f(r, c) = f(r-1, c) …