Mister雑記

競プロやります。

Codeforces Round 525 (Div.2) A-D

codeforces.com

4完3886点で323位(Rated内260位)。

f:id:misteer:20181205154326p:plain

なんとか紫に戻ることができました。

f:id:misteer:20181205154357p:plain

目次

A. Ehab and another construction problem

codeforces.com

概要

整数 xに対して、以下を全て満たす整数 a, bが存在すれば出力せよ。

  •  1 \leq a, b \leq x
  •  a bで割り切れる
  •  ab \gt x
  •  \frac{a}{b} \lt x

制約

  •  1 \leq x \leq 100

解法

一番素直なのが a, bの全探索。条件の中身を深く考えなくていいので楽。

しかし少し考察をしてみると、 x \gt 1の場合は簡単な解が存在することが分かる。それが a = b = xである。これが上の性質を満たすことは確かめれば分かる。

私は本番では後者で通したのだが、考察に時間がそれなりにかかってしまったので前者の方が実践寄りと言えそうな気がする。もっとプログラムの力に頼っていきたいところ。

実装例

#include <iostream>

using namespace std;

int main() {
    int x;
    cin >> x;

    if (x == 1) {
        // 解無し
        cout << -1 << endl;
    } else {
        // a = b = x
        cout << x << " " << x << endl;
    }
    return 0;
}

B. Ehab and subtraction

codeforces.com

概要

長さ Nの数列 \{a_i\}が与えられる。これに対して以下の操作を K回したときの出力を求めよ。

  1.  \{a_i\}で正の最小の要素( dとおく)を出力する。
    • 全要素が 0の場合は 0を出力して操作を終了する。
  2.  \{a_i\}の各正要素から dを引く。

制約

  •  1 \leq N, K \leq 10^5
  •  1 \leq a_i \leq 10^9

解説

まずこの問題ではindex(数列中の位置のこと)は関係がないので、最初に分かりやすいように数列を昇順にソートしてしまうことにする。

具体例として、 a = \{ 3, 1, 4, 1, 5, 9, 2, 6, 5 \}の場合を考えると以下の通り。

 \displaystyle \{ 3, 1, 4, 1, 5, 9, 2, 6, 5 \} \\
\downarrow sort \\
\{1, 1, 2, 3, 4, 5, 5, 6, 9\} \\
\downarrow print(1) \\
\{0, 0, 1, 2, 3, 4, 4, 5, 8\} \\
\downarrow print(1) \\
\{0, 0, 0, 1, 2, 3, 3, 4, 7\} \\
\downarrow print(1) \\
\vdots

このように操作を考えると、以下の操作と同値であることが分かる。

  1.  \{a_i\} 0を挿入してソートする。
  2.  \{a_i\}から重複を取り除き、各値が高々1度ずつ現れるようにする。
  3. 前から順番に、隣り合う項の差を出力していく。

最初に 0を挿入したのは、最初の要素を出力するときに都合が良いためである。

上と同じ aで考えると、以下の通り。

 \displaystyle \{ 3, 1, 4, 1, 5, 9, 2, 6, 5, 0 \} \\
\downarrow sort \\
\{0, 1, 1, 2, 3, 4, 5, 5, 6, 9\} \\
\downarrow unique \\
\{0, 1, 2, 3, 4, 5, 6, 9\} \\
\downarrow diff \\
\{1 - 0, 2 - 1, 3 - 2, 4 - 3, 5 - 4, 6 - 5, 9 - 6\} \\
= \{1, 1, 1, 1, 1, 1, 3\}

あとはこれの先頭から K個を出力し、足りない分は 0を出力すればOK。

実装例

上のをそのまま実装すると以下のようになる。

std::uniqueを使って重複要素を消す方法については、こちらの記事が参考になるだろう。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> a(N + 1);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    a[N] = 0;

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    // これでaから重複要素が消える

    for (int k = 0; k < K; ++k) {
        if (k < a.size() - 1) {
            cout << a[k + 1] - a[k] << endl;
        } else {
            cout << 0 << endl;
        }
    }
    return 0;
}

なお私は本番ではsetを使って実装した。ただsetを使うとイテレータとかをイジる必要が出てきて、少しC++の知識が必要となる。

C. Ehab and a 2-operation task

codeforces.com

概要

長さ Nの数列 \{a_i\}が与えられる。これに対して以下のいずれかの操作を合わせて N + 1回以下行い、 \{a_i\}狭義単調増加となるようにしたい。

  1.  1 \leq i \leq N 0 \leq x \leq 10^6を指定する。各 1 \leq j \leq iについて、 a_j xを加算する。
  2.  1 \leq i \leq N 1 \leq x \leq 10^6を指定する。各 1 \leq j \leq iについて、 a_j xで割った余りで a_jを置き換える。

これを実現する操作列を出力せよ。

なお、任意の長さ Nの数列は N + 1回以下の操作で狭義単調増加となるようにできることが証明できる。

制約

  •  1 \leq N \leq 2 \times 10^3
  •  0 \leq a_i \leq 10^5

