けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 168 C - : (Colon) (300 点)

余弦定理を使うか、座標を求めるか、、、いずれにしても三角関数の素養を要求する問題。

問題へのリンク

問題概要

時計の時針と分針があって、それぞれ長さは  A,  B となっている。 H B 分の段階において、時針の先端と分針の先端との距離がどのようになっているかを求めよ。

制約

  •  1 \le A, B \le 1000

解法 1: 余弦定理

まず一つの観察として、


三角形の二辺の長さと、それを挟む角度がわかっていたら、三角形の形が決まるはずだ

つまり、下図の赤線の長さがわかるはずだ!!!


というのがある。

f:id:drken1215:20200519043520p:plain

これを実際に求める方法を与えるのが、数学 1 で学ぶ「余弦定理」である。


余弦定理】
上図の赤線の長さは、

 \sqrt(A^{2} + B^{2} - 2AB \cos{\theta})

となる


余弦定理は「三平方の定理」を一般化したものになっている。具体的には、 \theta を直角とすると、 \cos{\theta} = 0 なので、赤線の長さは  \sqrt(A^{2} + B^{2}) になる。これは三平方の定理そのもの!!

いずれにせよ、余弦定理を見ると、 \theta さえ求められればよいということがわかる。

角度 θ

時針の角度  \alpha と、分針の角度  \beta をそれぞれ求めてあげて、その差を求めればよい。一見すると、

  •  \alpha \beta の大小関係で場合分け
  •  \theta が 180 度を超えるかどうかで場合分け

が必要なように思えてしまうかもしれない。

f:id:drken1215:20200519095827p:plain

しかしながら、

  •  \cos(- \theta) = \cos \theta (ゆえに、 \alpha \beta の大小関係は気にしなくてよい)
  •  \cos(2 \pi - \theta) = \cos \theta (ゆえに、 \theta が 180 度を超える側になっても問題ない)

といったことが成り立つ。よって、

  •  \theta = \alpha - \beta

として、 \sqrt(A^{2} + B^{2} - 2AB \cos{\theta}) を計算すればよい。

時針の角度 α の求め方

時針は 12 時間 (= 720 分) で 360 度回転する。よって、そのうちの  60H + M 分時点での角度  \alpha は、

 \alpha = \frac{60H + M}{720} × (2\pi)

と求められる。ここで、以下のように間違えないように注意!!

(間違い)  \alpha = \frac{H}{12} × (2\pi)

これだと、1 時間おきに時針が、「一気に動いて」「止まって」を繰り返す不自然な動きになってしまう。

分針の角度 β の求め方

分針は 60 分で 360 度回転する。よって、そのうちの  M 分時点での角度  \beta は、

 \beta = \frac{M}{60} × (2\pi)

で求められる。

まとめ

以上をまとめると、以下のようにして  O(1) で解ける

  •  \alpha = \frac{60H + M}{720} × (2\pi) として、
  •  \beta = \frac{M}{60} × (2\pi) として、
  •  \theta = \alpha - \beta として、
  • 答えは  \sqrt(A^{2} + B^{2} - 2AB \cos{\theta})

なお、円周率  \pi は、acos(-1.0) の値を用いるのが簡明。

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

const double PI = acos(-1.0);
int main() {
    double A, B, H, M;
    cin >> A >> B >> H >> M;
    double alpha = (H * 60 + M) / 720 * (PI * 2);
    double beta = M / 60 * (PI * 2);
    double theta = alpha - beta;
    double res = sqrt(A*A + B*B - 2.0*A*B*cos(theta));
    cout << fixed << setprecision(10) << res << endl;
}

解法 2: 2 点の座標を求めて距離を算出する

計算幾何に慣れている人にとっては、こっちの方がむしろ自然な解法だと思う。計算幾何は基本的に「点」と「線分」を扱う。その観点からは

  • なんらかの定義づけがなされた「点」の座標を一つ一つ求めていく

