はまやんはまやんはまやん

hamayanhamayan's blog

Hanjo 2 [AtCoder Beginner Contest 204 F]

競技プログラミング

競プロのコード例について補足 競技プログラミング練習問題集 Twitter 競技セキュリティまとめのまとめ

https://atcoder.jp/contests/abc204/tasks/abc204_f

前提知識

解説

https://atcoder.jp/contests/abc204/submissions/23263864

今回の問題はとても難しいのだが、典型度は高い。
まず、制約がかなりとがっているので、何を要求されているかは制約を見れば慣れてくれば分かる。
類題を見たことがあるので、解法までは一直線だったので、恐らく一部発想が飛んでいる。

敷き詰め対象について

組合せ計算をするという観点で考えると、2×1のタイルの置き方が決まれば、1×1はそれ以外に置くだけで置き方は一意に定まるので、
2×1のタイルをどのような形で置くかということだけを考えることにする。

H≦6とは何か？

パッと見て明らかにビットを意識した制約に見える。
今回の敷き詰めの問題を行っていくので、ビットで管理できそうなのは2×1のタイルが置かれているかどうかである。
その辺から組合せ計算という部分から考えるとビットDPが思いつく。

dp[i][msk] := i-1列目まで2×1のタイルの置き方が確定していて、i列目のタイルの置き方がmskである場合の置き方の組み合わせ

タイルが2×1のサイズしかないので、左から順に畳を置いていくように方針を決めれば、置こうとしている列の1つ前の列くらいしか置き方には影響しないことが分かる。
なので、i+1列目の置き方はi列目の置き方さえ分かればいいことになり、DPの状態として置き方のmaskが置かれることになる。

これでとりあえず状態圧縮は成功している。

Wの上限が1012

1012なので、log(W)かlog(1)を目指すしかない。
先のDPを見ると、i列目の状態からi+1列目の状態を作ることができる（それより前は関係ない）ので、行列累乗によるDP高速化が行えそうである。

行列累乗によるDP高速化

詳細を書くにはちょっとガッツが必要なので、コンセプトについては、ABC(AtCoder Beginner Contest)の009Dの解説を見るのがいいと思う。
Abc009
他にも「行列累乗 DP」とかでもいい解説が出てくるんじゃないかな？

ざっくり書くと
dp[i][any]からdp[i+1][any]への遷移について

  • dp[i+1][any]への遷移はすべてdp[i][any]からの遷移になっている
  • 1回の遷移は毎回同じように（同じ係数で）行われる
  • 行列計算で|any|^3の計算をするのでそれが間に合うか

が満たされれば使用することができる。

1番目は満たしていて、2番目も毎回状態が変化するわけではないので同じ遷移になるし、3番目が今回の条件に特にマッチする。
anyは26通りなので、218となり、ちょうどいい計算量となる。

後は実装

正直ここまで理解できるかが第一関門であり、実装もやや大変。
行列ライブラリを作る必要があるし、遷移のための行列を作るのも正直簡単ではない。
フィボナッチ数列の計算を行列累乗でできるかくらいの練習を先に挟むのがいいと思う。
そこで行列計算ライブラリか、行列計算の実装の手ごたえをつかむのがオススメ。

遷移の行列作り

さて、行列計算はOKと仮定すると、最後の関門は遷移の行列作りである。
色々実装はあると思うが、自分の実装では縦の組み合わせを先に計算してから、横の置き方を全探索することで遷移を試していくことにした。

init[msk] := 2×1の畳を縦に置くことでmskの状態を作ることができるか

これを先に作っておく。
これは全ての組み合わせについて上から2個グループが過不足無く作れるかを見ていけばいい。

E[to][from] := dp[i+1][to]に対して足し合わされる時のdp[i][from]に対する係数

を作る。fromとtoを全探索して係数を決めていくが、普通にやるのは難しい。
fromとtoを全探索するが、この時toは畳を縦に置いた場合のみを考える。その後、各列について横に畳を置く組合せを全探索して、
置けるなら置いて、置いた場所にビットを立たせてfromとtoを確定させて、組合せを足し合わせていく。
このやり方だとfrom, to, 各列の横置きの全探索で218通りかかるが、間に合うのでこれで実装した。

後は、initを初期ベクトルとして、Eを行列累乗でW-1回掛け合わせて、initとかけて総和を取れば答えになる。

int H; ll W;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;

    Mat m(1 << H, Vec(1 << H, 0));
    Vec v(1 << H, 0);

    Vec init(1 << H, 0);
    rep(msk, 0, 1 << H) {
        bool nextPlace = false;
        bool ok = true;
        rep(i, 0, H) {
            if (nextPlace) {
                if (msk & (1 << i)) nextPlace = false;
                else ok = false;
            }
            else {
                if (msk & (1 << i)) nextPlace = true;
            }
        }
        if (nextPlace) ok = false;
        if (ok) {
            init[msk] = 1;
        }
    }

    rep(msk, 0, 1 << H) v[msk] = init[msk];

    rep(from, 0, 1 << H) rep(to, 0, 1 << H) {
        rep(used, 0, 1 << H) {
            bool ok = true;
            rep(i, 0, H) if (used & (1 << i)) {
                if ((from & (1 << i)) || (to & (1 << i))) ok = false;
            }
            if (ok) {
                int to2 = to;
                rep(i, 0, H) if (used & (1 << i)) to2 += 1 << i;
                m[to2][from] = add(m[to2][from], init[to]);
            }
        }
    }

    m = fastpow(m, W - 1);
    v = mulMatVec(m, v);

    int ans = 0;
    rep(msk, 0, 1 << H) ans = add(ans, v[msk]);
    cout << ans << endl;
}