情画プロコン#1 プログラム解答例

サービス券
フィルタ
整理整頓
部分回文

ソースコードの動作確認は、ideoneで行いました。

ソースコードの言語はC++です。

Lv.1 サービス券

whileループ, 1回づつ計算版

#include <iostream>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int ans = 0;
    while(N >= M) {
        N += 1 - M;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

whileループ, まとめて計算版

#include <iostream>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int ans = 0;
    while(N >= M) {
        ans += N / M;
        N = N / M + N % M;
    }
    cout << ans << endl;
    return 0;
}

再帰版

#include <iostream>

using namespace std;

int solve(int N, int M) {
    if (N < M) return 0;
    return N / M + solve(N / M + N % M, M);
}

int main() {
    int N, M;
    cin >> N >> M;
    int ans = solve(N, M);
    cout << ans << endl;
    return 0;
}

Lv.2 フィルタ

解答

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> A;
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        A.push_back(temp);
    }

    vector<int> B;
    for (int i = 0; i < N; i++) {
        vector<int> target;
        for(int j = i - 1; j <= i + 1; j++) {
            if (j < 0 || j >= N) continue;
            target.push_back(A[j]);
        }
        sort(target.begin(), target.end());
        int targetN = target.size();
        int m;
        if (targetN % 2 == 0) {
            m = (target[targetN / 2 - 1] + target[targetN / 2]) / 2;
        } else {
            m = target[targetN / 2];
        }
        B.push_back(m);
    }

    for (int i = 0; i < N; i++) {
        cout << B[i] << " ";
    }
    cout << endl;

    return 0;
}

Lv.3 整理整頓

全探索版(深さ優先探索)

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;
vector<int> L;
int N, X;

bool dfs(int n) {
    if (n == 0) {
        int areaA = 0;
        int areaB = 0;
        for(int i = 0; i < N; i++) {
            if (arr[i] == 0) areaA += L[i]; else areaB += L[i];
        }
        if (areaA <= X && areaB <= X) {
            return true;
        } else {
            return false;
        }
    }
    bool result0, result1;
    arr.push_back(0); result0 = dfs(n - 1); arr.pop_back();
    if (result0) return true;
    arr.push_back(1); result1 = dfs(n - 1); arr.pop_back();
    return result1;
}

int main() {

    cin >> N >> X;

    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        L.push_back(temp);
    }
    bool possible = dfs(N);
    if (possible) {
        cout << "possible" << endl;
    } else {
        cout << "impossible" << endl;
    }
    return 0;
}

全探索版（シンプル再帰）

#include <iostream>
#include <vector>

using namespace std;

int N, X, S;
vector<int> L;

bool dfs(int n, int sum) {
    if (n == N) {
        if (sum <= X && S - sum <= X) return true;
        return false;
    }
    return dfs(n + 1, sum + L[n]) || dfs(n + 1, sum);
}

int main() {
    cin >> N >> X;
    S = 0;
    for(int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        L.push_back(temp);
        S += temp;
    }

    bool possible = dfs(0, 0);

    if (possible) {
        cout << "possible" << endl;
    } else {
        cout << "impossible" << endl;
    }

    return 0;
}

全探索版（ビット演算）

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int N, X;
    cin >> N >> X;

    vector<int> len;
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        sum += temp;
        len.push_back(temp);
    }

    for (int i = 0; i < 1 << N; ++i) {
        int areaA = 0;
        for (int j = 0; j < N; ++j) {
            if (i >> j & 1) {
                areaA += len[j];
            }
        }
        if (areaA <= X && (sum - areaA) <= X) {
            cout << "possible" << endl;
            return 0;
        }
    }
    cout << "impossible" << endl;
    return 0;
}

DP版

#include <iostream>
#include <vector>

using namespace std;

/* dp[i][j] := i番目のブロックまで考慮した場合、領域Aに入るブロックの横の長さの合計がjとなる選び方があるか
0 : 無い　1 : ある */
int dp[16][1001] = {{0}};

int main() {

    int N, X;
    cin >> N >> X;

    vector<int> len;
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        sum += temp;
        len.push_back(temp);
    }

    dp[0][0] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= X; ++j) {
            if (j - len[i] >= 0) {
                dp[i][j] |= dp[i - 1][j - len[i]];
            }
            dp[i][j] |= dp[i - 1][j];
            if (dp[i][j] && (sum - j <= X)) {
                cout << "possible" << endl;
                return 0;
            }
        }
    }
    cout << "impossible" << endl;
    return 0;
}

メモ化再帰版

#include <iostream>
#include <vector>

using namespace std;

int N, X, S;
vector<int> L;
int memo[16][1001] = {{0}};

bool dfs(int n, int sum) {
    if (memo[n][sum] == 1) return true;
    if (memo[n][sum] == -1) return false;
    if (sum > X) return false;

    if (n == N) {
        if (sum <= X && S - sum <= X) {
            memo[n][sum] = 1;
            return true;
        } else {
            memo[n][sum] = -1;
            return false;
        }
    }
    return dfs(n + 1, sum + L[n]) || dfs(n + 1, sum);
}

int main() {
    cin >> N >> X;
    S = 0;
    for(int i = 0; i < N; i++) {
        int temp;
        cin >> temp;
        L.push_back(temp);
        S += temp;
    }

    bool possible = dfs(0, 0);

    if (possible) {
        cout << "possible" << endl;
    } else {
        cout << "impossible" << endl;
    }

    return 0;
}

Lv.4 部分回文

部分点解答（150点：全探索）

#include <string>
#include <iostream>

using namespace std;

string S(1000, ' ');
int N;

