Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

paiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」
@shoji127

十億連勝 (paizaランク S 相当)を考察する

Posted at

十億連勝 (paizaランク S 相当)を考察する

paiza×Qiitaコラボキャンペーン ということで
十億連勝 (paizaランク S 相当)
を題材に、アルゴリズムの改善について考察してみたいと思います。

まずは問題文通りに実装する

この問題のように組み合わせに対する処理を行う場合は、大きく2通りあるかと思います。

  1. 再帰処理を行う
    再帰処理を行う場合一般的には深さ優先探索となります。

  2. ループで行う
    一般的には幅優先探索となります。

説明だけだとわかりづらいので、まずは問題文通りのアルゴリズムをそれぞれの方法でC言語で実装してみます。

既に動くものからチューニングを行っていくと、正解がわかっている状態でチューニングができるのでデグレードを起こしにくくなります。デバッグも入れて処理の流れも見られるようにしておきます。

(ただし入力が大きいデータの場合、このバージョンでは動作しないので注意)

確認用の入力データとして、非常に小さいデータセットを用意します。

3 3
2
1
2

再帰を使った実装(アルゴリズムは問題文通り)

#include <stdio.h>

static void doit(int n, int win, int max, int N, int X, int A[], int *count){
    int i;
    printf("%*d win=%d max=%d%s\n", n*3, n, win, max, n==N&&max==X?"*":"");

    if (n >= N){
        if (max == X){
            *count += 1; //maxがちょうどXのものだけ対象
        }
        return;
    }

    for (i = 0; i < A[n]; i++, win++){
        doit(n + 1, 0, win > max ? win : max, N, X, A, count); //負けの再帰
    }
    doit(n + 1, win, win > max ? win : max, N, X, A, count);   //勝ちの再帰
}

int main(void)
{
    int i, N, X, A[4000], count;

    /* 入力データ取得 */
    fscanf(stdin, "%d %d", &N, &X);
    for (i = 0; i < N; i++){
        fscanf(stdin, "%d", &A[i]);
    }

    doit(0, 0, 0, N, X, A, &count);
    printf("%d\n", count);
}

入力データを使って実行すると次のような出力になります。

0 win=0 max=0
  1 win=0 max=0
     2 win=0 max=0
        3 win=0 max=0
        3 win=0 max=1
        3 win=2 max=2
     2 win=1 max=1
        3 win=0 max=1
        3 win=0 max=2
        3 win=3 max=3*
  1 win=0 max=1
     2 win=0 max=1
        3 win=0 max=1
        3 win=0 max=1
        3 win=2 max=2
     2 win=1 max=1
        3 win=0 max=1
        3 win=0 max=2
        3 win=3 max=3*
  1 win=2 max=2
     2 win=0 max=2
        3 win=0 max=2
        3 win=0 max=2
        3 win=2 max=2
     2 win=3 max=3
        3 win=0 max=3*
        3 win=0 max=4
        3 win=5 max=5
3

出力からも再帰処理を使う場合は深さ優先探索になっていることがわかると思います。

ループを使った実装(アルゴリズムは問題文通り)

#include <stdio.h>

int main(void)
{
    int N, X, A[4000], i, j, k, ndata, n, count;
    struct {
        int win;    /* 現在の連勝数 */
        int max;    /* これまでの最大連勝数 */
    } d1[100000], d2[100000], *data = d1, *next = d2;

    /* 入力データ取得 */
    fscanf(stdin, "%d %d", &N, &X);
    for (i = 0; i < N; i++){
        fscanf(stdin, "%d", &A[i]);
    }

    data[0].win = data[0].max = 0, ndata = 1; //初期データ
    for (i = 0; i < N; i++){
        for (j = 0, n = 0; j < ndata; j++){
            int win = data[j].win, max = data[j].max;

            printf("%*d win=%d max=%d\n", i*3, i, win, max);
            for (k = 0; k < A[i]; k++, win++){
                next[n].win = 0, next[n++].max = win > max ? win : max; //負けデータ
            }
            next[n].win = win, next[n++].max = win > max ? win : max;   //勝ちデータ
        }
        next = data, data = next == d1 ? d2 : d1, ndata = n; /* 配列の入れ替え */
    }
    for (i = 0, count = 0; i < ndata; i++){
        printf("%*d win=%d max=%d%s\n", N*3, N, data[i].win, data[i].max, data[i].max==X?"*":"");
        if (data[i].max == X){
            count++;
        }
    }
    printf("%d\n", count);
}

