C - Synthetic Kadomatsu

atcoder.jp

この問題は個人的に過去のABC-Cでも一二を争う難しさではないかと思いました。一言で言うと「全探索するだけ」なんですが、その全探索の仕方が独特というかいくつかの気づきが必要な問題だと感じました。

まず一つが「延長・短縮・合成の操作の順番を自由に入れ替えても最終的な状態や総コストは変わらない」ということです。延長・短縮の操作が入れ替え可能なのは明らかで、延長と合成も「竹Xを延長した後、竹Yと合成する」としても「竹XとYを合成した後、その竹を延長する」としても一緒だと言うことが分かります。短縮と合成についても同様です。

「操作の順番を好きなように入れ替えられること」を「操作が可換である」と言ったりもします。競プロにおいてはしばしば何か(数列とかグラフとか)に対して操作を繰り返すような問題が出ますが、「与えられた操作が可換であるかどうか?」は常に気を配りたいポイントですね。

そして延長・短縮・合成の中で一番複雑な操作が合成です。操作が可換だと分かったので「合成を先に全てやってしまって、残った竹に延長・短縮をやってA,B,Cを作る」と考えると少し考えやすくなる気がします。(もちろん複雑な操作は最後にまとめてやってしまう、という考え方もあると思いますしその方が考えやすくなる問題もあるかもしれません……その辺はアドホックなのかな、少なくとも今回は合成を先にやってしまう方が楽になりそう、というのは勘みたいなものが働いている気がします)

なのでまず合成を考えることにします。合成の順番も関係無いので、次のような操作に置き換えて考えると分かりやすくなりそうです。

  • 合成: 1本以上の竹を選んで、それらを全て接続した竹を作る。このコストはk本の竹を選んだとすると  10(k-1)

このように考えておくと「合成した竹を合成する」のは一回の合成で置き換えらえることも分かるので、合成した竹を合成するのは考えなくてよくなります。(1本の竹だけ選んだものも合成と呼んでる点に注意です)

次に大事なポイントが「合成した竹を使わないのは明らかに損」ということです。ここでいう「合成した竹を使わない」というのは作りたいA,B,Cのために割り当てない、ということです。これも明らかで使わないんだったら最初から合成しなかったことにしたほうが明らかにコストが小さくなるからです。

これらの考察から合成の仕方として考えるべきは、全ての竹について

  • Aのための合成に使う
  • Bのための合成に使う
  • Cのための合成に使う
  • 何もしない

という4つの場合全てを考えれば十分だということが分かりました。

これで合成に対して考えるべきことは終わりました。後は、

(Aのために使われた竹の長さの総和とAの長さの絶対値) + (Bのために使われた竹の長さの総和とBの長さの絶対値) + (Cのために使われた竹の長さの総和とCの長さの絶対値)

が延長・短縮にかかるコストの最小であることは明らかです。

最後に計算量を考えます。

各竹について選択肢が4つありますから、全ての場合を試すと4^n通りです。指数時間は一般的には遅いと思われていますが、今回の場合ですと n \le 8とかなり小さいので最大ケースでも 4^8 = 2^{16} = 65536通りとなり十分計算可能であることが分かります。

ここまで分かれば解ける人も多いと思いますが「4^nの全探索ってどうやるの?」という人も少なくないと思います。やり方は思いつく限り3通りあって

  1. 深さ優先探索(DFS)
  2. 4進数で全探索
  3. bit全探索(2進数の全探索)でゴリ押し

です。オススメ順に並べてみました。

深さ優先探索

一番素直だと思うのがこのDFSによる解法です。今回のような各点での枝分かれがk本みたいな状況に限らず、もう少し複雑な枝分かれをする場合にも応用が効きます。放送でchokudaiさんも言っていましたが汎用性がかなり高いのでスラっと書けるようになっておくとよいです。

部分的なコードは以下のような形です。

