0000 から 9999 までの \(10^4\) 通りの暗証番号それぞれについて高橋くんの記憶に合致するかを判定し、合致するものの個数を数えることでこの問題を解くことができます。

実装の際は、0000 から 9999 までの暗証番号を「\(0\) 以上 \(9999\) 以下の整数に leading zero を付けたもの」と見做すことで簡潔なコードを書くことができます。例えば、\(1\) に leading zero を付けて生成される暗証番号は 0001, \(132\) に leading zero を付けて生成される暗証番号は 0132 です。

計算量は \(M=10^4\) として \(O(M|S|)\) となります。

解答例 (C++)

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

int main(){
    string S; cin >> S;
    int ans = 0;
    for(int i=0; i<=9999; i++){
        vector<bool> flag(10);
        int X = i;
        for(int j=0; j<4; j++){
            flag[X%10] = true;
            X /= 10;
        }
        bool flag2 = true;
        for(int j=0; j<10; j++){
            if(S[j]=='o' && !flag[j]) flag2 = false;
            if(S[j]=='x' && flag[j]) flag2 = false;
        }
        ans += flag2;
    }
    cout << ans << endl;
}

解答例 (Python)

S = input()
ans = 0
for i in range(10000):
    flag = [False]*10
    now = i
    for j in range(4):
        flag[now%10] = True
        now //= 10
    flag2 = True
    for j in range(10):
        if S[j] == 'o' and not flag[j]:
            flag2 = False
        if S[j] == 'x' and flag[j]:
            flag2 = False
    ans += flag2
print(ans)