Mister雑記

競プロやります。

Codeforces Round 534

Div2 A-D(Div1 A-B)を解説。Dは特に詳しく。

codeforces.com

目次

A. Splitting into digit

Problem - A - Codeforces

概要

整数 nが与えられる。このとき、以下を満たす整数列 \{ d_i \}で、出現する値の種類が最も少ないものを1つ出力せよ。

  •  1 \leq d_i \leq 9
  •  \sum d_i = n

制約

  •  1 \leq n \leq 1000

解説

理論値はもちろん「1種類」、つまり全ての要素が同じ数列である。

実はこれは「 1 n個並んだ数列」によって常に実現することができる。

実装例

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    // 長さはN
    cout << N << endl;
    
    // 1をN回出力
    for (int i = 0; i < N; ++i) {
        cout << 1 << " ";
    }
    cout << endl;
    return 0;
}

B. Game with string

Problem - B - Codeforces

概要

文字列 sについて、2人のプレイヤーがゲームをする。

各プレイヤーは自分のターンで、 sから「同じ文字からなる長さ2の連続部分列」を1つ消す。その後ターンは相手に移る。

最終的に、自分のターンで連続部分列を消せなくなった方が負けとなる。

2人のプレイヤーが最適に行動したとき、先手と後手のどちらが勝つか求めよ。

制約

  •  1 \leq |s| \leq 10^5

解説

まず、このゲームの勝敗は2人の手順(どの順番に連続部分列を消したか)に依存しない。よって貪欲に前から連続部分列を消していき、消した回数の偶奇を調べればよい。

しかし、これを愚直にシミュレートすると O(|s|^2)かかってしまい、制約的にとても厳しい1。そこでこれをstackを利用することで高速化する。

stackによるシミュレート方法は以下の通り。

  • 今見ている要素とstackの末尾を比較する。
    • 同じだったら、stackの末尾を削除する。
    • 違かったら、stackの末尾にその文字を挿入する。

このアルゴリズム計算量は O(|s|)なので余裕で間に合う。ちなみにこれは「括弧マッチング」のアルゴリズムを複数種類の文字に拡張したものとも言える。

実装例

以下ではstd::stringをstackとして使っている。std::stringの中身は概ねstd::vectorと同じなのでこのような使い方ができる。

#include <iostream>
#include <string>

using namespace std;

int main() {
    string S;
    cin >> S;

    int cnt = 0;
    string stack;
    for (char c : S) {
        if (stack.back() == c) {
            // 末尾と一致したらpop
            ++cnt;
            stack.pop_back();
        } else {
            // 末尾と異なればpush
            stack.push_back(c);
        }
    }

    cout << (cnt % 2 > 0 ? "Yes" : "No") << endl;
    return 0;
}

C. Grid game

Problem - C - Codeforces

概要

 4 \times 4のグリッドに、 1 \times 2のタイルと 2 \times 1のタイルを配置していく。タイルは回転させたり重ねて置くことはできない。

また全てのマスがタイルで埋まっている行/列がある場合、その行/列上にあるタイルは埋まった瞬間に全て消える。

タイルを置く順番が文字列 sとして与えられるので、それらのタイルの置き方を1つ出力せよ。

制約

  •  1 \leq |s| \leq 1000

解説

様々な解法が考えられる問題だが、私の解法は以下の通り。

まず縦タイル( 2 \times 1)は上から2行、横タイル( 1 \times 2)は3行目にだけ置くことにする。

そしてどちらも左端から順に置いていく。縦タイルは4枚、横タイルは2枚揃うとタイルが消えるので、そしたら再び左端から置き始めればよい。

実装

#include <iostream>
#include <string>

using namespace std;

int main() {
    string S;
    cin >> S;

    int ver = 0, hol = 0;
    for (char c : S) {
        if (c == '0') {
            // 縦タイル (1,1)->(1,2)->(1,3)->(1,4)->(1,1)->...
            cout << 1 << " " << ver + 1 << endl;
            ver = (ver + 1) % 4;
        } else {
            // 横タイル (3,1)->(3,3)->(3,1)->...
            cout << 3 << " " << hol + 1 << endl;
            hol = (hol + 2) % 4;
        }
    }
    return 0;
}

