ABC337-A 解説

A - Scoreboard

2チームのN試合分の野球の点数が与えられて、合計得点が高いチーム、または引き分けかを判定する問題です。N回ループを回して、合計得点を求め、あとはifで比較をするだけです。

N = int(input())
sx = 0
sy = 0
for _ in range(N):
    X, Y = map(int, input().split())
    sx += X
    sy += Y
if sx > sy:
    print("Takahashi")
elif sx < sy:
    print("Aoki")
else:
    print("Draw")

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

int main() {
    int N;
    cin >> N;
    int sx = 0, sy = 0;
    for (int i = 0; i < N; i++) {
        int X, Y;
        cin >> X >> Y;
        sx += X;
        sy += Y;
    }
    if (sx > sy) {
        cout << "Takahashi\n";
    } else if (sx < sy) {
        cout << "Aoki\n";
    } else {
        cout << "Draw\n";
    }
}

ABC197-E 解説

E - Traveler

各色ごとに回収する順番を考えます。色 $i$ に対して、最も座標が小さいものを $Min_i$ 、最も座標が大きいものを $Max_i$ とすると、簡単に言えば $Max_i$ までまっすぐ行ってから $Min_i$ に行く、または $Min_i$ までまっすぐ行ってから $Max_i$ に行くのが最適です。

よって、DPできます。具体的には、各色に対して最も座標が小さいもの、最も座標が大きいもののそれぞれに到達するまでにかかる最小の時間を持ちます。

inf = 1500000000
N = int(input())
Min, Max = [inf] * N, [-inf] * N
for _ in range(N):
    X, C = map(int, input().split())
    C -= 1
    Min[C] = min(Min[C], X)
    Max[C] = max(Max[C], X)
dp0, dp1, pre_min, pre_max = 0, 0, 0, 0
for i in range(N):
    if Min[i] == inf:
        continue
    m = abs(Max[i] - Min[i])
    dp0, dp1 = min(dp0 + abs(Max[i] - pre_min), dp1 + abs(Max[i] - pre_max)) + m, min(dp0 + abs(Min[i] - pre_min), dp1 + abs(Min[i] - pre_max)) + m
    pre_min = Min[i]
    pre_max = Max[i]
print(min(dp0 + abs(pre_min), dp1 + abs(pre_max)))

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1500000000;

int main() {
    int N;
    cin >> N;
    vector<int> Min(N, inf), Max(N, -inf);
    for (int i = 0; i < N; i++) {
        int X, C;
        cin >> X >> C;
        C--;
        Min[C] = min(Min[C], X);
        Max[C] = max(Max[C], X);
    }
    ll dp0 = 0, dp1 = 0, pre_min = 0, pre_max = 0;
    for (int i = 0; i < N; i++) {
        if (Min[i] == inf) {
            continue;
        }
        int m = abs(Max[i] - Min[i]);
        ll ndp0 = min(dp0 + abs(Max[i] - pre_min), dp1 + abs(Max[i] - pre_max)) + m;
        ll ndp1 = min(dp0 + abs(Min[i] - pre_min), dp1 + abs(Min[i] - pre_max)) + m;
        dp0 = ndp0;
        dp1 = ndp1;
        pre_min = Min[i];
        pre_max = Max[i];
    }
    cout << min(dp0 + abs(pre_min), dp1 + abs(pre_max)) << '\n';
}

AGC010-A 解説

A - Addition

全ての和が偶数なら、奇数は偶数個あるので、奇数を2つずつ組にすると全て偶数になり、これは明らかにすべて合成できます。 そうでないなら、奇数は奇数個あるので、奇数をどのように合成しても必ず奇数が1つだけ残り、残りは全て偶数になるので、全て合成するのは不可能です。 よって、全ての和が偶数かどうか判定することで解けます。

N = int(input())
A = list(map(int, input().split()))
print("YES" if sum(A) % 2 == 0 else "NO")

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    cout << (accumulate(A.begin(), A.end(), 0LL) % 2 == 0 ? "YES" : "NO") << '\n';
}

JOI2014 本選1 解説

A - JOI 紋章 (JOI Emblem)

まず最初に、全体での答えを求めておき、次に1箇所だけ変えた時に答えがどれだけ変わるかを計算すると解けます。計算量は $O(MN)$ です。

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

int main() {
    int M, N;
    cin >> M >> N;
    vector<string> S(M);
    for (int i = 0; i < M; i++) {
        cin >> S[i];
    }
    vector<string> E(2);
    cin >> E[0] >> E[1];
    auto isok = [&](int x, int y) -> bool {
        return (S[x][y] == E[0][0] && S[x][y + 1] == E[0][1] && S[x + 1][y] == E[1][0] && S[x + 1][y + 1] == E[1][1]);
    };
    int now = 0;
    for (int i = 0; i < M - 1; i++) {
        for (int j = 0; j < N - 1; j++) {
            now += isok(i, j);
        }
    }
    int ans = now;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            char c = S[i][j];
            int cnt = 0;
            for (int k = max(0, i - 1); k < min(M - 1, i + 1); k++) {
                for (int l = max(0, j - 1); l < min(N - 1, j + 1); l++) {
                    cnt += isok(k, l);
                }
            }
            for (char nc: "JOI") {
                S[i][j] = nc;
                int cnt2 = 0;
                for (int k = max(0, i - 1); k < min(M - 1, i + 1); k++) {
                    for (int l = max(0, j - 1); l < min(N - 1, j + 1); l++) {
                        cnt2 += isok(k, l);
                    }
                }
                ans = max(ans, now - cnt + cnt2);
            }
            S[i][j] = c;
        }
    }
    cout << ans << '\n';
}

