【Codeforces】Round 73(div.2)を振り返る

Codeforcesに初参加した

　海外競技プログラミングコンテストのCodeforcesに初参加してきたので、解けた問題だけ備忘録的に置いておきます。

コンテストページはこちら
2019/9/19(木)23:35開催(日本時間)
Educational Codeforces Round 73 (Rated for Div. 2)

A-2048 Game

　2のべき乗数がN個与えられるので、それらのいくつかを使って2048という数値を作ることが出来るかという問題。結論から言うと2048から大きい入力を順番に引いていき、ぴったり0になれば解ける。ただし入力の制約条件内に2048よりも大きな数値があるので(最大で2の29乗)標準入力の段階で2048より大きな数値は無視して対策する。元々2048が入力に含まれている場合はなにも処理しなくてよい。

入力例
5
4096 1024 512 512 32
出力> YES

2048-1024-512-512 = 0となるので答えはYES

6
2048 256 512 1024 1 1
出力> YES

すでに入力に2048があるのでYES
2048-2048 = 0としてもよい

以下、実装例です

A_sample.cpp

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)

using namespace std;

void solve() {
    int n; cin >> n; // 要素数
    vector<long long> S; // ２のべき乗数を格納する配列

    long long tmp;
    rep(i, n) {
        scanf("%lld", &tmp);

        // 2048より大きい数は不要
        if (tmp <= 2048) S.push_back(tmp);
    }

    // 降順ソート(2048, 1024, 512, 512...)
    sort(S.begin(), S.end(), greater<int>());

    bool flag = false; // 2048が作れるか管理するフラグ
    long long res = 2048;

    rep(i, S.size()) {
        res -= S[i]; // 2048から2のべき乗数を引いていく
        if (res == 0) {
            flag = true; // 2048が作れた！
            break;
        }
        else if (res < 0) { // 2048が作れなかった
            break;
        }
    }

    // flag == trueならYES、そうでないならNO
    cout << (flag ? "YES" : "NO") << endl;
}

int main(void) {
    int q; cin >> q; // クエリをq回回す
    rep(i, q) solve();

    return 0;
}

ちなみに非常に初歩的なことなのですが、rep(i, n)というのはfor文をマクロ化したもので競プロ界隈ではfor文書くのがめんどいって人がよく多用するテクニックらしいです。私も最近知りました。

rep_sample.cpp

// for文をマクロ化
#define rep(i, n) for(int i=0; i<n; i++)

// 使用例
rep(i, n) {
    print("%d\n", i);
}

B-Knights

　チェスの駒の一つである白と黒のナイトを二次元の縦横マスに配置して戦わせることを考える。白と黒のナイトを空白マスのないように配置してバトルの回数が最大となるようにせよ。白と黒のナイトがお互いに攻撃圏内にいるときバトルすると考える。

という問題。上図において青の位置に置いた駒から見て、赤色のマスが攻撃圏内に入る。つまり青と赤はなるべく異なる駒を配置したいということになる。

入力はNだけでN×Nのボードが与えられ、そのマス（二次元配列）に"W"、"B"(白か黒)を入力して回答する。上手くバトルの回数を最大化出来る駒配置を考えるのだが、これも結論から言うと、チェッカーフラッグのように白と黒を交互に並べていくとAcceptとなる。N=3, 4, 5...と順番に図を描いてみるとよくわかると思う。

以下実装例です。

B_sample.cpp

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n; cin >> n; // ボードの幅、もしくは高さ
    bool rev = false; // 各行の先頭要素をW, Bを入れ替えてチェッカーになるようにする

    // チェッカーフラッグのようにW,Bを配置していく
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (rev) {
                if (j % 2 == 0) cout << "B";
                else cout << "W";
            }
            else {
                if (j % 2 == 0) cout << "W";
                else cout << "B";
            }
        }
        rev = (1 - rev);
        cout << endl;
    }
}

int main(void) {
    solve();
    return 0;
}

C-Perfect Team

　コーダーと数学者と専門無しの3タイプの人間がそれぞれc, m, x人ずつ与えられ、3人のチームを複数個作りたい。ただしコーダーと数学者はそれぞれどのチームにも最低1人以上は入っていないといけない。作ることの出来るチームの数の最大はいくらか。

という問題。例えばコーダーcが1人、数学者mが1人、専門無しxが1人いれば１つのチームが作れる。しかしコーダーが1人あるいは数学者が1人で専門無しが2人とかだとチームを作ることが出来ない。逆にコーダーが2人、数学者が1人、専門無しが0人でも1つのチームを作ることが出来る。

入力例
(c, m, x) = (コーダー、数学者、専門無し)
1 1 1
出力> 1
コーダーと数学者と専門無しで1つのチームを作ることができ、かつそれが最大です。

3 6 0
出力> 3
コーダー1人、数学者2人、専門無し0人の3人チームが最大で3組作ることが出来ます。

0 0 0
出力> 0
人手不足です。

0 1 1
出力> 0
人手不足です。

10 1 10
出力> 1
数学者が一人しかいないので、コーダー2人、数学者1人、専門無し0人か、コーダー1人、数学者1人、専門無し1人の1チームしか作ることが出来ません。

4 4 1
出力> 3
コーダー1人、数学者1人、専門無し1人のチームと、コーダー2人、数学者1人、専門無し0人のチームと、コーダー1人、数学者2人、専門無し0人のチーム
の合計3チームを作ることが出来ます。

解法への考え方として、まず作れるチームは高々(c+m+x)/3です。体育館に1クラスの生徒を全員集めて3人チームを組んだら何チーム出来るか、というような感じです。30人いれば10チーム出来上がります。そこから1チーム内には最低でもコーダー1人以上、数学者が1人以上在籍していないとだめなわけなので、コーダーの数、もしくは数学者の数の小さいほうを答えとして出力すればAcceptとなります。

以下実装例です。

C_sample.cpp

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)

using namespace std;

void solve() {
    long long c, m, x; // コーダー、数学者、専門無し
    long long sum, minv;
    scanf("%lld%lld%lld", &c, &m, &x);
    sum = (c + m + x) / 3; // 高々作れるチームの数
    minv = min(c, m); // コーダー、数学者の内小さいほう
    cout << min(sum, minv) << endl;
}

int main(void) {
    int q; cin >> q;
    rep(i, q) solve(); // q回クエリを回す
    return 0;
}

D以降

　とりあえず疲れたのでこれ以上の解説は上級者の方に任せます。また解けたら追記します。

誤りや質問ありましたらコメントお願いします。