Codeforces Round #666 (Div. 2) 感想

Dashboard - Codeforces Round #666 (Div. 2) - Codeforces

ABCDの4完。今回全体的にかなり雑に解いてしまった。

A - Juggling Letters

各アルファベットの登場回数がすべて $n$ で割り切れるかを確かめる。

提出コード

リンク： http://codeforces.com/contest/1397/submission/91352877

inline void solve_one() {
    ll N;
    cin >> N;
    Vl cnt(26);
    for (ll i = 0; i < N; i++) {
        string S;
        cin >> S;
        for (auto c : S) {
            int t = c - 'a';
            ++cnt[t];
        }
    }
    bool ok = true;
    for (ll i = 0; i < 26; i++) {
        if (cnt[i] % N != 0) {
            ok = false;
            break;
        }
    }
    prints()(ok ? "YES" : "NO");
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}

B - Power Sequence

$c$ を 1 から大きくしながら全探索した。上は $c^{n-1} > 10^{18}$ となるところで切った。

1回目の提出は pretest は通ったものの後になって致命的なバグが見つかったので念のため再提出をした。

この再提出がなければ順位は100位台だった......。

後で見返すと2回目の提出にも穴があることに気づいた(オーバーフローする可能性がある)。運がよかったね。しかし、あまりにも適当すぎる......。反省。

提出コード

リンク： http://codeforces.com/contest/1397/submission/91396481

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
 
    ll ans = L_INF;
    bool end_f = false;
    for (ll c = 1;; c++) {
        ll t = 0;
        ll x = 1;
        for (ll i = 0; i < N; i++) {
            t += abs(A[i] - x);
            x *= c;
            if (x > 1000000000000000000ll) {
                end_f = true;
                break;
            }
        }
        if (end_f)
            break;
        chmin(ans, t);
    }
    prints()(ans);
}

C - Multiples of Length

1回目と2回目の操作で配列の要素をすべて $n$ の倍数にして、3回目の操作を区間 $[ 1, n ]$ に対して行ってすべて 0 にするという戦略でいける。

1回目の操作は区間 $[ 1, n-1 ]$ に対して行う。

$\mathrm{gcd}(N-1, N) = 1$ なので、区間 $[ 1, n - 1 ]$ に対して操作を行うことで区間内のすべての要素を $n$ の倍数に変えることができる。

2回目の操作は区間 $[ n, n ]$ に対して操作を行って $a_n = 0$ にする。

3回目の操作は上で述べた通り区間 $[ 1, n ]$ に対して行い、要素をすべて 0 にする。

提出コード

リンク： http://codeforces.com/contest/1397/submission/91382657

template <typename T>
void extended_euclidean(T& x, T& y, const T& a, const T& b) {
    T u, v, s, t, k;
    s = a;
    t = b;
    x = 1;
    y = 0;
    u = 0;
    v = 1;
    while (t) {
        k = s / t;
        s -= k * t;
        swap(s, t);
        x -= k * u;
        swap(x, u);
        y -= k * v;
        swap(y, v);
    }
}
 
void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
 
    if (N == 1) {
        prints()(1, 1);
        prints()(-A[0]);
        prints()(1, 1);
        prints()(0);
        prints()(1, 1);
        prints()(0);
        return;
    }
 
    prints()(1, N - 1);
    for (ll i = 0; i < N - 1; i++) {
        prints("", " ")(A[i] * (N - 1));
        A[i] += A[i] * (N - 1);
    }
    prints()();
 
    prints()(N, N);
    prints()(-A[N - 1]);
    A[N - 1] = 0;
 
    prints()(1, N);
    for (ll i = 0; i < N; i++) {
        prints("", " ")(-A[i]);
    }
}

D - Stoned Game

「最も数の多い山から石を取っていくのが最適」という未証明エスパーをなげてしまった......。

「ある $i$ が存在して $a_i > (\textrm{その他の和})$ 」が成り立った瞬間に勝敗が決まる（ターンが回ってきたときにこれが成り立っていれば、最も数の多い山を独占し続けることで必ず勝てる）。なので、「少ない山から取っても相手の勝ちパターンを増やすだけじゃね？？」となって上のエスパーが思い浮かんだ。

Dashboard を見るとすでにたくさんの人が通していたので「まぁええか（笑）」と言いながら提出した。時間も残り少なかったしね。

提出コード

リンク： http://codeforces.com/contest/1397/submission/91409600

inline void solve_one() {
    ll N;
    cin >> N;
    Vi A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
 
    multiset<Pii> st;
    for (ll i = 0; i < N; i++) {
        st.emplace(A[i], i);
    }
 
    bool is_T = true;
    int pre = -1;
    while (true) {
        if ((ll)st.size() == 1) {
            is_T ^= true;
            break;
        }
        auto itr = prev(st.end());
        int x, idx;
        tie(x, idx) = *itr;
        if (idx == pre) {
            if ((ll)st.size() < 2) {
                break;
            }
            itr = prev(itr);
            tie(x, idx) = *itr;
        }
        st.erase(itr);
        --x;
        pre = idx;
        if (x > 0) {
            st.emplace(x, idx);
        }
        is_T ^= true;
    }
    prints()(is_T ? "HL" : "T");
}
 
void solve() {
    int Q;
    cin >> Q;
    while (Q--) solve_one();
}