というのが自然なアプローチだと思う。その観点から言うと、今回の問題も

  • 時針の先端の座標  (x_{A}, y_{A})
  • 分針の先端の座標  (x_{B}, y_{B})

を求めてあげれば、その二点間の距離を

 \sqrt((x_{A}-x_{B})(x_{A}-x_{B}) + (y_{A}-y_{B})(y_{A}-y_{B} ) )

によって求めることができる (二点間の距離の公式を参照)。

単位円と座標

最後に、時針・分針の先端の座標を求める方法を考えよう。その前に単位円を用いた三角関数の定義を確認しておく。

f:id:drken1215:20200520071701p:plain

上図のように、円の半径を 1 として、X 軸とのなす角が  \theta であるような円周上の点を P とする。このとき、P の座標を

 (\cos \theta, \sin \theta)

とする。むしろこっちの方が、高校数学の範囲では汎用的な三角関数の定義といえる (この記事参照)。そして円の半径が  A のときは、P の座標は

 (A \cos \theta, A \sin \theta)

となる。

今回の問題だと

今回の問題では、下図のように X 軸、Y 軸をとれば OK。そうすると、単純に、

  • 時針の先端の座標は、 (A \cos \alpha, A \sin \alpha)
  • 分針の先端の座標は、 (B \cos \beta, B \sin \beta)

と求められる。0 時の方向に X 軸を合わせるイメージ。そして針の進行方向に Y 軸を持ってくるイメージ。

f:id:drken1215:20200520082159p:plain

まとめ

以上をまとめると、以下のようにして  O(1) で解ける

  •  \alpha = \frac{60H + M}{720} × (2\pi) として、
  •  \beta = \frac{M}{60} × (2\pi) として、
  • 時針の先端の座標は、 (x_{A}, y_{A}) = (A \cos \alpha, A \sin \alpha)
  • 分針の先端の座標は、 (x_{B}, y_{B}) = (B \cos \beta, B \sin \beta)
  • 答えは  \sqrt((x_{A}-x_{B})(x_{A}-x_{B}) + (y_{A}-y_{B})(y_{A}-y_{B} ) ) となる
#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);
int main() {
    double A, B, H, M;
    cin >> A >> B >> H >> M;
    double alpha = (H * 60 + M) / 720 * (PI * 2);
    double beta = M / 60 * (PI * 2);
    double xA = A * cos(alpha), yA = A * sin(alpha);
    double xB = B * cos(beta), yB = B * sin(beta);
    double res = sqrt((xA-xB)*(xA-xB) + (yA-yB)*(yA-yB));
    cout << fixed << setprecision(10) << res << endl;
}

AtCoder ABC 138 D - Ki (400 点)

まさに「the 緑 diff」な問題だと思う。
「木を上手く扱えるか」を問いかける問題。

問題へのリンク

問題概要

 N 頂点の木が与えられる。この木の頂点 1 を根とした根付き木を考える。各頂点には初期状態では 0 という数値が書かれている。以下の  Q 回の操作を行なった後の各頂点の数値を答えよ。

  •  j 回目の操作では、頂点  p_{j} を根とする根付き木に含まれるすべての頂点に  x_{j} を加算する

制約

  •  N, Q \le 2 \times 10^{5}

考えたこと

この問題は、2 つのことを要求している

  • 木じゃなくて配列なら解けるのか?
  • 木はどう扱えばよいのか?

これらそれぞれ単体では、茶色 diff になるのかなと思う。

木じゃなくて配列ならどうか?

この問題に限らず、木上のクエリを処理する問題では、「まずは配列について考える」というのがポイントになることが多い。配列は「枝分かれのない木」なので、木の特殊ケースとみなせるのだ。

さて、今回の問題を木に置き換えると、次のような問題になる。


  •  N 要素からなる配列があって、最初はすべて 0 が書き込まれている
  • 各クエリは「配列の  p, p + 1, \dots, N に、値  x を加算する」

