Mister雑記

競プロやります。

Codeforces Round #487 (Div2)

久々のCodeforcesコンテスト。昨日はABCの方に専念したが、今日は他にやることもない1のでもちろん参加。 しかしこれが中々に疲れたコンテストになりました。

Eは問題を見てすらいないので本記事では触れません、悪しからず。

ちなみに問題名の和訳はオリジナル。センスなくても許して。

目次

A. A Blend of Springtime (混じり合う春花)

問題リンク

超要約

A,B,C,.の4文字からなる文字列が与えられる。 このとき、連続する長さ3の部分文字列でA,B,Cを1つずつ含むものがあるか判定せよ。

解説

本質的には上の通りなのだが、問題文がめちゃくちゃ読みづらい。 「花が枯れる」とか「種が広がる」とか結局何が言いたいんだ。

しかし忘れてはならない。これこそがCodeforcesである。2

何にせよ提出コードは以下の通り。簡単な尺取り法。

int main() {
    string S;
    cin >> S;
    V<int> cnt(3, 0);
    // 区間に含まれるA,B,Cの数を数える

    REP(i, SIZE(S)) {
        if (S[i] != '.') {
            cnt[S[i] - 'A']++;
        }

        bool flag = true;
        REP(j, 3) {
            if (cnt[j] == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << "Yes" << endl;
            return 0;
        }

        // 外れる要素を抜くのをお忘れなく
        if (i >= 2) {
            cnt[S[i - 2] - 'A']--;
        }
    }
    cout << "No" << endl;
    return 0;
}

もちろん尺取りじゃなくて地道に全探索しても余裕で通る。

AtCoderなら200点ってところだろうか。

B. A Tide of Riverscape (満ち干く河)

問題リンク

要約

1,0,.からなる文字列が与えられる。 .を1か0に置き換えることで、i文字目とi + p文字目が異なるようなiが存在するようにできるか判定せよ。

出来なければNoを出力、出来るなら条件を満たすように置き換えた例を1つ出力せよ。

解説

Aに比べれば趣旨は理解しやすいし、さして難しくもない。 順番にi文字目とi + p文字目を比較して、どちらか一方でも.ならYesで適切に置き換え、そうでなくても文字が異なればYes。

ただこの問題、曖昧なのがp=nのケース。問題文からこれがYesなのかNoなのかがよく分からない。 私はNoにしたけど通ったので、もしかしたらテストに入っていないのかもしれない3

で、提出したのがこれ。

int main() {
    const string num = "01";
    // .に値入れるときに使う

    int N, p;
    cin >> N >> p;

    string S;
    cin >> S;

    bool judge = false;
    REP(i, N - p) {
        if (S[i] != '.' && S[i + p] != '.' && S[i] == S[i + p]) continue;

        // 上の条件を満たさないiが1つでもあればYes
        judge = true;

        if (S[i] == '.' && S[i + p] == '.') {
            // 両方.ならとりあえず0と1に変える
            S[i] = num[0];
            S[i + p] = num[1];
        } else if (S[i] == '.') {
            // 一番上のnumを使って、.じゃない方と被らないように変える
            S[i] = num[(S[i + p] - '0' + 1) % 2];
        } else if (S[i + p] == '.') {
            S[i + p] = num[(S[i] - '0' + 1) % 2];
        }
    }

    if (!judge) {
        cout << "No" << endl;
        return 0;
    }

    for (char c : S) {
        // N-pからpは調べてないので、.が残っていることに注意
        if (c == '.') {
            cout << 1;
        } else {
            cout << c;
        }
    }

    cout << endl;
    return 0;
}

通ったはいいがイマイチ釈然としない。 普通に落ちてもおかしくなかったし、問題に落ち度があるとしか思えない。

細かいところを無視すれば、AtCoderなら300点の下位といったところだろうか。

C. A Mist of Florescence (霞みの中の花畑)

問題リンク

概要

A,B,C,Dが書かれたグリッドについて、互いに隣接しあった同じ文字の集団をグループとする。 このとき、A,B,C,Dのグループ数がそれぞれa, b, c, dになるように長方形のグリッドを作成せよ。グリッドのサイズは制約内なら不問。

解説

俗に言う構築系問題。解法によっては瞬殺のひらめき勝負。

  1. 50 × 50のグリッドを用意します。
  2. 上半分をA、下半分をBで埋めます。
  3. 上半分にc個のCとb-1個のBを1マス間隔で埋めます(詳しくは下図)。
  4. 同様に下半分にd個のDとa-1個のAを埋めます。
  5. 出力します。

例えば10 15 20 25の場合の出力は、グリッドを20 × 20とすると以下の通り。

CACACACACACACACACACA // Cを20個埋める
AAAAAAAAAAAAAAAAAAAA
CACACACACACACACACACA
AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA
BABABABABABABABABABA // Bを14個埋める
AAAAAAAAAAAAAAAAAAAA
BABABABAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBB
ABABABABABABABABABBB // Aを9個埋める
BBBBBBBBBBBBBBBBBBBB
DBDBDBDBDBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBB
DBDBDBDBDBDBDBDBDBDB
BBBBBBBBBBBBBBBBBBBB
DBDBDBDBDBDBDBDBDBDB // Dを25個埋める

そしてこれを実現するコードがこちら。

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    cout << 50 << " " << 50 << endl;
    V<string> pic(50, string(50, 'B'));
    // 全部Bで埋める

    REP(i, 25) {
        // 上半分をAで埋める
        pic[i] = string(50, 'A');
    }

    REP(i, c) {
        // Cをc個、1マス間隔で置いていく
        pic[(i / 25) * 2][i % 25 * 2] = 'C';
    }

    REP(i, b - 1) {
        pic[(i / 25) * 2 + 10][i % 25 * 2] = 'B';
    }

    REP(i, d) {
        pic[49 - (i / 25) * 2][i % 25 * 2] = 'D';
    }

    REP(i, a - 1) {
        pic[39 - (i / 25) * 2][i % 25 * 2] = 'A';
    }

    for (string s : pic) {
        cout << s << endl;
    }

    return 0;
}

