Codeforces Round #704 (Div. 2) 参加記

はじめに

久しぶりにCodeforcesに参加しました。
相変わらず英語がそこまで早く読めないので翻訳しながらやってます。

A - Three swimmers

P以上の最小のA, B, Cの倍数は繰り上げればすぐに求まるので、そのそれぞれからPを引くだけです。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int q;
    cin >> q;
    while(q--) {
        long long p, a, b, c;
        cin >> p >> a >> b >> c;
        long long x = (p + a - 1) / a * a - p;
        long long y = (p + b - 1) / b * b - p;
        long long z = (p + c - 1) / c * c - p;
        cout << min({x, y, z}) << endl;
    }
    return 0;
}

B - Card Deck

方針としては、上から、山に残っているカードのうち一番大きい数字のカードまでを取り出して答えの山に積む、という操作を繰り返します。
順列なので、取出したかどうかの配列を持っておくと、それを後ろから順にみていって、次に取り出すべき1番大きい値を見つけられます。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int q;
    cin >> q;
    while(q--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for(int i = 0; i < n; i++) cin >> p[i];

        vector<bool> use(n + 1, false);  // 各数字を取り出したかどうか
        vector<int> ans;  // 答えの山となる配列
        vector<int> add;  // 積み替える際に取出して保存する配列
        int next = n;  // 次に取り出すべき数字

        // 元の山が無くなるまで
        while((int)p.size() != 0) {
            for(int i = (int)p.size() - 1; i >= 0; i--) {
                // 上から取出していく値をメモしていく
                use[p[i]] = true;
                add.push_back(p[i]);

                // 探すべき1番大きい値が見つかったら
                if(p[i] == next) {
                    // 答えの山に今取出したカードを積む
                    for(int i = (int)add.size() - 1; i >= 0; i--) ans.push_back(add[i]);
                    // まだ取り出してない1番大きい値を次探すべき数字に変更する
                    for(int j = next; j >= 0; j--) {
                        if(!use[j]) {
                            next = j;
                            break;
                        }
                    }
                    // 元の山からカードを減らす
                    p.erase(p.end() - ((int)p.size() - i), p.end());
                    add = vector<int>();
                }
            }
        }
        for(int i = 0; i < (int)ans.size(); i++) {
            cout << ans[i] << (i + 1 == (int)ans.size() ? "\n" : " ");
        }
    }
    return 0;
}

おわりに

CのREが消えずに無限に悩んでいました。