これは各クエリに対して愚直に計算すると  O(NQ) になってしまうのでダメ。

ここで「いもす法」のようなアイディアを思い出してみよう。まず、「配列の  p, p + 1, \dots, N に、値  x を加算する」という操作は次の 2 段階の操作に分解できる。

  1. 配列の index p の位置に、 x を加算する
  2. 配列の累積和をとる

f:id:drken1215:20200516214459p:plain

通常は、各クエリごとに、「1」をやって「2」をやるという感じのイメージだけど、

  • まず 1 について、全クエリ分を処理してしまう (それぞれのクエリにつき  O(1))
  • 最後に一回だけ累積和をとる ( O(N))。

という風にすれば、 O(N + Q) で処理できる。これはいもす法の特殊ケースで、「一律加算する右側が常に配列の右端になっているような場合」とみなせる。

木上で

これまでの処理を自然に木に拡張すれば OK。配列上で累積和をとる操作は、木では「根から子へと値を配っていく」というイメージになる。

まず配列 res を 0 に初期化しておく。そして、各クエリ ( p, x) ごとに、res の index  p のところに  x を加算しておく。その後、木の根から出発して、子へと値を累積させていく。最終的には各頂点 v に対して、

  • res[ v ] = 根から頂点 v に至るまでの各頂点までの  x の値の総和

となるようにすれば OK。以下のような再帰関数を定義してあげて、

// 頂点 v について処理、p: v の親
dfs(int v, int p, vector<long long> &res);

次のように処理することで実現できる。

  • val[ v ] += val[ p ] (v が根の場合はしない)

計算量は  O(N + Q)

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

using Graph = vector<vector<int>>;
int N, Q;
Graph G;

void dfs(int v, int p, vector<long long> &res) {
  if (p != -1) res[v] += res[p];
  for (auto e : G[v]) {
    if (e == p) continue;
    dfs(e, v, res);
  }
}