jのループが組み合わせを処理するためのループです。

ループごとに組み合わせを処理するためのデータを準備し、処理した結果をまた次のデータとして準備しています。

入力のデータを使って実行すると次のような出力になります。

0 win=0 max=0
  1 win=0 max=0
  1 win=0 max=1
  1 win=2 max=2
     2 win=0 max=0
     2 win=1 max=1
     2 win=0 max=1
     2 win=1 max=1
     2 win=0 max=2
     2 win=3 max=3
        3 win=0 max=0
        3 win=0 max=1
        3 win=2 max=2
        3 win=0 max=1
        3 win=0 max=2
        3 win=3 max=3*
        3 win=0 max=1
        3 win=0 max=1
        3 win=2 max=2
        3 win=0 max=1
        3 win=0 max=2
        3 win=3 max=3*
        3 win=0 max=2
        3 win=0 max=2
        3 win=2 max=2
        3 win=0 max=3*
        3 win=0 max=4
        3 win=5 max=5
3

出力からもループを使う場合は幅優先探索になっていることがわかると思います。

問題文のアルゴリズムの計算量を考察する

サンプルプログラムを見てもわかる通り、問題文のアルゴリズム通りに処理を行うと一つの階層で、

  • 途中で負けるパターン ... A[n]回
  • すべて勝つパターン ... 1回

の計A[n]+1の処理が行われます。

それが階層ごとに積算されていくため、総パターン数は指数関数的に増大します。

例えば、問題文にある入力例3の場合

(8+1)×(5+1)×(9+1)×(7+1)×(6+1)×(9+1)×(0+1)×(9+1)×(8+1)×(2+1)×(8+1)×(1+1)×(4+1)×(10+1) = 80831520000

となり、ループ版だと動作できません。

※スタック上に配列は持てないですし、ヒープからもこのサイズを取ってくることは難しいでしょう

再帰版だと動作はするのですが、10分くらいかかります。

今回の題材では

・1 ≦ N ≦ 4,000
・0 ≦ X ≦ 1,000,000,000
・0 ≦ A_i ≦ 1,000,000,000 (1 ≦ i ≦ N)

とあるので、問題文通りの実装ではデータによっては動作しないということになります。

アルゴリズムを改良する(その1)

それではアルゴリズムを改良していきたいと思います。

基本的な考えは問題文の解釈を変えて計算量を減らすということです。

もういちど問題文を見てみます。

問題文(抜粋)

最大の連勝数がちょうど X だった場合、ボーナスステージが出現する

  • 連勝数がXを超えた場合はボーナスステージが出現しないことが確定する

    そのケース以降は計算不要

  • 負けのパターンは連勝数がXを越えなければ、連勝数が0に戻る
    いちいちループして調べる必要はなく

    • どこで負けても連勝数が超えない場合
      すべて同一ケースとしてまとめることができる

    • どこかで超える場合
      超えるまでは同一ケースとしてまとめることができる
      ちょうどXの場合は、ボーナスステージが(この時点では)確定する
      超えた場合は、計算不要

  • 勝ちのパターンは連勝数がXを超える場合は、負け確定なのその場合は以降の計算不要

というアルゴリズムに変更すれば、計算量が減らせそうです。

再帰を使った実装(問題文の解釈を変更しアルゴリズム改良1)

