AtCoder Beginner Contest 278（ABC278）

atcoder.jp

A - Shift

シミュレーションをする

提出コード

void solve() {
    int N, K;
    cin >> N >> K;
    deque<int> dq;
    REP(i, N) {
        int a;
        cin >> a;
        dq.push_back(a);
    }
    REP(_, K) {
        dq.pop_front();
        dq.push_back(0);
    }
    while (!dq.empty()) {
        int a = dq.front();
        dq.pop_front();
        cout << a << " ";
    }
    cout << endl;
}

B - Misjudge the Time

シミュレーションをし、条件が見つかればそれを出力する

提出コード

void solve() {
    int H, M;
    cin >> H >> M;
    int A = H / 10;
    int B = H % 10;
    int C = M / 10;
    int D = M % 10;

    auto check = [](int h, int m) -> bool {
        int a = h / 10;
        int b = h % 10;
        int c = m / 10;
        int d = m % 10;
        int hh = a * 10 + c;
        int mm = b * 10 + d;
        if (hh >= 0 and hh < 24 and mm >= 0 and mm < 60) return true;
        return false;
    };

    for (int i = 0; i < H + 24; i++) {
        for (int j = 0; j <= 60; j++) {
            int m = (C * 10 + D + j) % 60;
            int h = ((A * 10 + B + i) + (C * 10 + D + j >= 60)) % 24;
            if (check(h, m)) {
                dumps(i, j);
                printf("%02d %02d\n", h, m);
                return;
            }
        }
    }
}

C - FF

map に setをもたせ各ユーザが誰をフォローしているかを管理する

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    map<int, set<int>> mp;
    while (Q--) {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1) {
            mp[a].emplace(b);
        }
        else if (t == 2) {
            mp[a].erase(b);
        }
        else {
            if (mp[a].count(b) and mp[b].count(a)) {
                cout << "Yes" << endl;
            }
            else cout << "No" << endl;
        }
    }
}

D - All Assign Point Add

区間変更、一点取得ができればいいので遅延セグ木を使う

提出コード

using S = long long;
using F = long long;

const F ID = LINF;

S op(S a, S b) { return std::min(a, b); }
S e() { return LINF; }
S mapping(F f, S x) { return (f == ID ? x : f); }
F composition(F f, F g) { return (f == ID ? g : f); }
F id() { return ID; }

void solve() {
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);
    int Q;
    cin >> Q;
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int x;
            cin >> x;
            seg.apply(0, N, x);
        }
        else if (q == 2) {
            int i, x;
            cin >> i >> x;
            --i;
            seg.apply(i, i + 1, x + seg.prod(i, i + 1));
        }
        else {
            int i;
            cin >> i;
            --i;
            cout << seg.prod(i, i + 1) << endl;
        }
    }
}

E - Grid Filling

各整数ごとに二次元累積和を使って各区間に含まれる個数を求める
その個数が全体の個数より多いか少ないかで種類数に加えるかどうかが決まる
上記を全区間に対して求めても $ O(NHW) $ となるので実行時間以内に解くことができる

提出コード

void solve() {
    int H, W, N, h, w;
    cin >> H >> W >> N >> h >> w;
    vector<vector<int>> A(H, vector<int>(W));
    vector<int> sum(N);
    REP(i, H) REP(j, W) {
        cin >> A[i][j];
        sum[A[i][j] - 1]++;
    }
    vector cum(N, vector(H + 1, vector(W + 1, 0)));
    REP(i, H)
    REP(j, W)
    REP(k, N) cum[k][i + 1][j + 1] += cum[k][i + 1][j] + cum[k][i][j + 1] - cum[k][i][j] + (A[i][j] == k + 1);
    REP(k, H - h + 1) {
        REP(l, W - w + 1) {
            int cnt = 0;
            REP(n, N) {
                cnt += sum[n] - (cum[n][k + h][l + w] + cum[n][k][l] - cum[n][k][l + w] - cum[n][k + h][l]) > 0;
            }
            cout << cnt << " ";
        }
        cout << endl;
    }
}

F - Shiritori

$ dp[i][j] := $ 直前に選んだものが $ i $ で、選んだものの集合が $ j $ のときに勝ちか負けかどうかをDPする
今が自分のターンのとき勝ちのノードがあればそれを選べばいい、逆に相手のターンのとき自分が負けるノードがあれば相手はそれを選ぶのでそれをもとに遷移を更新する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i, N) cin >> S[i];

    vector dp(N + 1, vector(1 << N, -1));
    auto memo = [&](auto &&self, int state, int pre) -> bool {
        if (dp[pre][state] != -1) return dp[pre][state];
        int turn = __builtin_popcount(state) % 2;
        int ok = 0;
        int no = 0;

        REP(i, N) {
            if (state >> i & 1) continue;
            if (pre < N and S[pre].back() != S[i][0]) continue;
            int ret = self(self, state ^ (1 << i), i);
            if (ret) ok++;
            else no++;
        }
        if (turn == 0) {
            if (ok) return dp[pre][state] = 1;
            else return dp[pre][state] = 0;
        }
        else {
            if (no) return dp[pre][state] = 0;
            else return dp[pre][state] = 1;
        }
    };
    cout << (memo(memo, 0, N) == 1 ? "First" : "Second") << endl;
}