int main() {
  cin >> N >> Q;
  G.assign(N, vector<int>());
  for (int i = 0; i < N-1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<long long> val(N, 0);
  for (int i = 0; i < Q; ++i) {
    int p, x;
    cin >> p >> x;
    --p;
    val[p] += x;
  }
  dfs(0, -1, val);
  for (auto v : val) cout << v << " ";
  cout << endl;
}

AtCoder ABC 139 D - ModSum (400 点)

これが灰色 diff なのかーーー、マジかーーー!!!
いや、AtCoder プレイヤー、数学強すぎでしょ!!!

問題へのリンク

問題概要

正の整数  N が与えられる。
 1, 2, \dots, N の順列  P をすべて考えたときの、

 \sum_{i = 1}^{N} i %  P_{i}

の値の最大値を求めよ。

制約

  •  1 \le N \le 10^{9}

考えたこと

文句なしの数学ゲー。でも灰色 diff なのは驚く。そもそも問題の趣旨を理解するのもそんなに簡単じゃないと思う。 N = 5 とすると

  • 1 % ○
  • 2 % ○
  • 3 % ○
  • 4 % ○
  • 5 % ○

の総和が最大になるように、○のところに 1〜5 を 1 個ずつ入れる、という問題になる。この場合の答えは

  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • 4 % 5 = 4
  • 5 % 1 = 0

が最適になる。これ以上は大きくできない。それは何故だろうか。

上界の証明

まず、「% 1」「% 2」「% 3」「% 4」「% 5」のそれぞれについて、理論的にどこまで余りを大きくできるのかを考えてみよう。そうすると

  • 「% 1」: あまり 0 にしかならない
  • 「% 2」: あまりは最大で 1
  • 「% 3」: あまりは最大で 2
  • 「% 4」: あまりは最大で 3
  • 「% 5」: あまりは最大で 4

という感じになっている。一方、上で作った例を見ると...

  • 5 % 1 = 0
  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • 4 % 5 = 4

見事に「% 1」「% 2」「% 3」「% 4」「% 5」の全部について、最大を達成している。よって、合計値も当然最大だ!!!

一般の  N の場合でも、

  • N % 1 = 0
  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • ...
  • (N-1) % N = N-1

とすれば、各「% Pi」に対して最大を達成できるので、合計値も最大になる。答えは、

  •  0 + 1 + 2 + \dots + (N-1) = \frac{N(N-1)}{2}

となる。計算量は  O(1)。実装上はオーバーフローに注意 (int 型ではなく、long long 型にしよう)!!!

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

int main() {
  long long N;
  cin >> N;
  cout << N * (N - 1) / 2 << endl;
}

AtCoder ABC 140 D - Face Produces Unhappiness (400 点)

ABC では数少ない発想力系。

問題へのリンク

問題概要

L と R から成る  N 文字の文字列  S が与えられる。文字列のスコアは次のようにして決められる。

  • 各 index i について
    • S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算
    • S[ i ] = 'R' ならば、i + 1 < N かつ S[ i + 1 ] = 'R' のときに限り、1 を加算

今、文字列  S に対して、「区間を指定して区間内の 'L' と 'R' を入れ替える」という操作を  K 回まで行える。 S のスコアを最大化せよ。

制約

  •  1 \le N, K \le 10^{5}

考えたこと

とてもメタ思考的なことを言うと、「操作を最大  K 回まで行うことができる」という問題設定は、アルゴリズム的にできることがとても限られてくる。そういう問題は最終的には

  • 1 回操作するごとに、何らかの値が規則的に変化していく
  • なんらかの意味で Greedy に、順にやっていくとよい

といった解法になることがほとんどだ!!!
そしてそういう解法にもっていくためには、とにかく「操作の意味をわかりやすく言い換える」というのが大変重要になってくる。

スコアの意味を言い換える

というわけでこの問題では、まず、スコアの意味がよくわからないので、スコアをわかりやすく言い換えることを試みてみよう。たとえば、

S = LLLRRRLLLLLRLLLRRLRRRR

といった文字列であったとき、このスコアは、「L が連続した部分」と「R が連続した部分」を完全に別々に考えて合算すれば問題ないことがわかる。

そしてたとえば、

S = LLLLL

について考えると、スコアは 4 になる。ところで、"LLLLL" という文字列には、'L' と 'L' の隙間が 4 箇所ある。よって、"LLLLLLLLL" のように、同じ文字が連続している部分のスコアは

  • 文字と文字の間の隙間の個数

に一致することがわかる。このように解釈すると、結局


文字列  S (長さ  N) のスコアは、「文字と文字との間の隙間」のうち異なる文字が隣接している箇所を  a 箇所としたとき、

 N-1-a

で与えられる


ということがわかる。つまり、 N-1 箇所ある「隙間」のうち、'L' と 'R' の変わり目の個数を除いた値ということになる。

解法へ

スコアをここまで言い換えられたら、あとは単純明快。操作を行なっていくごとに「'L' と 'R' の変わり目」を減らしていけば良い。

具体的には

  • S = "LLLLLRRRLLLLRRLLLL"

といった状態のとき、たとえば "RRR" のところを反転させれば

  • S = "LLLLLLLLLLLLRRLLLL"

になる。このように、一回の操作で「'L' と 'R' の変わり目」を最大で 2 箇所ずつ消すことができる。よって求める最大値は、

  •  N - 1 - \max(a - 2K, 0)

となる。計算量は  O(N)

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

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  int a = 0;
  for (int i = 0; i + 1 < N; ++i) if (S[i] != S[i+1]) ++a;
  cout << N - 1 - max(a - K*2, 0) << endl;
}

よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜

時は 2020 年 5 月 3 日。
ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています!!!

これらの多くは緑後半から水色前半の difficulty を叩き出す、とても恐れられている問題たちです。しかし実のところ、「ちょっと複雑だけど、単純に全探索するだけ」という側面もあります。