#include <stdio.h>

static void doit(int n, int win, int match, int ncase, int N, int X, int A[], int *count){
    printf("%*d win=%d ncase=%d%s\n", n*3, n, win, ncase, n==N&&match?"*":"");

    if (n >= N){
        if (match){
            *count += ncase; //条件にマッチしたケース数を加算
        }
        return;
    }

    /* 負け */
    if (A[n] + win <= X){
        doit(n + 1, 0, match, ncase * A[n],  N, X, A, count); //すべて負けてもOK
    } else {
        if (X - win > 0){
            doit(n + 1, 0, match, ncase * (X - win),  N, X, A, count); //ここまではOK
        }
        doit(n + 1, 0, 1, ncase, N, X, A, count); //条件にマッチ
    }

    /* 勝ち */
    if (A[n] + win == X){
        doit(n + 1, X, 1,            ncase,  N, X, A, count);
    } else if (A[n] + win < X){
        doit(n + 1, A[n]+win, match, ncase,  N, X, A, count);
    }
}

int main(void)
{
    int i, N, X, A[4000], count;

    /* 入力データ取得 */
    fscanf(stdin, "%d %d", &N, &X);
    for (i = 0; i < N; i++){
        fscanf(stdin, "%d", &A[i]);
    }

    doit(0, 0, 0, 1, N, X, A, &count);
    printf("%d\n", count);
}

ケース数は前のデータからの積算になります。

また、マッチしないことが確定したケースについては再帰呼び出しを行っておりません。

入力データを実行すると次のような結果になります。

0 win=0 ncase=1
  1 win=0 ncase=2
     2 win=0 ncase=2
        3 win=0 ncase=4
        3 win=2 ncase=2
     2 win=1 ncase=2
        3 win=0 ncase=4
        3 win=3 ncase=2*
  1 win=2 ncase=1
     2 win=0 ncase=1
        3 win=0 ncase=2
        3 win=2 ncase=1
     2 win=3 ncase=1
        3 win=0 ncase=1*
3

ケースが集約されたことが確認できます。

ループを使った実装(問題文の解釈を変更しアルゴリズム改良1)

#include <stdio.h>

int main(void)
{
    int N, X, A[4000], i, j, ndata, n, count;
    struct {
        int win;    /* 現在の連勝数 */
        int match;  /* 0:未確定 1:確定 */
        int ncase;  /* 該当ケース */
    } d1[100000], d2[100000], *data = d1, *next = d2;

    /* 入力データ取得 */
    fscanf(stdin, "%d %d", &N, &X);
    for (i = 0; i < N; i++){
        fscanf(stdin, "%d", &A[i]);
    }

    data[0].win = data[0].match = 0, data[0].ncase = ndata = 1; //初期データ
    for (i = 0; i < N; i++){
        for (j = 0, n = 0; j < ndata; j++){
            int win = data[j].win, match = data[j].match, ncase = data[j].ncase;

            printf("%*d win=%d ncase=%d%s\n", i*3, i, win, ncase, match?"*":"");
            if (A[i] + win <= X){
                next[n].win = 0, next[n].match = match, next[n++].ncase = ncase * A[i];
            } else {
                if (X - win > 0){
                    next[n].win = 0, next[n].match = match, next[n++].ncase = ncase * (X - win);
                }
                next[n].win = 0, next[n].match = 1, next[n++].ncase = ncase;
            }
            if (A[i] + win == X ){
                next[n].win = X, next[n].match = 1, next[n++].ncase = ncase;
            } else if (A[i] + win < X) {
                next[n].win = A[i] + win, next[n].match = match, next[n++].ncase = ncase;
            }
        }
        next = data, data = next == d1 ? d2 : d1, ndata = n; /* 配列の入れ替え */
    }
    for (i = 0, count = 0; i < ndata; i++){
        printf("%*d win=%d ncase=%d%s\n", N*3, N, data[i].win, data[i].ncase, data[i].match?"*":"");
        if (data[i].match){
            count += data[i].ncase;
        }
    }
    printf("%d\n", count);
}

