おはようございます。今日も解説記事です。

昨晩のABC165、A問題で適当を書いたらコーナー見落とすしC通せないしFでとんちんかんな考察するし散々でした。

今回は僕の他にも混乱した人が多かったであろうC問題を取り上げます。

問題

要素が $1$ 以上 $M$ 以下で長さ $N$ の非減少列 $A$ を考える。
$A$ の得点を $f(A)$ とすると、 $\displaystyle{f(A)=\sum _ {\{i|A _ {b_i} - A _ {a_i} == c _ i \}}d_i}$ ( $i = 1,\ \dots,\ Q$ )
$f(A)$ の最大値を出力せよ。
$2\leq N\leq10$
$1\leq M\leq10$
$1\leq Q\leq50$

解法

$N$ や $M$ が小さいので $A$ を全探索できないか考えます。
$A$ としては $(1,\ \dots,\ 1)$ から $(M,\ \dots,\ M)$ が考えられるのでこの数列の全探索は一見 $O(M^{N})$ かのように見えます(コンテスト中の僕はそう思って棄却しました......)。が、これが意外と少ないんです。その理由を考えるために長さ5の非減少列の大小関係の例を少し眺めてみましょう。

$A_0\lt A_1=A_2\lt A_3 = A_4$
$A_0 = A_1 = A_2 = A_3 = A_4$
$A_0\lt A_1 \lt A_2 \lt A_3 \lt A_4$

こうして見ると数列 $A$ が非減少 $\Leftrightarrow$ 隣接項の大小関係は '=' か '<' のみ なんですよね(当たり前だろ)。
仮に '<' による値の増加が 1 だけだとしたら各項の間にどちらの記号を入れるのかを選ぶだけなので $2^{n-1}$ 通りです。何かいけそうな雰囲気が出てきました。
いま、値の増加は 1 だけとは限らないのですが増加量の総和は最大でも $(M-1)$ と小さいです。したがって同じように各項の間に記号を挟むことで非減少列を表現することを考えてみます。
まず 『間に1コ挟むごとに次の値が1増加する』 という記号" $+$ "を導入します。" $+$ " は $(M-1)$ コあれば十分です( $M$ コ以上挟むと $M$ より大きい値が発生して制約に反するため)。また、項の区切りを示す記号を " $\#$ " とすると " $\#$ " は明らかに $N - 1$ コです。
これらの記号を並べるイメージについて $N = M = 5$ の場合の例を挙げておきます。補足ですが $A$ の構築にあたって、 $f(A)$ の計算式では $A$ の特定2要素の差だけが条件になっている(値の大きさは不問である)ことから $A_0 = 1$ と固定して問題ありません。

$A=\{1, 2, 3, 4, 5\}\ \Leftrightarrow\ A_0 +\# A_1 +\# A_2 +\# A_3 +\# A_4 \ \Leftrightarrow "+\#+\#+\#+\#"$
$A=\{1, 1, 3, 3, 4\}\ \Leftrightarrow\ A_0 \# A_1 ++\# A_2 \# A_3 +\# A_4+ \ \Leftrightarrow "\#++\#\#+\#+"$
$A=\{1, 1, 1, 1, 5\}\ \Leftrightarrow\ A_0 \# A_1 \# A_2 \# A_3 ++++\# A_4 \ \Leftrightarrow "\#\#\#++++\#"$

このように、 $M-1$ コの " $+$ " と $N - 1$ コの " $\#$ " を並べることで $A$ を網羅することができます。これは ${} _ {N+M-2} C _ {N-1}$ 通りで、 ${} _ {20} C _ {10}$ = 184756 くらいなので十分計算可能な状態数です。この方針によると実装1のような $2^{N+M-2}$ 通りの bit 全探索が可能となります。トータルの計算量は $O((N+M-2)2^{N+M-2}Q)$ です。C++であればこれでも全然間に合います。

また実装2のように、 $A_{i+1}$ の値を $[A_i,\ M]$ から選んでいく再帰関数で網羅することもできます。こちらはシンプルに実装できて、計算量改善にもなっています(bit 全探索では同じ数列を表すパターンを複数回調査している場合があるはず)。 $O((N+Q){} _ {N+M-2} C _ {N-1})$ です。

実装

実装1 : bit 全探索

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll n, m, q;
    cin >> n >> m >> q;

    vll a(q), b(q), c(q), d(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }

    ll res = 0, xxx = n + m - 2;
    // 2 ^ (n + m - 2) を全探索
    for (int bit = 0; bit < (1LL << xxx); bit++) {
        vll A(n, 1);
        ll id = 1;
        for (int i = 0; i < xxx; i++) {
            // i bit目が "+"
            if ((bit >> i) & 1) {
                A[id]++;
                if (A[id] == m) {
                    for (int j = id; j < n; j++) A[j] = m;
                    break;
                }
            }
            // i bit目が "#"
            else {
                A[id + 1] = A[id];
                if (++id == n) break;
            }
        }
        ll mem = 0;
        for (int i = 0; i < q; i++) {
            if (A[b[i]] - A[a[i]] == c[i]) mem += d[i];
        }
        chmax(res, mem);
    }
    cout << res << endl;
    return 0;
}

実装2 : 再帰関数

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll n, m, q;
ll res = 0;
vll a(55), b(55), c(55), d(55);
vll A(15);

void dfs(int id, int cur) {
        if (id == n) {
            ll mem = 0;
            for (int i = 0; i < q; i++) {
                if (A[b[i]] - A[a[i]] == c[i]) mem += d[i];
            }
            chmax(res, mem);
        }
        else {
            // A[id + 1] を [cur, m] から自由に決めることを再帰的に繰り返す
            for (int nxt = cur; nxt <= m; nxt++) {
                A[id + 1] = nxt;
                dfs(id + 1, nxt);
            }
        }
    };

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }
    A[0] = 1;
    dfs(0, 1);
    cout << res << endl;
    return 0;
}

実装3 : TL でちらほら流れてきたギャグ

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll n, m, q;
    cin >> n >> m >> q;

    vll a(q), b(q), c(q), d(q);
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }
    ll res = 0;
    vll A(10);
    for (A[0] = 1; A[0] <= m; A[0]++) {
        for (A[1] = A[0]; A[1] <= m; A[1]++) {
            for (A[2] = A[1]; A[2] <= m; A[2]++) {
                for (A[3] = A[2]; A[3] <= m; A[3]++) {
                    for (A[4] = A[3]; A[4] <= m; A[4]++) {
                        for (A[5] = A[4]; A[5] <= m; A[5]++) {
                            for (A[6] = A[5]; A[6] <= m; A[6]++) {
                                for (A[7] = A[6]; A[7] <= m; A[7]++) {
                                    for (A[8] = A[7]; A[8] <= m; A[8]++) {
                                        for (A[9] = A[8]; A[9] <= m; A[9]++) {
                                            ll mem = 0;
                                            for (int i = 0; i < q; i++) {
                                                if (A[b[i]] - A[a[i]] == c[i]) mem += d[i];
                                            }
                                            chmax(res, mem);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

感想

黄色のお友達も落としてたしヤバい(EF を通して補ってたけど)。全探索が10¹⁰に見えると貪欲を探してパニックして終わりという問題でした。 1時間くらい詰まってる暇があったらギャグを試してみるべきでしたね。通らない考察より通る『証明:AC』！(最悪)。

倒錯思索ステイルメイト

愚問愚答観察。

AtCoder ABC165 C - Many Requirements

問題

解法

実装

実装1 : bit 全探索

実装2 : 再帰関数

実装3 : TL でちらほら流れてきたギャグ

感想