// idx は今見ている竹の番号、 gc はこれまで合成に使った竹の本数
int dfs(int idx, int la, int lb, int lc, int gc) {
    if (idx == n) {
        if (la == 0 || lb == 0 || lc == 0) {
            // A, B, Cの合成の竹に使われた竹が存在しないときは有効な回答ではない
            // このときは答えに影響が起きないような十分大きな値を返すことにする
            return inf3;
        }
        else {
            return abs(la - a) + abs(lb - b) + abs(lc - c) + 10 * (gc - 3);
        }
    }
    int res = inf3;
    // idx番目の竹を A のための合成に使う場合
    res = min(res, dfs(idx + 1, la + l[idx], lb, lc, gc + 1));
    // idx番目の竹を B のための合成に使う場合
    res = min(res, dfs(idx + 1, la, lb + l[idx], lc, gc + 1));
    // idx番目の竹を C のための合成に使う場合
    res = min(res, dfs(idx + 1, la, lb, lc + l[idx], gc + 1));
    // idx番目の竹は使わない場合
    res = min(res, dfs(idx + 1, la, lb, lc, gc));
    return res;
}

4進数で全探索

次に4進数による全探索です。こちらはややテクニカルな印象がありますが、dfsのような関数を書かずforループを回すだけでさくっと書けるのがポイントでしょうか。bit全探索を知っている方はこちらの解法を思いつきやすい気がします。

以下のコードでは(0 -> 使わない、 1 -> Aに使う、 2 -> Bに使う、 3 -> Cに使う)と対応付けています。その他の部分はdfsによる解法と大きな違いは無いです。

int ans = inf3;

foreach (s ; 0 .. 4^^n) {
    int la, lb, lc;
    int gc;

    foreach (i ; 0 .. n) {
        if (s % 4 == 1) {
            la += l[i];
            gc++
        }
        else if (s % 4 == 2) {
            lb += l[i];
            gc++
        }
        else if (s % 4 == 3) {
            lc += l[i];
            gc++;
        }
        s /= 4;
    }

    if (la == 0 || lb == 0 || lc == 0) continue;
    ans = min(ans, abs(la - a) + abs(lb - b) + abs(lc - c) + 10*(gc - 3));
}

bit全探索によるごり押し

上記2つと比較してスマートでもなく自然でもないのであまりオススメできない解法です。それでもなぜ書いたかというと、私がコンテスト中に書いたのがこの方法だったからです……

あまり多くは語らないので雰囲気だけ掴んでもらえたらと思います。 2^{3n}くらいかかってそうでやばくね?って思いますが、よく考えるとs,t,uの各bitが立つ本数が高々1本しかないので実は 4^nに収まっているという奴です(多分)

(2019.02.26 追記) と思ったんですが4^nに収まっているというのは嘘な気がしてきたのでやっぱり参考にしないでください

long ans = inf6;

foreach (s ; 1 .. 1 << n) {
    long tmp;

    int la;
    foreach (j ; 0 .. n) {
        if (s & (1 << j)) {
            la += l[j];
            tmp += 10;
        }
    }
    tmp -= 10;

    foreach (t ; 1 .. 1 << n) {
        auto ttmp = tmp;
        int lb;
        if (s & t) continue;
        foreach (k ; 0 .. n) {
            if (t & (1 << k)) {
                lb += l[k];
                ttmp += 10;
            }
        }
        ttmp -= 10;

        foreach (u ; 1 .. 1 << n) {
            if ((s | t) & u) continue;
            auto tttmp = ttmp;
            int lc;
            foreach (e ; 0 .. n) {
                if (u & (1 << e)) {
                    lc += l[e];
                    tttmp += 10;
                }
            }
            tttmp -= 10;
            tttmp += abs(la - a) + abs(lb - b) + abs(lc - c);
            ans = min(ans, tttmp);
        }
    }
}

おわりに

分かっているように書きましたが、実際コンテスト中は難しすぎてテンパってしまい、いろいろと最悪でした。一番下のコードになった理由も「合成する竹としない竹で分ければいいのか」→「いや、A,B,Cの3つに分ければいいのか」→「いや、使わなくていい竹もあるんじゃん」となってネストがどんどん深くなってしまったからです(しかも計算量は何となく大丈夫でしょみたいな感じで本当に適当だった)

いろいろと反省すべき点が多いコンテストでした。ABC-Cでも難しく感じたら焦らずに、考察はじっくりやらないとダメですね。