CODE FESTIVAL 2017 予選A 参加記

結果

A,B,C問題を解いて3完。C問題でかなり手間取ってしまったのが痛かった。時間があってもD問題を解けたがどうかはわからないが、しっかり考えてみたかった。

　一応CODE FESTIVALの方にエントリーはしてみているけど、まぁ無理だわな。

A問題

　substrで先頭4文字だけ取ってきて比較するだけ。今考えると4文字未満のときを考慮してなかったのでC++の仕様に救われたか。まぁ親切にも入力例3で3文字のケースがあるので、問題があってもWA出す前に気づけてはいたと思うけど。

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

int main()
{
    string S;
    cin >> S;
    if (S.substr(0, 4) == "YAKI")
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B問題

　2回押すと元に戻るだけだから各ボタンについて押すか押さないかだけが重要。

　行ボタンのうちi個、列ボタンのうちj個を選ぶと $i \times M + (N - i) \times j - i \times j$ 個が黒くなるはずで、それで解ける。

　コードだと頭が悪くて列を先に押すのと行を先に押すので結果が変わると勘違いしている。何をやっているんだ。普通に二つとも同じ式じゃないか……。というか順番によって結果が変わると思ってしまうのがかなりセンス悪い気がする。頑張ろうな。

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

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= M; ++j) {
            if (i * M + (N - i) * j  - i * j== K
                    || j * N + (M - j) * i - i * j== K) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

C問題

　最初は

HとWが両方奇数のとき、奇数個の文字が1個、それ以外の文字は偶数個
そうでないとき全部の文字が偶数個

で解けると勘違いしてコードを書き始めてしまったんだけど、入力例2で失敗してちょっと困る。ここで小手先の回避方法として

HとWが両方2以上の時は4回以上表れている文字が最低1個は必要

という条件を付け足して、とりあえずサンプルだけ通るようにして提出してしまい、当然WA。

　しばらく考えてから、4個必要になる領域は角だけじゃないことに気づいて、HとWの偶奇によって偶偶 or 奇奇 or 偶奇(奇偶)で場合分けして書き直したが、まだ1個だけWAが出るようになった。

　どうしてもわからなかったのでそれぞれの場合分けに一個ずつassert(false)を仕込んでみたところ、奇奇のところでWAがREになったので、ここで変なことが起きていると判断した。今回はペナルティがなしということだってのでこういう邪悪なハックをやることに対する抵抗がちょっと小さかった。

　で、何が間違っていたかというと、4個以上出てくる文字が奇数になっている場合というのを考慮していなかった。たとえばaが5個出てきて、1個を中央に使って4個を対象的に使うとか、そういうことがありえるんだ。気づいたらすぐ直せてAC。結構大変だった。

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0;
    int num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    if (H % 2 == 0 && W % 2 == 0) {
        if (odd_num == 0 && H * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else if (H % 2 == 1 && W % 2 == 1) {
        if (odd_num == 1 && (H - 1) * (W - 1) <= num4 * 4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    } else {
        //必ずHが奇数ということにする
        if (H % 2 == 0)
            swap(H, W);

        if (odd_num == 0 && (H - 1) * W / 4 <= num4)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

　場合分けが美しくないと思ったのでちょっと書き直してみた。まぁ本番でこれを書きにいくことはしないかなぁ。でもこれの方が解法をちゃんと理解した上でのコードっぽい気はする。

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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> a(H);
    vector<int> num(26, 0);
    for (int i = 0; i < H; ++i) {
        cin >> a[i];
        for (char c : a[i]) {
            num[c - 'a']++;
        }
    }
    int odd_num = 0, num4 = 0;
    for (int i = 0; i < 26; ++i) {
        num4 += num[i] / 4;
        if (num[i] % 2 == 1) {
            odd_num++;
        }
    }

    //4個使う領域(たとえば右上)を求めるときの長さ
    int h = (H % 2 == 0 ? H / 2 : (H - 1) / 2);
    int w = (W % 2 == 0 ? W / 2 : (W - 1) / 2);

    if (odd_num == (H % 2 == 1 && W % 2 == 1)
            && h * w <= num4)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

D問題

　時間もなかったので、単純にRYGBの順で塗れるだけ塗ってみるとか、できるだけバランスよく塗ってみるとか、簡単な方法で貪欲にやっていくのを試してみたけどWA。間違ってるパターンをいろいろ出してみて眺めているうちに時間切れ。

　ある場所に対して同じ色を塗れない位置が角の利きに似ているので一瞬Rotated Bitboardみたいな考え方が頭をよぎったんだど、それを推し進めることができなかった。マンハッタン距離は45度回転させてみるというの、ちょっと気に留めておいていいパターンだと思う。