スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

Codeforces Global Round 9 感想

問題

Dashboard - Codeforces Global Round 9 - Codeforces

感想

4完。 ギャクが多かった。

[追記]

うぉ~~~!!ついに紫になったぞ~~~~うれし~~~~

維持できるようにがんばる。

f:id:scol:20200705113244p:plain
やったぜ。
f:id:scol:20200705113225p:plain
絶望の-107からの涙ぐましい軌跡

A - Sign Flipping

正負正負...... or 負正負正......にすればいい。ギャグ。

問題を理解するのに時間かかった。

提出コード

void solve() {
    int Q;
    cin >> Q;
    Vl A, B;
    while (Q--) {
        ll N;
        cin >> N;
        A.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> A[i];
        }
        B.resize(N);
        for (ll i = 0; i < N; i++) {
            if (i & 1) {
                B[i] = abs(A[i]);
            }
            else {
                B[i] = -abs(A[i]);
            }
        }
        for (ll i = 0; i < N; i++) {
            cout << B[i] << " ";
        }
        cout << "\n";
    }
}

B - Neighbor Grid

例えば、 N = 4,\ M = 5 なら

 \displaystyle{
    \begin{array}{ccc}
        2 & 3 & 3 & 3 & 2 \\
        3 & 4 & 4 & 4 & 3 \\
        3 & 4 & 4 & 4 & 3 \\
        2 & 3 & 3 & 3 & 2 \\
    \end{array}
}

みたいにすればいい。できなければNO。ギャグ。

提出コード

void solve() {
    int Q;
    cin >> Q;
    while (Q--) {
        ll N, M;
        cin >> N >> M;
        bool ok = true;
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < M; j++) {
                int a;
                cin >> a;
                if ((i == 0 && j == 0) || (i == 0 && j == M - 1) || (i == N - 1 && j == 0) || (i == N - 1 && j == M - 1)) {
                    if (a > 2) {
                        ok = false;
                    }
                }
                else if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
                    if (a > 3) {
                        ok = false;
                    }
                }
                else {
                    if (a > 4) {
                        ok = false;
                    }
                }
            }
        }
 
        if (ok) {
            cout << "YES\n";
            for (ll i = 0; i < N; i++) {
                for (ll j = 0; j < M; j++) {
                    int a;
                    if ((i == 0 && j == 0) || (i == 0 && j == M - 1) || (i == N - 1 && j == 0) || (i == N - 1 && j == M - 1)) {
                        a = 2;
                    }
                    else if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
                        a = 3;
                    }
                    else {
                        a = 4;
                    }
                    cout << a << " ";
                }
                cout << "\n";
            }
        }
        else {
            cout << "NO\n";
        }
    }
}

C - Element Extermination

結論はギャグで、 a_1 <  a_n ならYES、そうでなければNO。

[必要性の証明]

どんな操作をしても先頭は  a_1 より小さくできないし、末尾は  a_n より大きくできない。 だから、もし  a_1 > a_n なら (先頭) > (末尾) の関係はずっと保存されてしまうので、要素数を1にすることはできない。

[十分性の証明]

 a_1 <  a_n を仮定したときに、数列の要素数を1にできる操作列が必ず存在することを示す。

操作によって、先頭と末尾の間の要素たち(先頭と末尾は含まない)を単調減少にすることができる。 単調増加な連続部分列に対して、一番大きな要素以外を消すように操作を行っていくことでこれは実現できる。

この操作の結果、数列が  a_1, b_1, b_2, \ldots, b_k, a_n に変化したとする。

そして、可能な限り、先頭2つに対して  a_1 を残すように操作を繰り返す。

その結果、数列が  a_1, b_l, b_{l+1}, \ldots, b_k, a_n に変化したとする。このとき、 a_1 > b_l が成り立つ。

また、同様に、可能な限り、末尾2つに対して  a_n を残すように操作を繰り返す。

 a_1 <  a_n ならば、 b_k \lt b_{k+1} \lt \cdots \lt b_l \lt a_1 \lt a_n なので、 この操作によって  a_n 以外はすべて消えて数列の要素数は必ず1になる。(証明終わり)

この証明をコンテスト中に思いつけたのはよかった。

提出コード

void solve() {
    int Q;
    cin >> Q;
    Vl A;
    while (Q--) {
        ll N;
        cin >> N;
        A.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> A[i];
        }
        if (A[0] < A[N - 1]) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
}

D - Replace by MEX

適当を投げるとなんか通った、笑。

どうせ数列を 0, 1, ... , n-1 にするんだろな~~と思って、mex != n なら  a_\mathrm{mex} を mex に変化させて、 mex == n なら  a_i \neq i を満たす最小の i を s、  a_i = s を満たす i を tとして、 t -> s の順番に操作をするというコードを投げたら通った。やったぜ。

一応、色々テストケースを作って大丈夫なことを確かめてから提出した。

提出コード

void solve() {
    int Q;
    cin >> Q;
    Vi A;
    vector<set<int>> pos;
    Vi ans;
    while (Q--) {
        ll N;
        cin >> N;
        A.resize(N);
        pos.assign(N + 1, set<int>());
        for (ll i = 0; i < N; i++) {
            int a;
            cin >> a;
            A[i] = a;
            pos[a].emplace(i);
        }
 
        ans.clear();
 
        while (true) {
            bool ok = true;
            int cur;
            for (ll i = 0; i < N; i++) {
                if (A[i] != i) {
                    ok = false;
                    cur = i;
                    break;
                }
            }
            if (ok) {
                break;
            }
 
            int mex = 0;
            while (mex <= N && !pos[mex].empty()) {
                ++mex;
            }
 
            if (mex == N) {
                auto itr = pos[cur].begin();
                ans.emplace_back(*itr);
                pos[mex].emplace(*itr);
                A[*itr] = mex;
                pos[cur].erase(itr);
                mex = cur;
            }
 
            while (mex < N) {
                ans.emplace_back(mex);
                pos[A[mex]].erase(mex);
                pos[mex].emplace(mex);
                A[mex] = mex;
                mex = 0;
                while (mex <= N && !pos[mex].empty()) {
                    ++mex;
                }
            }
        }
 
 
 
 
        cout << ans.size() << "\n";
        for (const auto& ai : ans) {
            cout << ai + 1 << " ";
        }
        cout << "\n";
    }
}

E以降

問題を見てないので割愛。