int isKaibun(string &target) {
    int n = target.size();
    for(int i = 0; i <= n / 2; i++) {
        if (target[i] != target[n - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int isNotBubunKaibun(string &target) {
    int ret = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j > i; --j) {
            string t = target.substr(i, j - i + 1);
            ret |= isKaibun(t);
        }
    }
    return !ret;
}

int dfs(int n, string &nowString) {
    if (n >= N) return isNotBubunKaibun(nowString);
    if (S[n] != '*') {
        nowString[n] = S[n];
        return dfs(n + 1, nowString);
    }
    int ret = 0;
    for (int i = 1; i <= 9; ++i) {
        nowString[n] = '0' + i;
        ret += dfs(n + 1, nowString);
        ret %= 1000000007;
    }
    nowString[n] = ' ';
    return ret;
}

int main(int argc, char const *argv[]) {
    cin >> S;
    N = S.length();
    string nowString(N, ' ');
    cout << dfs(0, nowString) << endl;
    return 0;
}

部分点解答（210点：全探索、判定を工夫）

#include <string>
#include <iostream>

using namespace std;

string S(1000, ' ');
int N;

int isNotBubunKaibun(string &target) {
    for (int i = 1; i < N; ++i) {
        if (i >= 2 && target[i - 2] == target[i]) return 0;
        if (target[i - 1] == target[i]) return 0;
    }
    return 1;
}

int dfs(int n, string &nowString) {
    if (n >= N) return isNotBubunKaibun(nowString);
    if (S[n] != '*') {
        nowString[n] = S[n];
        return dfs(n + 1, nowString);
    }
    int ret = 0;
    for (int i = 1; i <= 9; ++i) {
        nowString[n] = '0' + i;
        ret += dfs(n + 1, nowString);
        ret %= 1000000007;
    }
    nowString[n] = ' ';
    return ret;
}

int main(int argc, char const *argv[]) {
    cin >> S;
    N = S.length();
    string nowString(N, ' ');
    cout << dfs(0, nowString) << endl;
    return 0;
}

満点解法（通常DP版）

#include <iostream>
#include <string>
#define MOD 1000000007

using namespace std;

/* dp[i][j][k] := k文字目まで考慮したとき、k - 1文字目に当てはめた数字がi, 
k文字目に当てはめた数字がjであるときの「部分回文でない」順列の数. */
int dp[10][10][1000] = {{{0}}};
string str;

inline void add(int ind, int a, int b, int value) {
    if (str[ind] == '*' || str[ind] == b + '0') {
        dp[a][b][ind] += value;
        dp[a][b][ind] %= MOD;
    }
}

int main() {
    cin >> str;
    int n = str.size();

    for(int b = 1; b < 10; b++) {
        add(0, 0, b, 1);
    }
    for(int k = 0; k < n - 1; k++) {
        for(int a = 0; a < 10; a++) {
            for(int b = 1; b < 10; b++) {
                for(int c = 1; c < 10; c++) {
                    if (b == c || a == c) continue;
                    add(k + 1, b, c, dp[a][b][k]);
                }
            }
        }
    }

    int ans = 0;
    for(int a = 0; a < 10; a++) {
        for(int b = 0; b < 10; b++) {
            ans += dp[a][b][n - 1];
            ans %= MOD;
        }
    }

    cout << ans << endl;

    return 0;
}

満点解法（省メモリDP版）

#include <iostream>
#include <string>
#define MOD 1000000007

using namespace std;

/* dp[i][j][k] := k文字目まで考慮したとき、k - 1文字目に当てはめた数字がi, 
k文字目に当てはめた数字がjであるときの「部分回文でない」順列の数.
ただしkは0か1のみをつかい、配列の領域をリサイクルして使う。 */

int dp[10][10][2] = {{{0}}};
string str;

inline void add(int ind, int a, int b, int value) {
    if (str[ind] == '*' || str[ind] == b + '0') {
        dp[a][b][ind % 2] += value;
        dp[a][b][ind % 2] %= MOD;
    }
}

int main() {
    cin >> str;
    int n = str.size();

    for(int b = 1; b < 10; b++) {
        add(0, 0, b, 1);
    }
    for(int k = 0; k < n - 1; k++) {
        for(int a = 0; a < 10; a++) {
            for(int b = 1; b < 10; b++) {
                for(int c = 1; c < 10; c++) {
                    if (b == c || a == c) continue;
                    add(k + 1, b, c, dp[a][b][k % 2]);
                }
                dp[a][b][k % 2] = 0;
            }
        }
    }

    int ans = 0;
    for(int a = 0; a < 10; a++) {
        for(int b = 0; b < 10; b++) {
            ans += dp[a][b][(n - 1) % 2];
            ans %= MOD;
        }
    }

    cout << ans << endl;

    return 0;
}

満点解法（メモ化再帰版）

#include <iostream>
#include <string>

#define MOD 1000000007

using namespace std;

string str;
int N;
int memo[10][10][1000];

/* 先頭からk個目がk個目がj、k-1個目がiで確定し、
残された部分に数字を入れて作れる部分回文でない文字列の数を返す */
int dfs(int i, int j, int k) {
    if (memo[i][j][k] != -1) return memo[i][j][k];
    if (k == N - 1) return memo[i][j][k] = 1;

    int ret = 0;
    for(int l = 1; l < 10; l++) {
        if (i == l || j == l) continue;
        if (str[k + 1] != '*' && str[k + 1] != '0' + l) continue;
        ret += dfs(j, l, k + 1);
        ret %= MOD;
    }
    return memo[i][j][k] = ret;
}

int main() {

    cin >> str;
    N = str.size();
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            for(int k = 0; k < 1000; k++) {
                memo[i][j][k] = -1;
            }
        }   
    }

    int ans = 0;
    for(int j = 1; j < 10; j++) {
        if (str[0] != '*' && str[0] != '0' + j) continue;
        ans += dfs(0, j, 0);
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;   
}