これらの出題が最近急増しているのは、おそらくは AtCoder 社側に


  • 最近の AtCoder 参加者は数学パズル的な問題を解きすぎていて、こういうむしろプログラミングに寄った全探索ができない傾向にある
  • そういう出題を増やすことで、そういうのに慣れてもらいたい

という危機感があるのだと思われます。こういう「複雑だけど全探索するだけ」という雰囲気の問題は、大昔の競プロではむしろ主流でした。数学要素が強めな出題傾向は、割と最近のことのようです。

全体レベルがドンドン上がっていると言われている中、こうした古き良き雰囲気の問題は、むしろ difficulty が高く出てしまう傾向にあります。よって、逆に言えば

  • 「複雑だけど全探索するだけ」という問題は、プログラミング力を問う側面が強く、数学経験値の大小に左右されない!!!
  • 練習すればするだけ解けるようになるし、慣れれば発想は不要なので簡単!!
  • よって差をつけられる!!

ということで、慣れればお買い得な問題と言えます!!!

 

1. 再帰関数のモチベーション

再帰関数って、一口にいっても、色んな使い方があります!

しかしここでは、下に挙げたような「あまりにもエグい多重 for 文」を再帰関数にする、という使い方を徹底的に練習していきたいと思います!それができれば、上に挙げた、最近の AtCoder の DFS 全探索問題が大体解けます!!!

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

