接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 265（ABC265）

AtCoder Beginner Contest 265（ABC265）

AtCoderBeginnerContest AtCoderBeginnerContest265 ABC ABC265

atcoder.jp

A - Apple

$ X $ 円のものを $ i $ 個、$ Y $ 円のものを $ j $ 個買うものとして、全探索をする

提出コード

void solve() {
    ll X, Y, N;
    cin >> X >> Y >> N;
    ll ans = INF;
    REP(i, 101) REP(j, 101) {
        if (i + j * 3 == N) {
            chmin(ans, i * X + j * Y);
        }
    }
    cout << ans << endl;
}

B - Explore

シミュレートで判定する

提出コード

void solve() {
    ll N, M, T;
    cin >> N >> M >> T;
    vector<int> A(N - 1);
    REP(i, N - 1) cin >> A[i];
    vector<int> X(N), Y(N);
    REP(i, M) {
        int x, y;
        cin >> x >> y;
        x--;
        X[x]++, Y[x] = y;
    }
    REP(i, N - 1) {
        if (X[i]) T += Y[i];
        if (T > A[i]) {
            T -= A[i];
        }
        else {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

C - Belt Conveyor

シミュレートを行い、一度訪れたマスを記録する
一度訪れたマスに再度訪れた場合、無限に移動し続けることになるので-1
そうでない場合は、最後に止まったマスを出力

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> G(H);
    REP(i, H) cin >> G[i];
    vector used(H, vector<int>(W, -1));
    queue<pair<int, int>> q;
    q.emplace(0, 0);
    while (!q.empty()) {
        auto [h, w] = q.front();
        q.pop();
        if (used[h][w] != -1) {
            cout << "-1" << endl;
            return;
        }
        used[h][w] = 1;
        char c = G[h][w];
        int nh = h, nw = w;
        if (c == 'U') nh--;
        else if (c == 'D') nh++;
        else if (c == 'R') nw++;
        else nw--;
        if (nh < 0 or nh >= H or nw < 0 or nw >= W) {
            cout << h + 1 << " " << w + 1 << endl;
            return;
        }
        q.emplace(nh, nw);
    }
}

D - Iroha and Haiku (New ABC Edition)

予め累積和を求めておく
ある区間の和は単調増加するため、区間の片方を決めた場合、もう片方は一意に求まる
よって $ x $ の開始位置を全探索し、残りの $ y, z, w $ は二分探索で求めることができる

提出コード

void solve() {
    ll N, P, Q, R;
    cin >> N >> P >> Q >> R;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    vector<ll> cum(N + 1);
    REP(i, N) cum[i + 1] = cum[i] + A[i];
    string ans = "No";
    REP(x, N) {
        auto y = lower_bound(ALL(cum), cum[x] + P);
        if (y == cum.end()) continue;
        int y_idx = y - cum.begin();
        if (cum[x] + P != cum[y_idx]) continue;

        auto z = lower_bound(ALL(cum), cum[y_idx] + Q);
        if (z == cum.end()) continue;
        int z_idx = z - cum.begin();
        if (cum[y_idx] + Q != cum[z_idx]) continue;

        auto w = lower_bound(ALL(cum), cum[z_idx] + R);
        if (w == cum.end()) continue;
        int w_idx = w - cum.begin();
        if (cum[z_idx] + R != cum[w_idx]) continue;
        ans = "Yes";
    }
    cout << ans << endl;
}

E - Warp

$ dp[i][j][k] := i $ 回移動をし、そのうち $ (x+A, y+B) $ の移動を行った回数が $ j $ 回、$ (x+C, y+D) $ 　の移動を行った回数が $ k $ 回、$ (x+E, y+F) $ の移動を行った回数が $ i - j - k $ 回行ったときの移動経路の数としてDPを行う
それぞれの移動回数が決まっていれば、今いる座標は一意に決まるので、それぞれの操作が障害物にあるかどうかで遷移をさせる

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    ll A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    map<pair<int, int>, int> mp;
    REP(i, M) {
        int x, y;
        cin >> x >> y;
        mp[{x, y}] = 1;
    }
    // i 回目までに(+A,+B)の移動をj回、(+C, +D)の移動をk回、(+E, +F)の移動をi-j-k回
    vector dp(N + 1, vector<mint>(N + 1, 0));
    dp[0][0] = 1;
    REP(i, N) {
        vector nxt(N + 1, vector<mint>(N + 1, 0));
        REP(j, N) {
            REP(k, N) {
                if (dp[j][k] == 0) continue;
                ll x = A * j + C * k + (i - j - k) * E;
                ll y = B * j + D * k + (i - j - k) * F;
                {  // (+A, +B)
                    ll nx = x + A;
                    ll ny = y + B;
                    if (!mp.count({nx, ny})) {
                        nxt[j + 1][k] += dp[j][k];
                    }
                }
                {  // (+C, +D)
                    ll nx = x + C;
                    ll ny = y + D;
                    if (!mp.count({nx, ny})) {
                        nxt[j][k + 1] += dp[j][k];
                    }
                }
                {  // (+E, +F)
                    ll nx = x + E;
                    ll ny = y + F;
                    if (!mp.count({nx, ny})) {
                        nxt[j][k] += dp[j][k];
                    }
                }
            }
        }
        swap(dp, nxt);
    }
    mint ans = 0;
    REP(i, N + 1) REP(j, N + 1) ans += dp[i][j];
    cout << ans << endl;
}