ABC 241

Table of Contents

A - Digit Machine

問題

a[a[a[0]]] を出力すれば良い.

void solve() {
    vint a(10);
    rep(i, 10) cin >> a[i];

    cout << a[a[a[0]]] << endl;
}

提出コード

B - Pasta

問題

map にそれぞれの麺の長さの数を保存して, $i$ 日目に麺が残っていたら 1 decrement, 残っていなかったら No を出力.

最終的に $M$ 日間の食事計画に問題なければ Yes を出力.

提出コード

C - Connect 6

問題

$(i, j)$ を始点として上下左右斜め8方向に対して6マスの中に白の数が2つ以下となっているかを全探索する.

方向が違う以外は調べる処理の中身は同じなので関数化しておくと楽.

bool search(int i, int j, int di, int dj) {
    // (i, j): start point
    // (fi, fj): final point
    int fi = i + di * 5;
    int fj = j + dj * 5;
    if (fi < 0 || fi >= n || fj < 0 || fj >= n)
        return false;

    int rem = 6;
    int r = i, c = j;
    int numwhite = 0;
    rep(i, rem) {
        numwhite += grid[r][c] == '.';
        r += di;
        c += dj;
    }

    if (numwhite <= 2) {
        return true;
    }
    return false;
}

提出コード

D - Sequence Query

[問題](D - Sequence Query)

コンテスト後自力AC

multiset 1 つだけ使っても解けるが, 2つ使うと 2, 3番のクエリで同じ処理が使え楽になる.

$x$ 以下 を扱うときは要素を $-1$ 倍して 以上 の問題に直したほうが扱いが楽になる.

2つの多重集合をそれぞれ $S_2, S_3$ とする

void query(multiset<ll>& s, ll sign) {
    ll x, k;
    cin >> x >> k;
    auto it = s.lower_bound(sign * x);
    if (it == s.end()) {
        cout << -1 << endl;
        return;
    }

    int rem = k - 1;
    while (it != s.end() && rem) {
        it++;
        rem--;
    }
    if (it == s.end())
        cout << -1 << endl;
    else
        cout << sign * (*it) << endl;
}

void solve() {
    int q;
    cin >> q;
    multiset<ll> s2, s3;

    rep(i, q) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll x;
            cin >> x;
            s2.insert(-x);
            s3.insert(x);
        } else if (t == 2) {
            query(s2, -1);
        } else {
            query(s3, 1);
        }
    }
}

提出コード

E - Putting Candies

問題

Pollard’s rho algorithm の要領である地点で周期的に回る. 周期の長さを $L$, 一周で増える要素の数を $T$, しっぽの長さを $l$, しっぽ分で増える要素の個数を $t$ とする.

$K \leq l$ のときは愚直にシミュレーションする.

それ以上のときは $\displaystyle t + \lfloor \frac{K-l}{L} \rfloor \times T + (あまりの操作分)$ を出力する. あまりの操作分は愚直にシミュレーションする. 残る操作は $L \leq N$ 以下となるので愚直にシミュレーションしても問題ない.

提出コード

F - Skate

問題

解説読んだ