AtCoder 三井住友信託銀行プログラミングコンテスト2019 D問題

Question

前提・実現したいこと

AtCoder 三井住友信託銀行プログラミングコンテスト2019 D問題についての質問です。
問題文のURLは以下です。
D - Lucky PIN

0から999まで全探索をすれば解けることがわかりましたが、以下のようなコードを書いてTLEが出てしまいました。isContainPIN()を使えば以下のようなTLEが出力され、解説を見て、試しに以下のisContainPIN2()関数を作成し、これを使えばACとなりました。

考え方は同じように書いたつもりでしたが、どこでこのような違いが発生してしまっているのでしょうか。

お教え頂ければ幸いです。よろしくお願いいたします。

発生している問題・エラーメッセージ

・isContainPIN()を使用したとき

・isContainPIN2()を使用したとき

該当のソースコード

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
using namespace std;

bool isContainPIN(int64_t first,int64_t second, int64_t third , int64_t n, string s){
    REP(i, n - 2){
        if(s[i] - '0'== first){
            REP3(j, i + 1 ,n - 1){
                if(s[j] - '0' == second){
                    REP3(k, j + 1, n){
                        if(s[k] - '0' == third){
                            return true;
                        }
                    }
                }
            }
        }
    }
    return false;
}

bool isContainPIN2(int64_t first,int64_t second, int64_t third , int64_t n, string s){
    int64_t c[3] = {first, second, third};
    int64_t f = 0;
    REP(i, n){
        if(s[i] - '0'== c[f])f++;
        if(f == 3) return true;
    }
    return false;
}

int64_t solve(int64_t n, string s) {
    int64_t ans = 0;
    REP(i, 10){
        REP(j, 10){
            REP(k, 10){
                if(isContainPIN(i, j, k, n, s))ans++;
            }
        }
    }
    return ans;
}

int main() {
    int64_t N;
    string S;
    cin >> N >> S;
    auto ans = solve(N, S);
    cout << ans << endl;
    return 0;
}

試したこと

上記のように、２つのisContainPIN関数を用意し、比較を行いました。明らかに実行速度に差が出ているのがわかり、アルゴリズムが違うのだと推測します。

補足情報（FW/ツールのバージョンなど）

特にありません。
共有する情報が不足している等ございましたら、ご指摘いただけると幸いです。よろしくお願いいたします。

Answer 1

isContainPINで"111111111...11"から"112"を探す場合を考えてみてください

(s[i] - '0'== first)
(s[j] - '0' == second)
(s[k] - '0' == third)

このうち最初二つは必ずtrueで最後は必ずfalseなのでこう書き換えることができます。

    REP(i, n - 2){
        REP3(j, i + 1 ,n - 1){
            REP3(k, j + 1, n){
                //pass
            }
        }
    }
    return false;

isContainPIN2がループ1つなのにしたいして、こちらは3重ループですから相当遅くなります。

Comments

[bonjiri____]

ご回答いただきありがとうございます。
理解できました、この書き方だとtrueが一つでもあった場合それ以降の桁も探索してしまうのですね
試しにk == n - 1のときに3重ループを抜けるよう修正するとACとなりました
ただこの場合だとそもそも3重ループである必要がありませんね。順に線形探索すればよいだけなので、意識的にisContainPIN2を書けるように頑張っていきます。