int main() {
    const int M = 2;
    for (int a = 0; a < M; ++a) {
        for (int b = 0; b < M; ++b) {
            for (int c = 0; c < M; ++c) {
                for (int d = 0; d < M; ++d) {
                    for (int e = 0; e < M; ++e) {
                        for (int f = 0; f < M; ++f) {
                            for (int g = 0; g < M; ++g) {
                                for (int h = 0; h < M; ++h) {
                                    for (int i = 0; i < M; ++i) {
                                        for (int j = 0; j < M; ++j) {
                                            cout << a << b << c << d << e << f << g << h << i << j << endl;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

ちなみにこのエグい多重ブープは、 2^{10} = 1024 通りの 0, 1 列を出力するコードになっています。出力結果は下のようになります。

0000000000
0000000001
0000000010
0000000011
0000000100
0000000101
...
1111111000
1111111001
1111111010
1111111011
1111111100
1111111101
1111111110

こういうエグい多重ループは、大抵の場合、再帰関数で機械的に書き直すことができます!!!

具体的な再帰関数の書き方の詳細は後に回すとして、試しに下のコードを実行すると、全く同じ出力結果になるはずです!!!

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

const int M = 2;
void dfs(vector<int> &A) {
    // 終端条件 --- 10 重ループまで回したら処理して打ち切り
    if (A.size() == 10) {
        for (int i = 0; i < 10; ++i) cout << A[i];
        cout << endl;
        return;
    }

    for (int v = 0; v < M; ++v) {
        A.push_back(v);
        dfs(A);
        A.pop_back(); // これが結構ポイント
    }
}

int main() {
    vector<int> A;
    dfs(A);
}

これは Python だと、下のように書けます (本当は itertools を使えばもっと簡単に書けたりもしますが、応用は効かない感じです)!

M = 2
def dfs(A):
    # 終端条件 --- 10 重ループまで回したら処理して打ち切り
    if len(A) == 10:
        print(A)
        return
    for v in range(M):
        A.append(v)
        dfs(A)
        A.pop() # これが結構ポイント

dfs([])

なお、このような出力結果を見て「これ bit 全探索もできるやん」と思った方も多いかもしれません。実際、bit 全探索を再帰関数で実現する上での注意点などを細かく解説した記事も以前書きました!!!

drken1215.hatenablog.com

さて、このような再帰関数の書き方は、実は、ほとんどテンプレ化することができます。そこで本記事では、


テンプレ化された再帰関数」に慣れる


ことによって、様々な探索を実現できるようにしていきます!

 

2. 再帰関数の書き方

さて、多重 for 文が何をしているのかを思い起こしてみましょう。多重 for 文というのは結局、


ある条件を満たす「数列」を全探索する


というのをしていると言えます。上のエグい多重 for 文も、言い換えれば、

  • 0 または 1 からなる、長さ 10 の数列 ( 2^{10} = 1024 通りある)

を全探索しています。ここで再帰関数の出番です!再帰関数を使うと、色んな数列を簡単に生成することができます!

このように数列を生成する再帰関数は、大体次のような実装テンプレで対応できます!!!ただし、ここでは

  • 長さ  N の数列を生成したい
  • 数列の各項の値は  0, 1, \dots, M-1 であるようにしたい

という状況を考えています (そのような数列は  M^{N} 通りあります)。

C++

void dfs(vector<int> &A) {
    // 数列の長さが N に達したら打ち切り
    if (A.size() == N) {
        // 処理
        return;
    }

    for (int v = 0; v < M; ++v) {
        A.push_back(v);
        dfs(A);
        A.pop_back();
    }
}

int main() {
    vector<int> A;
    dfs(A);
}

Python

def dfs(A):
    # 数列の長さが N に達したら打ち切り
    if len(A) == N:
        # 処理
        return
    for v in range(M):
        A.append(v)
        dfs(A)
        A.pop()

dfs([])

この再帰関数の挙動を図示すると、下図のようになります。

f:id:drken1215:20200504173120p:plain

具体的に何をしているのかを順を追って見ていきましょう。たとえば  N = 5 M = 3 として、 A = (2, 0, 1) の状態で dfs(A) が呼び出されるシチュエーションを考えてみます。このとき、


  • まず A の要素数が N (= 5) かどうかをチェックする → 違うのでスルー
  • 最初に v = 0 について
    • A に v を push (append) する → A = (2, 0, 1, 0) になる
    • dfs(A) を再帰呼出しする
    • A を pop する → A = (2, 0, 1) になる
  • 次に v = 1 について
    • A に v を push (append) する → A = (2, 0, 1, 1) になる
    • dfs(A) を再帰呼出しする
    • A を pop する → A = (2, 0, 1) になる
  • 最後に v = 2 について
    • A に v を push (append) する → A = (2, 0, 1, 2) になる
    • dfs(A) を再帰呼出しする
    • A を pop する → A = (2, 0, 1) になる

という流れになっています。つまり、下図のような分岐処理を行なっていることになります。

f:id:drken1215:20200504171856p:plain

注意点として、for 文の中身は

A.push_back(v);  // v を push
dfs(A);  // 再帰呼出し
A.pop_back();  // pop

という三手一組になっていますが、最後の pop を忘れがちです。でもこれを実施しないと、下図のような分岐になってしまいます。

f:id:drken1215:20200504172423p:plain

さて、この再帰関数 dfs を、一番最初に呼び出すときには、「空の配列」を引数に入れています。C++ では、

int main() {
    vector<int> A;
    dfs(A);
}

という風にしていて、Python では

dfs([])

という風にしています。そして、再帰呼出しが行われるたびに、要素が 1 つ 1 つ追加されていくことになります。最終的に配列の長さが  N になったら、処理が打ち切られます。

細かい注意点

上で紹介した、下のような「三手一組」の実装についてです。

for v in range(M):
     A.append(v)
     dfs(A)
     A.pop()

Python だと、次のようにしたくなるかもしれません。

for v in range(M):
    dfs(A + [v])

これでも正しく処理することができます。しかしながら、これだと、毎回リストを作り直すような挙動になるので、多少計算に時間がかかるようになります。

なお、今回の記事で扱っているような「数列生成」に限らず、このように

(次のノードへの遷移)
(再帰呼出し)
(一回元に戻す)

という三手一組の実装で動くアルゴリズムを、一般にバックトラックと呼ぶことがあります。ノード間の遷移を「差分」だけで実装しているので、一回一回コピーするよりも高速に動作します。

計算量

このような再帰関数の計算量を見積る方法を考えてみましょう。再帰関数では一般に、

  • 分岐の回数 (つまり、下図の矢印の本数)

が、そのまま計算時間となります。本記事で扱うような再帰関数では、「異なるノードから同一のノードへの合流」がないため、

  • 「分岐」 (下図の矢印) の本数
  • 「ノード」 (下図の丸) の個数

は一致します (厳密には、ノード数は分岐数より 1 小さい)。よって、ありうるノードの個数を見積もれば、それがそのまま計算量となります!!!

f:id:drken1215:20200504175249p:plain

たとえば、上のテンプレ再帰関数では、

  • 各要素が  0, 1, \dots, M-1 であるような
  • 長さ  N の数列

を生成しました。このような数列は  M^{N} 通りあるので、計算量は  O(M^{N}) となります。

 

3. 応用

上記のテンプレは、大抵の全探索 DFS を実現できてしまう程度には強いです!具体的な問題をいくつか解いてみましょう。

問題 1: AtCoder ABC 165 C - Many Requirements

  •  1 \le A_{1} \le A_{2} \le \dots \le A_{N} \le M

という条件を満たす長さ  N の数列  A_{1}, \dots, A_{N} を考える。そのうち、以下のようにして定まるスコアの最大値を求めよ。

スコアは、 Q 個の条件のうち、満たすものについて加算されていく。

  •  i 個目の条件は、4 つの整数  a_{i}, b_{i}, c_{i}, d_{i} で与えられる
  • 数列  A が、 A_{b_{i}} - A_{a_{i}} = c_{i} を満たすならば、スコアに  d_{i} が加算される

制約

  •  N, M \le 10
  •  Q \le 50
  •  1 \le a_{i} \lt b_{i} \le M

解法

条件を満たすような数列  A を全探索することを考えてみましょう。 A_{1}, \dots, A_{N} のとりうる値は  1, 2, \dots, M なので、上で示したテンプレにとてもよく似ています!!!!!

ただし、 A_{1} \le A_{2} \le \dots \le A_{N} という条件を加味しなければなりません。でもこれは、次のコードのように、ちょっとした変更で実現することができます!!!

void dfs(vector<int> &A) {
    if (A.size() == N) {
        return;
    }

    int prev_last = (A.empty() ? 1 : A.back());
    for (int v = prev_last; v <= M; ++v) {
        A.push_back(v);
        dfs(A);
        A.pop_back();
    }
}
def dfs(A):
    if len(A) == N:
        print(A)
        return
    prev_last = A[-1] if len(A) > 0 else 1
    for v in range(prev_last, M+1):
        A.append(v)
        dfs(A)
        A.pop()

変わったのは for 文だけです。

  • v を  0 から  M-1 までの範囲で回す代わりに
  • v を (数列の前回の最後の値) から  M までの範囲で回す

という風に変更しています。このように、v を回す範囲を、「数列の前回の最後の値以上の範囲」に限ることで、「A が単調増加」という条件を上手に扱うことできています。

また注意点として、一番最初に関数 dfs を呼び出すときは、数列 A は空の状態です。このときだけは、A.back() (C++) や A[-1] (python) を呼び出してしまうと配列外参照になることに注意しましょう。

以上によって、条件を満たす数列 A を全て生成することができるので、それらに対してスコアを計算して、その最大値を出力すればよいです。

計算時間

なお、計算量が不安になるかもしれません。というのも、もし「数列 A が単調増加」という条件がなかったら、 O(M^{N}) となります。 10^{10} は流石に間に合いません。

しかし、「単調増加」という条件によって、想像以上に選択肢が減ります。ものすごくざっくりとした感覚で言うと、

  • 数列の長さが  2 なら、選択肢の個数はざっくり  \frac{1}{2} になる
  • 数列の長さが  3 なら、選択肢の個数はざっくり  \frac{1}{6} になる
  • 数列の長さが  4 なら、選択肢の個数はざっくり  \frac{1}{24} になる
  • 数列の長さが  5 なら、選択肢の個数はざっくり  \frac{1}{120} になる
  • ...
  • 数列の長さが  N なら、選択肢の個数はざっくり  \frac{1}{N!} になる

というくらいに選択肢が減ります。今回は具体的には、92378 通りになります。ちゃんとした詳しい求め方はアルメリアさんの記事に書いてあります。

解答例 (C++)

ここでは、0-indexed で実装しました (数列の値範囲を 1〜M から 0〜M-1 とした)

また、今まで再帰関数 dfs の返り値は void 型で実装していたが、今回は、以下のように、「スコアの最大値」を返すようにしました。

  • dfs(A): 数列 A に要素を付け加えてできる数列すべてについてのスコアの最大値

少しわかりにくいかもしれません。たとえば  A = (1, 3) のときは、 (1, 3, \dots) という形をした数列についてのスコアの最大値を求めることになります。これは具体的には、

  •  A = (1, 3, 3, \dots)
  •  A = (1, 3, 4, \dots)
  •  A = (1, 3, 5, \dots)
  • ...
  •  A = (1, 3, M-1, \dots)

についての dfs(A) の値をすべて求めて、その最大値をとることで求められます。最終的には、空配列 A = () に対して dfs(A) の値が、求める最大値になります。

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

// 入力
int N, M, Q;
vector<long long> a, b, c, d;

// 数列 A のスコアを計算
long long score(const vector<int> &A) {
    long long res = 0;
    for (int i = 0; i < Q; ++i) if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
    return res;
}

// 数列 A に要素を付け加えて行って、最終的にできる数列のうちの
// スコアの最大値を返す
// 特に、最初の呼出しに対する返り値が答え
long long dfs(vector<int> &A) {
    if (A.size() == N) {
        return score(A);
    }
    long long res = 0;
    int prev_last = (A.empty() ? 0 : A.back());
    for (int add = prev_last; add < M; ++add) {
        A.push_back(add);
        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);
    for (int q = 0; q < Q; ++q) {
        cin >> a[q] >> b[q] >> c[q] >> d[q];
        --a[q], --b[q];
    }
    vector<int> A;
    cout << dfs(A) << endl;
}

解答例 (Python)

Python なら、本当は itertools を使えば簡単に実現できます (maspyさんのコードなどを参照)。

しかしここでは C++ と同様の再帰関数で実装してみます。

# 入力
N, M, Q = map(int, input().split())
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

# スコア計算
def score(A):
    tmp = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A[ai] == ci:
            tmp += di
    return tmp

# DFS
def dfs(A):
    if len(A) == N:
        return score(A) # 数列 A のスコアを返す
    res = 0
    prev_last = A[-1] if len(A) > 0 else 0
    for v in range(prev_last, M):
        A.append(v)
        res = max(res, dfs(A)) # 再帰呼出しながら、スコア最大値も更新
        A.pop()
    return res

# 求める
print(dfs([]))

 

問題 2: AtCoder ABC 114 C - 755

10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶことにする。

整数  N が与えられて、 N 以下の 753 数が何個あるかを求めよ。

制約

  •  1 \le N \le 10^{9}

解法

 N 以下の 753 数をすべて列挙すれば OK!!!
これも、今までの実装テンプレをちょっと変えるだけで書くことができます。詳しくは以下の記事に書きました。

drken1215.hatenablog.com

 

問題 3: AtCoder ABC 161 D - Lunlun Number

1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。

 K 番目に小さいルンルン数を求めよ。

制約

  •  1 \le K \le 10^{5}

解法

最大の  K に対するルンルン数は 3234566667 になります (これはサンプルからわかる...し、概算で概ね見積ることもできる)。よって、10 桁以下のルンルン数を全列挙すれば求められます。詳しくは下の記事で。

drken1215.hatenablog.com