AtCoder Beginner Contest 369に参加しました。

使用しているテンプレート

A - 369

$2$ つの整数が与えられたときに、この $2$ つの数と並べることで $3$ 項の等差数列となる数がいくつあるかを求める問題。偶奇に注目して場合分けでもいいが、全探索する方が楽な気がする。全探索の範囲は $-100$ 以上 $200$ 以下で十分。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int A, B; cin >> A >> B;
    int ans = 0;

    for(int i = -100; i <= 200; i ++){
        vector<int> X= {i, A, B};
        sort(all(X));
        if(X[2] - X[1] == X[1] - X[0]){
            ans ++;
        }
    }

    cout << ans << "\n";
}

B - Piano 3

左手と右手の動かす位置が与えられ、動かす距離の和の最小値を求める問題。実際には、両手のスタート位置をはじめの鍵盤においておくことでシミュレーションするだけの問題になるが、気づけずに全探索してしまった。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> A(N);
    vector<char> S(N);
    rep(i, N) cin >> A[i] >> S[i];

    int ans = 1e9;

    for(int l = 1; l <= 100; l ++){
        for(int r = 1; r <= 100; r ++){
            int R = r, L = l, now = 0;
            rep(i, N){
                if(S[i] == 'L'){
                    now += abs(A[i] - L);
                    L = A[i];
                }else{
                    now += abs(A[i] - R);
                    R = A[i];
                }
            }

            ans = min(ans, now);
        }
    }

    cout << ans << "\n";
}

C - Count Arithmetic Subarrays

長さ $N$ の整数列 $A$ が与えられ、$A$ の連続部分列であって、等差数列であるものの個数を数え上げる問題。
$D_i=A_{i + 1} - A_i$ で定義される数列 $D$ を考えると、同じ数が連続する区間ごとに分割 (いわゆるランレングス圧縮) し、それぞれの区間において、区間の長さが $d$ なら、長さが $2$ 以上の条件を満たす部分列は ${}_dC_2$ 個である。あとは長さが $1$ の部分列 $N$ 個を加えればよい。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> A(N); v_cin(A);
    vector<int> D(N - 1); rep(i, N - 1) D[i] = A[i + 1] - A[i];
    
    ll ans = N;

    int now = 0;
    int val = -1e9;
    rep(i, N - 1){
        if(D[i] != val){
            ans += (ll) now * (now + 1) / 2;
            val = D[i];
            now = 1;
        }else{
            now ++;
        }
    }

    ans += (ll) now * (now + 1) / 2;

    cout << ans << "\n";
}

D - Bonus EXP

強さが $A_i$ の $N$ 匹のモンスターがいる。プレイヤーは、それぞれのモンスターに対して順番に以下の操作を選択することができる。

  • モンスターを倒す
    • モンスターを倒すのが奇数回目なら、経験値 $A_i$ を得る
    • モンスターを倒すのが偶数回目なら、経験値 $2A_i$ を得る
  • モンスターを倒さない

このとき、プレイヤーが得られる経験値の最大値を求める問題。

\[dp_{i,j} = i\text{ 匹目までで倒した数を $2$ で割ったあまりが$j$ のときの最大値}\]

とすると、

\[\begin{align*} dp_{i + 1,0} &= \max\{dp_{i, 0},~ dp_{i, 1} + 2A_i\}\\ dp_{i + 1, 1} &= \max\{dp_{i, 1},~ dp_{i, 0} + A_i\} \end{align*}\]

という簡単な遷移のDPで答えが求められる。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> A(N); v_cin(A);

    vector<vector<ll>> dp(N + 1, vector<ll> (2, -1e18));

    dp[0][0] = 0;
    rep(i, N){
        dp[i + 1][0] = max(dp[i][0], dp[i][1] + 2 *  A[i]);
        dp[i + 1][1] = max(dp[i][1], dp[i][0] + A[i]);
    }

    cout << max(dp[N][0], dp[N][1]) << "\n"; 
}

E - Sightseeing Tour

$N$ 頂点 $M$ 辺の重み付き単純無向グラフが与えられる。必ず通らなければならな辺の番号の集合 $K$ が与えられるという $Q$ 個のクエリに対して、点 $1$ から点 $N$ までの最短距離を求める問題。
まずは最短距離を求める問題なので、Dijkstra 法を考えた。しかし、Dijkstra 法は計算量が $O((N + M)\log M)$ なので、$M \leq 2\times 10^5 ,~Q\leq 3000$ という制約では間に合わない。
ここで、$|K|\leq 5$ という制約に注目した。必ず通らなければならない辺の順番と向きは、$|K|!2^{|K|}$ 通りで全探索ができる。あとは、グラフ上の $2$ 点間の距離が高速で求められればよいが、$N\leq400$ なので、Warshall–Floyd 法であらかじめ前計算しておけば問題ない。全体の計算量は、$O(\max ( N^3, ~ Q|K|!2^{|K|} ) )$ となる。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M; cin >> N >> M;
    vector<int> U(M), V(M), T(M);
    rep(i, M){
        cin >> U[i] >> V[i] >> T[i];
        U[i] --, V[i] --;
    }
    
    vector<vector<ll>> dp(N, vector<ll>(N, 1e18));
    rep(i, N) dp[i][i] = 0;
    rep(i, M){
        dp[U[i]][V[i]] = min(dp[U[i]][V[i]], (ll) T[i]);
        dp[V[i]][U[i]] = min(dp[V[i]][U[i]], (ll) T[i]);
    }

    rep(k, N) rep(i, N) rep(j, N){
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    }

    int Q; cin >> Q;
    while(Q --){
        int K; cin >> K;
        vector<int> B(K);
        rep(i, K){
            cin >> B[i];
            B[i] --;
        }

        ll ans = 1e18;

        do{
            rep(i, 1 << K){// bit が立っていたら U -> V の向き
                ll now = 0;
                rep(j, K) now += T[B[j]];

                vector<int> route = {0};
                rep(j, K){
                    if((i >> j) & 1){
                        route.push_back(U[B[j]]);
                        route.push_back(V[B[j]]);
                    }else{
                        route.push_back(V[B[j]]);
                        route.push_back(U[B[j]]);
                    }
                }
                route.push_back(N - 1);

                rep(j, K + 1){
                    now += dp[route[2 * j]][route[2 * j + 1]];
                }

                ans = min(ans, now);
            }
        }while(next_permutation(all(B)));

        cout << ans << "\n";
    }
}

コンテスト結果

コメント

E問題の考察がきれいにハマってくれて勝った。このまま入水したい。