ICPC国内予選2016 A~D

• A

全探索

#include <bits/stdc++.h>

using namespace std;

#define INF (1<<29)

int main()
{
    int N;
    while (cin >> N, N) {
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
            cin >> a[i];
        }
        int res = INF;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                res = min(res, abs(a[i] - a[j]));
            }
        }
        cout << res << endl;
    }
    return 0;
}

• B

シミュレーション
上位2位の情報を比較する

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    while (cin >> N, N) {
        vector<int> cnt(26, 0);
        vector<char> ch(N);
        for (int i = 0; i < N; i++) {
            cin >> ch[i];
        }
        
        int mn = -1, mx = 0;
        bool found = 0;        
        for (int i = 0; i < N; i++) {
            int n = ch[i] - 'A';
            cnt[n]++;
            if (mx < cnt[n]) {
                mx = cnt[n];
                mn = n;
            }
                
            int mx2 = 0;
            for (int j = 0; j < 26; j++) {
                if (j == mn) continue;
                mx2 = max(mx2, cnt[j]);
            }
            if (mx2 + (N - i - 1) < mx) {
                found = 1;
                cout << (char)(mn + 'A') << " " << i + 1 << endl;
                break;
            }
        }
        if (!found) {
            cout << "TIE" << endl;
        }
    }
    return 0;
}

• C

エラトステネスの篩っぽくやる
最大ケースは問題文に書いてある

#include <bits/stdc++.h>

using namespace std;

#define LIMIT 7368791

bool used[LIMIT+1];

int main()
{
    int m, n;
    while (cin >> m >> n, m) {
        int cnt = 0;
        memset(used, 0, sizeof(used));
        for (int i = m; cnt < n; i++) {
            if (!used[i]) {
                cnt++;
                for (int j = i; j <= LIMIT; j += i) {
                    used[j] = 1;
                }
            }
        }
        for (int i = m; ; i++) {
            if (!used[i]) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

• D

区間DPをやる。

#include <bits/stdc++.h>

using namespace std;

#define MAX 334
#define INF (1<<29)

int memo[MAX][MAX];
vector<int> w;

int rec(int L, int R)
{
    int &res = memo[L][R];
    if (res != -1) return res;
    if (L >= R) return (res = 0);
    res = -INF;
    
    if (abs(w[L] - w[R]) <= 1) {
        int r = rec(L + 1, R - 1);
        if (r == (R - 1) - (L + 1) + 1) {
            res = max(res, r + 2);
        }
    }
    
    for (int i = L; i <= R; i++) {
        res = max(res, rec(L, i) + rec(i+1, R));
    }   
    return res;
}

int main()
{
    int N;
    while (cin >> N, N) {
        w.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> w[i];
        }
        
        memset(memo, -1, sizeof(memo));
        cout << rec(0, N-1) << endl;
    }
    return 0;
}