接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 275（ABC275）

AtCoder Beginner Contest 275（ABC275）

AtCoderBeginnerContest AtCoderBeginnerContest275 ABC ABC275

atcoder.jp

A - Find Takahashi

max_elementで最大の値のインデックスを求める

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> H(N);
    REP(i, N) cin >> H[i];
    cout << max_element(ALL(H)) - H.begin() + 1 << endl;
}

B - ABC-DEF

掛け算する前にmodを取ってから計算する
modintを使うと楽

提出コード

void solve() {
    mint A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    cout << A * B * C - D * E * F << endl;
}

C - Counting Squares

一点を固定して、そこから時計回りに正方形を作ったときに条件を満たすかどうかを全探索する
4点の集合をsetなどで管理して重複して数えないようにする

提出コード

void solve() {
    const int N = 9;
    vector<string> S(N);
    REP(i, N) cin >> S[i];
    set<vector<pair<int, int>>> ans;
    auto check = [&](int x, int y) -> bool {
        if (0 <= x and x < N and 0 <= y and y < N and S[x][y] == '#') return true;
        return false;
    };
    REP(x, N) REP(y, N) REP(dx, -10, 10) REP(dy, -10, 10) {
        if (dx == 0 and dy == 0) continue;
        int x1 = x + dx;
        int y1 = y + dy;
        int x2 = x1 - dy;
        int y2 = y1 + dx;
        int x3 = x2 - dx;
        int y3 = y2 - dy;
        if (check(x, y) and check(x1, y1) and check(x2, y2) and check(x3, y3)) {
            vector<pair<int, int>> vp;
            vp.emplace_back(x, y);
            vp.emplace_back(x1, y1);
            vp.emplace_back(x2, y2);
            vp.emplace_back(x3, y3);
            sort(ALL(vp));
            ans.emplace(vp);
        }
    }
    cout << ans.size() << endl;
}

D - Yet Another Recursive Function

$ f(n) $ の種類数は $ \lfloor \frac{N}{2^x3^y} \rfloor $ 程度となりこれは メモ化することで $ O(log^2N) $ で解くことができる

提出コード

void solve() {
    ll N;
    cin >> N;
    map<ll, ll> dp;
    dp[0] = 1;
    auto memo = [&](auto &&self, ll n) -> ll {
        if (dp[n]) return dp[n];
        dp[n] = self(self, n / 2) + self(self, n / 3);
        return dp[n];
    };
    cout << memo(memo, N) << endl;
}

E - Sugoroku 4

$ dp[i][j] := i $ 回目にマス $ j $ にいるときの確率としてDPをする

提出コード

void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    vector dp(N + 1, mint(0));
    mint ans = 0;
    dp[0] = 1;
    REP(k, K) {
        vector nxt(N + 1, mint(0));
        REP(i, N) REP(m, 1, M + 1) {
            int to = (i + m > N ? 2 * N - i - m : i + m);
            nxt[to] += dp[i] / M;
        }
        swap(dp, nxt);
        ans += dp[N];
    }
    cout << ans << endl;
}

F - Erase Subarrays

$ dp[i][j][k] := i $ 番目まで見たときに総和が $ j $ で今、連続する部分列を消す操作をしているかどうかの状態を $ k $ で表したときの最小回数としてDPをする

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    vector dp(M + 1, vector<int>(2, INF));
    dp[0][0] = 0;
    REP(i, N) {
        vector nxt(M + 1, vector<int>(2, INF));
        REP(j, M + 1) {
            chmin(nxt[j][1], dp[j][0] + 1);
            chmin(nxt[j][1], dp[j][1]);
            if (j + A[i] <= M) {
                chmin(nxt[j + A[i]][0], dp[j][0]);
                chmin(nxt[j + A[i]][0], dp[j][1]);
            }
        }
        swap(dp, nxt);
    }
    REP(i, 1, M + 1) {
        int ans = min(dp[i][0], dp[i][1]);
        cout << (ans == INF ? -1 : ans) << endl;
    }
}