「こんな解法思いつくか!」って?私も初見はそう思った。 だが初見ではないんだなこれが。

初見だった人はこの問題を解いてみましょう。↓

AtCoder Beginner Contest 089-D 「Grid Components」

というわけでAtCoderなら500点相当の問題。

解説にも書かれていたが、人によって全然実装方法が違うのが面白い。

D. A Shade of Moonlight (陰る月光)

問題リンク

概要

数直線上に長さlの雲がn個浮かんでおり、それぞれ速度1か-1で動いている。

ある雲のペアについて、絶対値がw以下の風を吹かせることで、同時刻にどちらの雲も原点にある月を覆うようにしたい(風速はペアごとに独立でよい)。

このようにできる雲のペアはいくつあるか。

感想

クソ重い幾何問題。 式をコネコネしている間に頭がこんがらがって、結局戦意喪失という結果に。キツかった。

解説はどう説明しているのかと気になって見てみたら、時間軸を取ることで二次元問題にして全体像を目視できるようにし、さらに月を風で動かすことにすることで単純化していた。

なるほど、賢い。特に前者は他の問題でも応用が効きそうな発想。 それでも答えは相当煩雑っぽいが。

コンテスト中の正答者数が50人程度だった辺り、Dにしては相当の難問だったようだ。早々に見限ってhackに移ればよかったかな〜4とか思ったり思わなかったり。

感想

全体的にう〜んな感じのコンテストだった。 Bについてはこれ以上言うこともなし。 Cに関しては初見だったら相当厳しかっただろうが、初見じゃないこと自体が精進の現れでもある。

なお、成績はいつも通り3完、全体231位(Rated内で202位)で過去最高記録。Dが超絶重いタイプの問題だったおかげでもある。 f:id:misteer:20180612124819p:plain

ちなみに5日後の6/17(Sun)にRound #488があるらしい、日本時間で01:35から。殺す気か。

あと例によって幾分見やすいだろうHackMD版のリンクも貼っておきます。 Codeforces Round #487 (Div2) LOG


  1. 中間試験……

  2. 次回からは素直にgoogle先生にぶん投げることを決意。

  3. でもこれ普通に考えてYesじゃない?なんで通ったんだろうか。

  4. 実は今まで参加してきたコンテストでは一度もhackしたことがない。lockしてからミスに気づいたら悲しいじゃんね。