myauの競プロブログ

ARC109-E 1D Reversi Builder プチ解説

ARC109-E 1D Reversi Builder の解法が少し既存の解説と違ったので紹介します

備忘録的な感じ

参考リンク

drken1215.hatenablog.com

問題概要・考察の初歩は上記のリンクをご覧ください

盤面を固定した結果はけんちょんさんのブログの「正攻法」欄に記載されています

以下の説明は、この「正攻法」の考察がなされていることを前提とします

まず、多項式時間で「正攻法」の数え上げができるか考えてみます

以下の考察は左端が黒・右端が白であることを仮定します

スタートの位置 ${s}$ を固定します

ゲーム終了時の黒い石の個数は、左から何個黒が続くか、右から何個白が続くかの2つの情報でわかります

これらをそれぞれ ${A}$ , ${B}$ とします(けんちょんさんの記事と同様)

よって、 ${s}$ , ${A}$ , ${B}$ の3つを定めればゲーム終了時の黒い石の個数がわかるので、 ${O}({N}^{3})$ で数え上げることができます

ただし、今回の問題では ${N}≦{200000}$ なので、 ${O}({N})$ 程度まで高速化する必要があります

ここで ${s}$ を ${1}$ ~ ${N}$ まで動かしながら計算していくことを考えます

まず、 ${s}$ = ${1}$ のときはゲーム終了時の黒い石の個数は ${N-B}$ になります

${B}$ を決め打って、そのときの値を計算しておきましょう

一番左が黒、右から ${B}$ 個が白 = 右から ${B+1}$ 個目は黒になるので、自由に決められる色は ${max}$ ( ${N-B-2}$ , ${0}$ )個あり、この値を ${M}$ とすると、( ${N-B}$ ) × ${2}^{M}$ を足し合わせればよいです

それでは、 ${s}$ を1つずつ進めていきましょう

${s}$ を1つずつ進めていくと、 ${s}$ では終了時に ${N-B}$ 個黒い石があったのに、 ${s+1}$ では終了時に ${A}$ 個しか黒い石がない盤面が出てきます

その一方で、左端を黒に固定しているので、 ${s}$ よりも ${s+1}$ で終了時の黒い石が多くなることはありません

そこで、 ${s}$ では終了時に ${N-B}$ 個黒い石があったのに、 ${s+1}$ では終了時に ${A}$ 個しか黒い石がない盤面をまとめて数えることを考えます

そのような変化が起こるのは以下の2パターンになります

・ ${s-A = B-s}$

・ ${s-A+1 = B-s}$

ほとんど考え方は同じなので、 ${s-A = B-s}$ の場合のみ説明します

${s-A = B-s = D}$ とおきます (こちらの場合は条件より ${D=1}$ は存在できないことに注意)

この条件を満たす盤面の個数を考えます

左から ${A}$ 個は黒、左から ${A+1}$ 番目は白、右から ${B}$ 個は白、右から ${B+1}$ 番目は黒になることから、自由に決められるのは ${2D-3}$ 個になります

※ ${s}$ からの距離が ${D-1}$ 以上の場所はすでにきまっていると考えるのがわかりやすいかもしれません

よって、 ${D}$ を固定した時、 ${s}$ から ${s+1}$ になるタイミングで、( ${2D-1}$ ) × ${2}^{2D-3}$ だけ終了時の黒い石の個数が減少します

ある ${s}$ について、とることのできる ${D}$ の範囲は単一の区間になるので、あらかじめ各 ${D}$ のときの値を計算し、累積和を求めておくことで ${s}$ から ${s+1}$ に変わるときの差分を ${O}$ ( ${1}$ )で計算できるので、全体を ${O}$ ( ${N}$ )で求めることができます

実装例