こちらも入力データを使って実行してみます。

0 win=0 ncase=1
  1 win=0 ncase=2
  1 win=2 ncase=1
     2 win=0 ncase=2
     2 win=1 ncase=2
     2 win=0 ncase=1
     2 win=3 ncase=1*
        3 win=0 ncase=4
        3 win=2 ncase=2
        3 win=0 ncase=4
        3 win=3 ncase=2*
        3 win=0 ncase=2
        3 win=2 ncase=1
        3 win=0 ncase=1*
3

改良されたアルゴリズムの計算量を考察する

問題文通りのアルゴリズムに比べ計算量は減っているようですが、今回のお題の最大に耐えられるのかを検討してみたいともいます。

改良アルゴリズムでは

  • 負けのパターンの場合
    最大2ケース

  • 勝ちのパターンの場合
    最大1ケース

となっており、それぞれのラウンドで最大3ケースが考えられます。
確認用の入力データはラウンド数が3なので、最悪のケースとしては

3×3×3 = 27

になりますが、7ケースなので、おおよそ2のN乗

2×2×2 = 8

と考えると、Nが最大4000であるため、この改良版でも依然要件を満たさないことになります。

試しに問題文にある入力例3(ラウンド数14)をこのプログラムで実行すると

ケース数は12288でした。2の14乗が16384なので、おおよそ2のN乗と言ってよさそうです。

改良前のアルゴリズムでは80831520000ケースだったのでそれに比べると劇的に改善はしていますが、

30ラウンドがせいぜいでしょう。

アルゴリズムを改良する(その2)

それでは、さらなるチューニングをしていきたいと思います。

ケース数が前のラウンドの積算になると指数関数的に増えてしまうため、ラウンド毎にケース数を集約したほうがよさそうです。

これは入力例3のデータの実行結果の抜粋です。

                                     13 win=0 ncase=67184640
                                     13 win=4 ncase=16796160
                                     13 win=0 ncase=67184640
                                     13 win=5 ncase=16796160
                                     13 win=0 ncase=11197440*
                                     13 win=4 ncase=2799360*
                                     13 win=0 ncase=11197440*
                                     13 win=5 ncase=2799360*
                                     13 win=0 ncase=22394880
                                     13 win=4 ncase=5598720
                                     13 win=0 ncase=22394880
                                     13 win=5 ncase=5598720
                                     13 win=0 ncase=5598720*
                                     13 win=4 ncase=1399680*
                                     13 win=0 ncase=5598720*
                                     13 win=5 ncase=1399680*
                                     13 win=0 ncase=11197440*
                                     13 win=4 ncase=2799360*
                                     13 win=0 ncase=11197440*
                                     13 win=5 ncase=2799360*
                                     13 win=0 ncase=1866240*

これを見ると、各ケースは次のパターンになることがわかります。

  1. 連勝が続いているパターン

    前のラウンドからだけでなく、その前からのラウンドからも持ち越している可能性がある。
    連勝の数の種別は、最初のラウンドからすべて勝っていた場合を考慮してもたかだかN種類である。
    ただし、確定と未確定の2パターンがあるため、最大N×2である

  2. 連勝が0にリセットされているパターン
    確定した場合と、未確定の場合の2パターンのみである

そのため、ラウンド毎にケースを集約すれば、各ラウンドの計算量のオーダーはNで、全ラウンドの計算量はN×Nで収まりそうです。

配列数もNのオーダーで済みそうなので、Nの最大が4000の計算量は
4000×4000 = 16000000なので、このアルゴリズムであればNが最大の場合でも大丈夫そうです。

ただし、ラウンド毎に集約するためには、幅優先探索の実装である必要があります。
(深さ優先探索ではラウンド毎にすべてのケースを計算しないため)
そのため、ここで再帰をあきらめて、ループでの実装のみで進めることにします。

