AtCoder Beginner Contest 285（ABC285）

atcoder.jp

A - Edge Checker 2

$ i $ の子は $ 2i $ もしくは $ 2i + 1 $ となるのでこれを判定する

提出コード

void solve() {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    if (2 * a == b or 2 * a + 1 == b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Longest Uncommon Prefix

各 $ i $ について条件を満たすものを愚直に数える

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    REP(i, 1, N) {
        int cnt = 0;
        REP(k, N - i) {
            if (S[k] == S[k + i]) {
                break;
            }
            cnt++;
        }
        cout << cnt << endl;
    }
}

C - abc285_brutmhyhiizp

文字列を26進数のように扱い、これを10進数として変換する

提出コード

void solve() {
    string S;
    cin >> S;
    ll ans = 0;
    reverse(ALL(S));
    ll base = 1;
    for (char c : S) {
        ans += base * (c - 'A' + 1);
        base *= 26;
    }
    cout << ans << endl;
}

D - Change Usernames

$ S_i $ から $ T_i $ へ有向辺を貼ったグラフを考える
このグラフ上にサイクルが存在すれば操作は行えず、存在しなければ操作は行うことができる
よって、グラフにサイクルが存在するかどうかを判定すれば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<string> idx;
    vector<string> S(N), T(N);
    REP(i, N) {
        cin >> S[i] >> T[i];
        idx.emplace_back(S[i]);
        idx.emplace_back(T[i]);
    }
    sort(ALL(idx));
    idx.erase(unique(ALL(idx)), idx.end());
    int sz = idx.size();
    vector<vector<int>> g(sz);
    REP(i, N) {
        int u = lower_bound(ALL(idx), S[i]) - idx.begin();
        int v = lower_bound(ALL(idx), T[i]) - idx.begin();
        g[u].emplace_back(v);
    }
    auto res = topologicalSort(g);
    cout << (res.size() == sz ? "Yes" : "No") << endl;
}

E - Work or Rest

ある休日とその次の休日の間の生産量は休日間の平日の日数によって一意に定まるので予め前計算しておく
その上で、$ dp[i][j] := i $ 日目まで決めたとき、$ j $ 日間平日が続いているときの総和の最大としてDPを行う

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N + 1);
    REP(i, N) cin >> A[i + 1];
    vector<ll> b(N + 1);
    REP(i, 1, N + 1) b[i] = b[i - 1] + A[(i + 1) / 2];
    vector dp(N + 10, vector(N + 10, -1LL));
    dp[1][0] = 0;
    REP(i, 1, N) {
        REP(j, N + 1) if (dp[i][j] != -1) {
            chmax(dp[i + 1][j + 1], dp[i][j]);
            chmax(dp[i + 1][0], dp[i][j] + b[j]);
        }
    }
    ll ans = 0;
    REP(i, N) chmax(ans, dp[N][i] + b[i]);
    cout << ans << endl;
}