AGC004

AtCoder Grand Contest 004 - AtCoder Grand Contest 004 | AtCoder
A,Bはすぐ解けたんですが、結局その後一問も解けず……。
公式の解説があるコンテストなのでメモ書き程度に。
A
図を見てるとなんかわかる。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

int main() {
    i64 a[3];
    rep(i, 3) cin >> a[i];
    rep(i, 3) {
        if(a[i] % 2 == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    i64 mi = 1.0e18 + 1LL;
    rep(i, 3) rep(j, 3) {
        if(i == j) continue;
        mi = min(mi, a[i] * a[j]);
    }
    cout << mi << endl;
    return 0;
}

B
dp[i][j] := j回移動させたときのiまでの合計の最小　で解きました。
以下テンプレ略。

i64 dp[2001][2001];
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; i64 x; cin >> N >> x;
    vector<i64> a(N);
    rep(i, N) cin >> a[i];
    i64 sum = 0;
    rep(j, N) {
        dp[0][j] += sum;
        sum += x;
    }
    rep(i, N) {
        i64 mi = 1.0e16;
        rep(j, N) {
            mi = min(mi, a[(i + j) % N]);
            dp[i + 1][j] = dp[i][j] + mi;
        }
    }
    i64 ans = 1.0e16;
    rep(j, N) ans = min(ans, dp[N][j]);
    cout << ans << endl;
    return 0;
}

C
これは……
無理。

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int H, W; cin >> H >> W;
    vector<string> fld(H);
    rep(i, H) cin >> fld[i];
    auto red = fld, blue = fld;
    {
        string k = string(W - 1, '#') + '.';
        rep(i, H) {
            red[i][0] = '#';
            if(i % 2 == 0)
              red[i] = k;
        }
    }

    {
        string k = '.' + string(W - 1, '#');
        rep(i, H) {
            blue[i][W - 1] = '#';
            if(i % 2)
              blue[i] = k;
        }
    }

    rep(i, H) cout << red[i] << '\n';
    cout << '\n';
    rep(i, H) cout << blue[i] << '\n';
    return 0;
}

面白いとは思うんですけどどうやっても思いつく気がしません……。

D
Kより長くなりそうなら先頭に繋ぎ変えればいいんですけど、このとき「なるべく前で（根に近い方で）切りたい」というのがなかなか実装できず。

int N, K;
vector<int> G[100000];
int ans;
int dfs(int cur_v, int p) {
    int res = 0;
    for(int nv : G[cur_v])
      res = max(res, dfs(nv, cur_v) + 1);
    if(res == K - 1 && p != 0) {
        ++ans;
        res = -1;
    }
    return res;
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> K;
    ans = 0;
    rep(i, N) {
        int p;
        cin >> p;
        --p;
        if(i == 0) {
            if(p != 0) ++ans;
            continue;
        }
        G[p].emplace_back(i);
    }
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}