D. Game with modulo

Problem - D - Codeforces

概要

以下のクエリを 60回まで投げることで、整数 aの値を特定せよ。

  • 2つの整数の組 x, y ( 0 \leq x, y \leq 2 \times 10^9)を投げる。
  •  (x \bmod a) \lt (y \bmod a)ならy、そうでなければxが返ってくる。

制約

  •  1 \leq a \leq 10^9

解説

まずこれはとても重要なのだが、インタラクティブ問題の大半は二分探索である。この問題も類に漏れないどころか、クエリ回数上限が 60という時点で二分探索確定である( \because 10^9 \simeq 2^{30})。

コンテスト中は「二分探索を使うっぽい」ということは分かったのだが、どうやって解の範囲を絞り込むのかがまるで思いつかないままコンテストが終わった。悲しい。


以下解説。

本質だけを抜き取ると、この問題のクエリは以下の性質を持つ。

  • 2つの整数の組 x, y ( x \lt y \leq 2x + 1)を投げる。 yの上限に注意。
    •  y \lt aならばyを返す2
    •  x \lt a \leq yならばxを返す3
    •  a \leq xでは何を返すか分からない

証明は脚注を参照のこと。

これを使うことで、2つのパートに分けて aを特定することができる。

前半

まず、 2^k \leq a \lt 2^{k + 1}を満たす kを求める。

これは (2^i - 1, 2^{i + 1} - 1) i = 0, 1, 2, \dotsの順に投げることで求められる。具体的には、初めてxが返ってきたときの iが条件を満たす kである。

後半

次いで、 [2^k, 2^{k + 1})から具体的な aを探索する。

ここで、 x = 2^k - 1と固定してしまう。すると、上の性質は以下のように言い換えられる。

  • 整数 y ( 2^k \leq y \lt 2^{k + 1})を投げる。
    •  a \gt yならばyを返す。
    •  a \leq yならばxを返す。

この形になってしまえば、二分探索はとても容易い。これで aが求まった。

実装例

一番外のループは非本質なので省いた。

#include <iostream>

using namespace std;

void answer(int x) {
    cout << "! " << x << endl;
}

// (x, y)でクエリを投げ、xならtrueを返す
bool query(int x, int y) {
    cout << "? " << x << " " << y << endl;

    char res;
    cin >> res;
    return res == 'x';
}

void solve() {
    // 前半
    int k;
    for (k = 0; k < 30; ++k) {
        // (2^k-1, 2^(k+1)-1)でクエリを投げ、xが来たら終了
        if (query((1 << k) - 1, (1 << (k + 1)) - 1)) break;
    }

    // 後半
    int l = (1 << k) - 1, r = (1LL << (k + 1)) - 1;
    // a in (l, r]
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (query((1 << k) - 1, mid)) {
            // (2^k, mid)でxが来た <-> a <= mid
            r = mid;
        } else {
            l = mid;
        }
    }

    answer(r);
}

前にも言った気がするが、インタラクティブ問題における実装はクエリを投げる専用の関数を作ると格段に書きやすくなる。

感想

  • コンテストとしては5分1完なので精神的にキツかった。
  • 紫に落ちた。
    • Div1で2完安定しないと黄色維持は厳しい。
  • D好き。
    • 解説記事書いて好きになるタイプの問題。

  1. 「連続部分列を消しながらイテレートする」という方法で通している人もいるが、危険なのでオススメはしない。

  2.  x \bmod a = x, y \bmod a = y x \lt yよりyが返ってくる。

  3.  x \bmod a = x, y \bmod a = y - a。さらに y - a \leq (2x + 1) - a \leq (2x + 1) - (x + 1) = x x \geq y - aよりxが返ってくる。