MENU
  1. ホーム
  2. AtCoder
  3. ABC
  4. 【競プロ精進ログ】ABC165-C

【競プロ精進ログ】ABC165-C

AtCoder ABC
zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次へジャンプ
目次

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC165-C「Many Requiements」です。

ポイント

非常に良い問題でした。まず，方針として$N$と$M$が小さいことに注目します。すると，全探索できるかもという気持ちになります。しかし，一度全探索の方針でコードを書き始めてしまうと，いざTLE（処理時間オーバー）になってしまったときにまた0から書き直しという事態になりかねません。

そこで，大まかにでも良いので全探索した場合にかかる計算量を見積もりましょう。そこで必要となる考え方が「広義単調増加数列の重複順列」です。広義単調増加数列とは，1つ前のインデックスの数字よりも次の数字の方が小さくならないような数列のことを指します。小さくならないというのがポイントで，前の数字と等しい場合を含む増加数列が広義単調増加数列です。一方で，前の数字よりも常に大きくなるような数列は狭義単調増加数列と呼びます。

さて，少し天下り的ですが，広義単調増加数列の重複順列はボールと仕切り棒によってモデル化することができます。今回の問題で言えば，$M$個のボールと$N$個の仕切り棒を考えて，その並び順（順列）を考えれば，広義単調増加数列と一対一対応します。

どういうことかと言うと，$i$番目の仕切り棒の「左側にあるボールの数」を$A_i$とすれば，数列$\{A_1, \ldots, A_N\}$は広義単調増加数列になるのです。高校数学でも登場してきた考え方ですが，競技プログラミングでも頻出のアイディアですので，ぜひおさえておきたいところです。

さて，今回の問題は少しだけ例外があります。$A_i$は最小でも$1$という指定があります。$M$個のボールと$N$個の仕切り棒を考えてしまうと，$A_1$は最小で$0$になってしまいます。そこで，少し工夫して$M-1$個のボールと$N$個の仕切り棒を考えて，それぞれの$A_i$に$1$を足してあげればOKです。アイディアとしては，最小値が$1$になるように底上げして，その代わりにモデル化するボールを1個減らしてあげようというものです。

したがって，計算量$C$は「$M-1$個のボールと$N$個の仕切り棒の並べ方」に相当します。$M$も$N$も最大で$10$であることを踏まえると，計算量はコンビネーションを用いて以下の式で求められます。

\begin{align}
C &= {}_{19} C_{9} \\
&= 92378
\end{align}

コンビネーションの計算はWalframAlphaで「19 choose 9」と入力すれば，簡単に計算することができます。c++でコンビネーションを計算したい方は，こちらの記事【c++で楽しく実装！】二項係数（コンビネーション）の計算をご覧ください。

zuka

$10^5$程度だから全探索できるね。計算量の限界については下の表を見てみて。

スクロールできます
$N$$O(1)$$O(\log N)$$O(N)$$O(N \log N)$$O(N^2)$$O(2^N)$
$1$一瞬一瞬一瞬一瞬一瞬一瞬
$10$一瞬一瞬一瞬一瞬一瞬一瞬
$10^3$一瞬一瞬一瞬一瞬$\fallingdotseq 0.01$[s]地球爆発
$10^6$一瞬一瞬$\fallingdotseq 0.01$[s]$\fallingdotseq 0.2$[s]$\fallingdotseq 3$[h]地球爆発
$10^8$一瞬一瞬$\fallingdotseq 1$[s]$\fallingdotseq 30$[s]$\fallingdotseq 3$[y]地球爆発
$10^{16}$一瞬一瞬$\fallingdotseq 3$[y]$\fallingdotseq 170$[y]地球爆発地球爆発
APG4b「2.06.計算量」より
表中の[s]は秒，[h]は時間，[y]は年を表す
おさえるべき内容

　全探索を行うときは必ず計算量を見積もる

方針

先ほどまでの議論で，この問題は全探索で解くことができることが分かりました。問題になるのは，どうやって全探索を実現するか，つまりどのように考えられる数列$\{A_1 \ldots A_N\}$を列挙するかという点です。方針は大きく分けて3種類あります。

解答の方針
  1. next_permutationを利用する
  2. 深さ優先探索を利用する
  3. 幅優先探索を利用する

それぞれについて実装方法をみていきましょう。なお，深さ優先探索と幅優先探索では列挙していく数列の順番が異なるだけです。

実装

next_permutationの利用

next_permutationについては，以下の記事を参考にしていただければと思います。

あわせて読みたい
【競プロ精進ログ】ABC145-C 本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミ... 
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N, M, Q;
vector<int> a, b, c, d;