解説

いわゆる構築系の問題、といってもそこまで発想色が強いわけではない。

まず考えられる特異な操作として、「全体を 1で割る」ことが挙げられる。これをするとどんな数列だろうと全要素を 0にできる。 しかし考察をすれば分かるが、この操作が使えるのは狭義単調「減少」にしたいケースである。今回は残念ながら使えない。

構築系は自由度が高いので、できるだけシンプルなケースを構築する方針で考察を進めると上手く行きやすい。そこで今回は目的の数列を \{0, 1, \cdots , N - 1\}に固定して、それを実現する操作を考えることにする。

そしてこれを実現する操作手順の1つが以下の通り。

  1. 後ろから順に、 Nで割った余りが最後の数列と一致するように値を加える。
  2. 全体を Nで割る。

この操作回数は N + 1回とぴったりになりOKとなる。本番はこっちで実装した。

もう1つの解法として、以下のようなものがある。

  1. 全体に Nより大きい適当な値(例えば 5 \times 10^5)を加える。
  2. 先頭から余りが目的の数列と一致するように割っていく。

手前の方はすでに N未満になっているので、大きい数で割れば影響を受けないことを利用した巧い解法。できればこっちも思いつけるようになりたい。

実装例

今回は実装が短くて済む後者を実装することにする。

#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;

    cout << N + 1 << endl;
    // 操作数はN+1で固定

    cout << 1 << " " << N << " " << 500000 << endl;
    // 最初に全要素に500000を足してしまう

    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        a += 500000;

        // aをiにしたい
        // aが十分大きいのでa - iで割ってしまえばいい
        cout << 2 << " " << i + 1 << " " << a - i << endl;
    }
    return 0;
}

もはや競プロあるあるだが、操作数の出力忘れに注意

あと最初に足す値を 10^6にしてしまうと、割る値が 10^6を上回ってWAになるので注意(多分サンプルで落とされる)。

D. Ehab and another another xor problem

codeforces.com

概要

ある固定された整数 a, bがある。あなたはクエリとして整数 c, dを投げることで、以下の返答を受け取ることができる。

  •  a \oplus c \gt b \oplus dなら 1
  •  a \oplus c = b \oplus dなら 0
  •  a \oplus c \lt b \oplus dなら -1

ここで \oplus排他的論理和を指す。

クエリを高々 62回投げることで、 a bを特定せよ。

制約

  •  0 \leq a, b \leq 2^{30}
  • 各クエリについて 0 \leq c, d \leq 2^{30}

解説

上から各bitを決めていくという方針で考える。

 kbit目より上は特定済みとしよう。このとき、 c, dをこの特定済みのものにすることで kbit目より上を全て0にできる。

このとき kbit目を求めたい。そこで、 (c + 2^k, d + 2^k)をクエリに投げてみる。このとき、加える前と後で大小関係が変化したか否かで場合分けをする。


大小関係が変化した場合

このとき kbit目は a, bで異なるものになっている。 (c, d) a \oplus c \gt b \oplus dなら a, b kbit目はそれぞれ 1, 0となる。逆もまた然り。

大小関係が変化しなかった場合

このとき kbit目は a, bで同じものになっている。これが 0 1かを決めるために、追加で (c, d + 2^k)を投げる。 a \oplus c \gt b \oplus (d + 2^k)なら 1、そうでなければ 0であることが確定する。


こんな具合に c, dを更新していくと、各bitを 2回のクエリで特定できるため最初に (0, 0) a, bの大小比較をする分と合わせて 61回のクエリで答えが求まる。

実装例

自画自賛だがこの実装はスマートな方だと思う。具体的な大小関係をあまり気にしなくていいのが大きい。

#include <iostream>

using namespace std;

// クエリを投げる関数
int question(int c, int d) {
    cout << "? " << c << " " << d << endl;
    int ret;
    cin >> ret;
    return ret;
}

int main() {
    int c = 0, d = 0;

    // 現在のc, dでのa^cとb^dの大小関係を保持
    int stat = question(c, d);

    for (int k = 29; k >= 0; --k) {
        int ret = question(c + (1 << k), d + (1 << k));

        if (ret == stat) {
            // 大小関係に変化なし = k桁目は同じ

            int ret = question(c, d + (1 << k));
            if (ret == 1) {
                c += (1 << k);
                d += (1 << k);
            }
            // この更新で大小関係に変化はないのでstatはそのまま

        } else {
            // 大小関係が変化 = k桁目は異なる
            // 元の大小関係でどちらが1かが分かる
            if (stat == 1) {
                c += (1 << k);
            } else {
                d += (1 << k);
            }

            // この更新では大小関係が変化しうるのでstatも更新
            stat = question(c, d);
        }
    }

    cout << "! " << c << " " << d << endl;
    return 0;
}

感想

  • Cがあまりにも遅かった。
  • その分Dが考察、実装ともにスムーズにいったので無事紫に戻れた。
  • 深夜は集中力が続かない。