ループを使った実装(ラウンド毎にケースを集約)

#include <stdio.h>

struct round{
    int win;    /* 現在の連勝数 */
    int match;  /* 0:未確定 1:確定 */
    int ncase;  /* 該当ケース */
};

static int regist_data(struct round data[], int ndata, int win, int match, int ncase){
    int i;
    for (i = 0; i < ndata; i++ ){
        if (data[i].win == win && data[i].match == match){
            data[i].ncase += ncase;
            return ndata;
        }
    }
    data[ndata].win = win, data[ndata].match = match, data[ndata++].ncase = ncase;
    return ndata;
}

int main(void)
{
    int N, X, A[4000], i, j, ndata, n, count;
    struct round d1[100000], d2[100000], *data = d1, *next = d2;

    /* 入力データ取得 */
    fscanf(stdin, "%d %d", &N, &X);
    for (i = 0; i < N; i++){
        fscanf(stdin, "%d", &A[i]);
    }

    data[0].win = data[0].match = 0, data[0].ncase = ndata = 1; //初期データ
    for (i = 0; i < N; i++){
        for (j = 0, n = 0; j < ndata; j++){
            int win = data[j].win, match = data[j].match, ncase = data[j].ncase;

            printf("%*d win=%d ncase=%d%s\n", i*3, i, win, ncase, match?"*":"");
            if (A[i] + win <= X){
                n = regist_data(next, n, 0, match, ncase * A[i]);
            } else {
                if (X - win > 0){
                    n = regist_data(next, n, 0, match, ncase * (X - win));
                }
                n = regist_data(next, n, 0, 1, ncase);
            }
            if (A[i] + win == X ){
                n = regist_data(next, n, X, 1, ncase);
            } else if (A[i] + win < X) {
                n = regist_data(next, n, A[i] + win, match, ncase);
            }
        }
        next = data, data = next == d1 ? d2 : d1, ndata = n; /* 配列の入れ替え */
    }
    for (i = 0, count = 0; i < ndata; i++){
        printf("%*d win=%d ncase=%d%s\n", N*3, N, data[i].win, data[i].ncase, data[i].match?"*":"");
        if (data[i].match){
            count += data[i].ncase;
        }
    }
    printf("%d\n", count);
}

こちらも入力データを使って実行してみます。

0 win=0 ncase=1
  1 win=0 ncase=2
  1 win=2 ncase=1
     2 win=0 ncase=3
     2 win=1 ncase=2
     2 win=3 ncase=1*
        3 win=0 ncase=10
        3 win=2 ncase=3
        3 win=3 ncase=2*
        3 win=0 ncase=1*
3

regist_dataの既に登録済みの探索が線形処理となっているため、ここはボトルネックになりそうです。

他の言語のようにMapが使えると性能が向上しそうですが、C言語では自前の実装になってしまうため、今回はこれで良しとしておきます。

一番厳しいN=4000もこのプログラムでは実行できるため一応完成です。

最終ソース

お題にある下9桁のみ出力やデバッグを取り除いた最終ソースは次の通りです。

#include <stdio.h>

struct round{
    int win;     /* 現在の連勝数 */
    int match;   /* 0:未確定 1:確定 */
    long long ncase; /* 該当ケース */
};

static int regist_data(struct round data[], int ndata, int win, int match, long long ncase){
    int i;
    for (i = 0; i < ndata; i++ ){
        if (data[i].win == win && data[i].match == match){
            data[i].ncase = (data[i].ncase + ncase)%1000000000LL;
            return ndata;
        }
    }
    data[ndata].win = win, data[ndata].match = match, data[ndata++].ncase = ncase;
    return ndata;
}