int score(vector<int> A) {
    int res = 0;
    rep(i, Q) if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

int main(){
    // AとBはインデックスを表すので0インデックスに揃えておく
    // CとDはスコアなので関係ない
    cin >> N >> M >> Q;
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    rep(i, Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }
  // next_permutationするためのvector
  // 辞書順で生成しておく必要があるため最初のM-1個を0に初期化する
  // vector自体は1で初期化しておいて後から最初のM-1個を0に初期化する
  // ボールが0で仕切り棒が1を表す
  vector<int> X(N+M-1, 1);
  rep(i, M-1) X[i] = 0;

  // 最終的なアウトプットを管理する変数
  int ans = 0;
  // next_permutationのdo部分
  do{
    // A_iは最小でも1
    int cnt = 1;
    // next_permutationによって生成されたAを管理するvector
    vector<int> Y;
    // next_permutationされたXをYに対応させる
    // 仕切り棒が出てきたらYにそれまでのボールの個数を追加する
    rep(i, X.size()){
      if (X[i]==1) Y.push_back(cnt);
      else cnt++;
    }

    // 問題文の条件を記述する
    ans = max(ans, score(Y));
  }

  // next_permutationのwhile部分
  while (next_permutation(X.begin(), X.end()));

  // 解答出力
  cout << ans << endl;
}

深さ優先探索の利用

深さ優先探索と幅優先探索については以下の記事をご覧ください。

あわせて読みたい
【c++で楽しく実装！】深さ優先探索(DFS)&幅優先探索(BFS) 本記事では，深さ優先探索（DFS）と幅優先探索（BFS）の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の...

以下では，while文を使った実装と再帰を使った実装の2パターンをお見せしようと思います。

while文を使ったパターン

while文を使ったパターンでは，スタックに作成途中の数列を格納していきます。

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N, M, Q;
vector<int> a, b, c, d;

// スコア計算関数
int score(vector<int> A) {
    int res = 0;
    rep(i, Q) if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

int main() {
    cin >> N >> M >> Q;
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    rep(i, Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }

    // スタックの初期値は{{1},{2},{3},{4}}
    stack<vector<int>> st;
    rep(i, M){
        vector<int> s = {i+1};
        st.push(s);
    }

    int ans = 0;
    // スタックが空になるまで回し続ける
    while (!st.empty()){
        // スタックの一番上の要素について処理を行う
        vector<int> elem = st.top();
        // 読み取ったら削除しておく
        st.pop();
        // 数列の長さがNであればスコアを計算して最大値を更新していく
        if (elem.size() == N) ans = max(ans, score(elem));
        // 数列の長さがNでなければ要素を追加してスタックにプッシュする
        else {
            repi(i, elem[elem.size()-1], M+1){
                vector<int> elem_new = elem;
                elem_new.push_back(i);
                st.push(elem_new);
            }
        }
    }
    cout << ans << endl;
}

再帰を使ったパターン

再帰を使ったパターンでは，ベクター自身が探索対象の数列を表します。

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N, M, Q;
vector<int> a, b, c, d;

// スコア計算関数
int score(vector<int> A) {
    int res = 0;
    rep(i, Q) if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

// dfsの再帰部分定義
int dfs(vector<int> A) {
    // 数列の長さがNのときはスコアを返す
    if (A.size() == N) {
        return score(A);
    }
    // まだ数列の長さがNでないときはベクターの末尾に要素を追加していく
    int res = 0;
    int last = 0;
    // lastが数列の最大の値
    if (!A.empty()) last = A.back();
    // Aに要素を追加していく
    repi(i, last, M) {
        A.push_back(i);
        // 再帰部分
        res = max(res, dfs(A));
        // 処理を行なったものに関しては削除する
        A.pop_back();
    }
    return res;
}

int main() {
    cin >> N >> M >> Q;
    // グローバルに宣言したベクターを問題文の大きさに調節する
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    rep(i, Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }

    // 空のベクターを入れると再帰的に空になるまでdfsしてくれる
    vector<int> A;
    cout << dfs(A) << endl;
}

幅優先探索の利用

幅優先探索では，深さ優先探索においてスタックであるところをキューにします。

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N, M, Q;
vector<int> a, b, c, d;

// スコア計算関数
int score(vector<int> A) {
    int res = 0;
    rep(i, Q) if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

int main() {
    cin >> N >> M >> Q;
    a.resize(Q); b.resize(Q); c.resize(Q); d.resize(Q);
    rep(i, Q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--, b[i]--;
    }

    // キューの初期値は{{1},{2},{3},{4}}
    queue<vector<int>> que;
    rep(i, M){
        vector<int> q = {i+1};
        que.push(q);
    }

    // 以下は深さ優先探索と同様
    int ans = 0;
    while (!que.empty()){
        vector<int> elem = que.front();
        que.pop();
        if (elem.size()==N) ans = max(ans, score(elem));
        else {
            repi(i, elem[elem.size()-1], M+1){
                vector<int> elem_new = elem;
                elem_new.push_back(i);
                que.push(elem_new);
            }
        }
    }
    cout << ans << endl;
}
AtCoder ABC
よかったらシェアしてね！
  • URLをコピーしました！

コメント

コメントする

※ Please enter your comments in Japanese to distinguish from spam.

目次