Codeforces Round #654 (Div. 2) 感想

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

感想

🥺

f:id:scol:20200702093507p:plain

惜しかった～～

今回は界隈で有名な物理好きさん(@butsurizuki)がwriterでした。

いや～すごいな～。僕がwriterなんかしたらコンテスト中は怒りのclarが2兆個飛んできて、コンテスト後はwriter解に穴が5京個見つかり競プロ界から永久BANされそう。

日本人writerということもあってか、僕のフレンド（一方的）も温まっている方が多い感じがする。

A - Magical Sticks

$n$ が偶数の時は $n+1$ 、奇数の時は $n$ に揃えるのが一番いいだろうという直感を信じ提出するとACを得た。

提出コード

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N;
        cin >> N;
        cout << (N + 1) / 2 << "\n";
    }
}

B - Magical Calendar

色々試すと、 $r \lt n$ の時は $1 + 2 + \cdots + r$ 、 $r \ge n$ の時は $1 + 2 + \cdots + n - 1 + 1$ が答えだということが分かった。

横幅で分類して整理するのがポイントかもしれない。後のCやDより難しく感じた。

提出コード

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N, R;
        cin >> N >> R;
        ll b;
        if (R < N) {
            b = R * (R + 1) / 2;
        }
        else {
            b = N * (N - 1) / 2 + 1;
        }
        cout << b << "\n";
    }
}

C - A Cookie for You

type2（逆張り）の人を怒らせないように頑張れば良さそうで、そうなると $m \le \min(a, b)$ が条件となる。

あと、もちろん全員がクッキーにありつけるための条件 $n + m \le a + b$ も要る。

div2-Cにしては簡単で、逆に「なにか見落としてるんちゃうか......」とか言って時間を無駄に消費してしまった。ダメだなぁ。

提出コード

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll A, B, N, M;
        cin >> A >> B >> N >> M;
        bool ok = true;
        if (M > min(A, B)) {
            ok = false;
        }
        if (A + B < M + N) {
            ok = false;
        }
        cout << (ok ? "YES\n" : "NO\n");
    }
}

D - Grid-00100

$k\,\%\,n = 0$ の時は、下のようにすれば行も列も1の個数の差を0にできる。

そうでないときは、行も列も個数の差を0にするのは不可能だが、このときも下のようにすれば行も列も個数の差を1に抑えることができる。

はじめに、各列に $\lfloor k/n \rfloor$ 個ずつ1を入れる。このとき、

$\displaystyle{ \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ \end{bmatrix} }$

みたいに列ごとに1つずつ下にずらしながら1を入れると、各行に入る1の個数も $\lfloor k/n \rfloor$ になる。

そして、余りの $k\,\%\,n$ 個の1を $A(i, i+1),\ i=1,2,\cdots k\,\%\,n$ に入れていけば良い。

提出コード

void solve() {
    int Q;
    cin >> Q;
    int cell[301][301];
    while (Q--) {
        ll N, K;
        cin >> N >> K;
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                cell[i][j] = 0;
            }
        }
        ll a = K / N;
        ll b = K % N;
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < a; j++) {
                cell[i][(i + j) % N] = 1;
            }
        }
        for (ll i = 1; i <= b; i++) {
            cell[i][i - 1] = 1;
        }
 
        ll score;
        if (b == 0) {
            score = 0;
        }
        else {
            score = 2;
        }
 
        cout << score << "\n";
 
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                cout << cell[i][j];
            }
            cout << "\n";
        }
    }
}

E1 - Asterism (Easy Version)

まず、数列 $a$ をソートしておく。

$f(x)$ の値は、 $a_i$ の大きい $i$ から、 $P_i$ を割り当てて行くことを考えれば求められる。各 $i$ について割り当てられる $P_i$ の値が何通りずつあるかを調べて（これを $b_i$ とおく）、それらを掛け合わせれば $f(x)$ となる。

知りたいのは $f(x)$ が素数 $p$ で割り切れるかどうかだから、実際に $f(x)$ を求める必要はなくて、 $b_i$ の素因数に $p$ が含まれるかどうかを調べればいい。さらに、 $b_i$ は必ずある整数 $c_i$ の階乗 $c_i!$ になるので、 $c_i$ が $p$ 以上であるかどうかのみを調べればいい。

提出コード

void solve() {
    ll N, P;
    cin >> N >> P;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater<ll>());
 
    Vi ans;
    for (ll x = 0; x <= 2000; x++) {
        bool ok = true;
        ll mr = x + N;
        ll cnt = 0;
        for (ll i = 0; i < N; i++) {
            ll r = mr - max(A[i], x) - cnt;
            if (r == P || r <= 0) {
                ok = false;
                break;
            }
            else {
                ++cnt;
            }
        }
 
        if (ok) {
            ans.emplace_back(x);
        }
    }
 
    cout << ans.size() << "\n";
    for (const auto& ai : ans) {
        cout << ai << " ";
    }
    cout << "\n";
}