int main(void)
{
    int N, X, A[4000], i, j, ndata, n;
    struct round d1[100000], d2[100000], *data = d1, *next = d2;
    long long count = 0LL;

    /* 入力データ取得 */
    fscanf(stdin, "%d %d", &N, &X);
    for (i = 0; i < N; i++){
        fscanf(stdin, "%d", &A[i]);
    }
    
    data[0].win = data[0].match = 0, data[0].ncase = ndata = 1; //初期データ
    for (i = 0; i < N; i++){
        for (j = 0, n = 0; j < ndata; j++){
            int win = data[j].win, match = data[j].match;
            long long ncase = data[j].ncase;

            if (A[i] + win <= X){
                n = regist_data(next, n, 0, match, (ncase * A[i])%1000000000LL);
            } else {
                if (X - win > 0){
                    n = regist_data(next, n, 0, match, (ncase * (X - win))%1000000000LL);
                }
                n = regist_data(next, n, 0, 1, ncase);
            }
            if (A[i] + win == X ){
                n = regist_data(next, n, X, 1, ncase);
            } else if (A[i] + win < X) {
                n = regist_data(next, n, A[i] + win, match, ncase);
            }
        }
        next = data, data = next == d1 ? d2 : d1, ndata = n; /* 配列の入れ替え */
    }
    for (i = 0; i < ndata; i++){
        if (data[i].match){
            count = (count + data[i].ncase)%1000000000LL;
        }
    }
    printf("%lld\n", count);
}

考察

一番厳しいN=4000の次のようなデータを実行してみました。

4000 1000000000
1250000
...
...
1250000

800ラウンド連勝を続けると条件にマッチするため、非常に多くのパターンが考えられます。

最終ソースで確認したところ、実行時間は15秒ほどで実行結果は995000001でした。

ただし、これは1000000000のModを取っているため、実際のところ何ケースあったかはわかりません。

せっかくなので、最後に何ケースあったかを確認してみることにします。

C言語を改修して確認してみたいとところなのですが、C言語は言語仕様的に64bitまでの整数しか扱えず、

それを超える場合は、外部ライブラリを使用する必要があります。

(例えばPythonが使用しているlibmpdec等)

その改修を入れるとソースがやや複雑になってしまうので、アルゴリズムは変えずにそのままPythonで実装してみることにします。

Pythonは言語仕様として整数にほぼ制限がありません。ただし4300桁以上の文字列変換はガードがかかっているため解除します。

ついでにC言語版の登録済みの探索のところを辞書に置き換えることで自動的にボトルネックも解消です。

マッチするケースを1000000000のModをせずに出力(Python版)

import sys
from collections import defaultdict

sys.set_int_max_str_digits(0) #4300桁以上を文字列変換できるようにする

X = int(input().split()[1])
A = [int(i) for i in sys.stdin.read().split()]

data = {(0, False):1} #初期データ
for a in A:
    next_data = defaultdict(int)
    for (win, match), ncase in data.items():

        if a + win <= X:
            next_data[(0, match)] += (ncase * a)
        else:
            if X - win > 0:
                next_data[(0, match)] += (ncase * (X - win))
            next_data[(0, True)] += ncase

        if a + win == X:
            next_data[(X, True)] += ncase
        elif a + win < X:
            next_data[(a + win, match)] += ncase

    data = next_data #データの入れ替え

print(sum([ncase for (_, match), ncase in data.items() if match]))

Pythonで実装して思うのは、Pythonの簡潔性、生産性の高さです。

この単純なプログラムですら、C言語版の半分以下のコードで書けることに驚きです。

さっそく実行してみると、ケース数はなんと19511桁もありました。

13009585033186439831576729889860....034415629995000001

最後に

paiza×Qiitaコラボキャンペーン ということで
十億連勝 (paizaランク S 相当)
を題材に、アルゴリズムの改善について考察してみましたが、改めていろいろ考える機会を得られました。

すばらしい題材を提供していただいたpaiza様とQiita様に感謝しつつ終わりにしたいと思います。

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?