ABC157-E 解説

E - Simple String Queries

Fenwick Treeを使います。Point AddとRange Sumを高速にできます。 Fenwick Treeを $26$ 本持つと $1$ 文字を変更したり、各文字について、区間にその文字が現れる個数を高速に求めることができたりします。

• type1のクエリについて

Fenwick Treeの更新前の文字の $i$ 番目に $-1$ を足して更新後の文字の $i$ 番目に $1$ を足すとうまく変更できます。

• type2のクエリについて

Fenwick Treeの各文字に対し、$l$ 文字目から $r$ 文字目までの和を求めて、それが正である個数を求めます。

from atcoder.fenwicktree import FenwickTree
N = int(input())
S = list(input())
fw = [FenwickTree(N) for _ in range(26)]
for i in range(N):
    fw[ord(S[i]) - ord('a')].add(i, 1)
for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        i = int(q[1]) - 1
        c = q[2]
        fw[ord(S[i]) - ord('a')].add(i, -1)
        fw[ord(c) - ord('a')].add(i, 1)
        S[i] = c
    else:
        l = int(q[1]) - 1
        r = int(q[2]) - 1
        print(sum(fw[i].sum(l, r + 1) > 0 for i in range(26)))

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

int main() {
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<fenwick_tree<int>> fw(26, fenwick_tree<int>(N));
    for (int i = 0; i < N; i++) {
        fw[S[i] - 'a'].add(i, 1);
    }
    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            char c;
            cin >> i >> c;
            i--;
            fw[S[i] - 'a'].add(i, -1);
            fw[c - 'a'].add(i, 1);
            S[i] = c;
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            int ans = 0;
            for (int i = 0; i < 26; i++) {
                if (fw[i].sum(l, r + 1)) {
                    ans++;
                }
            }
            cout << ans << '\n';
        }
    }
}

ABC217-D 解説

D - Cutting Woods

データ構造ゲーです。要素が小さい順に並んでいて、データの挿入と探索が高速にできるデータ構造としては、PythonではSortedList、C++ではsetなどがあります。

from sortedcontainers import SortedList
L, Q = map(int, input().split())
s = SortedList([0, L])
for _ in range(Q):
    c, x = map(int, input().split())
    if c == 1:
        s.add(x)
    else:
        l = s.bisect_left(x)
        print(s[l] - s[l - 1])

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

int main() {
    int L, Q;
    cin >> L >> Q;
    set<int> s;
    s.insert(0);
    s.insert(L);
    for (int i = 0; i < Q; i++) {
        int c, x;
        cin >> c >> x;
        if (c == 1) {
            s.insert(x);
        } else {
            auto l = s.lower_bound(x);
            cout << *l - *next(l, -1) << '\n';
        }
    }
}

ABC261-D 解説

D - Flipping and Bonus

DPをします。$dp[$(0-indexedで)$i$回目のコイントスで$][j$回連続で表が出ているとき$]$のこれまでもらったお金の最大値 というDPができます。遷移は、$i$連続の連続ボーナスを$Bonus[i]$(なければ$0$)とすると、

$dp[i][0]=max(dp[i-1])$

$1 \le j \le i+1$のとき $dp[i][j]=dp[i-1][j-1]+X[i]+Bonus[j]$

で、答えは$max(dp[N-1])$です。

N, M = map(int, input().split())
X = list(map(int, input().split()))
Bonus = [0] * (N + 1)
for _ in range(M):
    C, Y = map(int, input().split())
    Bonus[C] = Y
dp = [[0] * (N + 1) for _ in range(N)]
dp[0][1] = X[0] + Bonus[1]
for i in range(1, N):
    dp[i][0] = max(dp[i - 1])
    for j in range(1, i + 2):
        dp[i][j] = dp[i - 1][j - 1] + X[i] + Bonus[j]
print(max(dp[N - 1]))

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> X(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }
    vector<int> Bonus(N + 1);
    for (int i = 0; i < M; i++) {
        int C, Y;
        cin >> C >> Y;
        Bonus[C] = Y;
    }
    vector<vector<long long>> dp(N, vector<long long>(N + 1));
    dp[0][1] = X[0] + Bonus[1];
    long long mx = dp[0][1];
    for (int i = 1; i < N; i++) {
        dp[i][0] = mx;
        for (int j = 1; j <= i + 1; j++) {
            dp[i][j] = dp[i - 1][j - 1] + X[i] + Bonus[j];
            if (mx < dp[i][j]) {
                mx = dp[i][j];
            }
        }
    }
    cout << mx << '\n';
}