【AtCoder】ABC 466 C - Count Close Pairs

C - Count Close Pairs

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 658 / NoviSteps: 2Q / 配点: 300 点

問題概要

数直線上に、点 $1$, $2$, $\ldots$, $N$ が 左から右に並んでいる。

最初、あなたには整数 $N$ のみが与えられる。

その後、あなたはジャッジに以下の質問を $2N$ 回まで行うことができる。

• ? i j: $1 \leq i < j \leq N$ を満たす整数 $i,j$ を選び、点 $i$ と点 $j$ の距離が $1$ 以下であるか質問する。

距離が $1$ 以下である場合は Yes、そうでない場合は No として、質問の答えがジャッジから標準入力に返される。

距離が $1$ 以下の $2$ 点組の個数 $X$ を以下の形式で出力せよ。

• ! X

制約

• $2 \leq N \leq 10^3$

考察

ABCでは見慣れないインタラクティブ問題。

数直線上での点 $i$ の座標を $x_i$ とする。

点 $i$ に対して、自身よりも右側にあって、距離が $1$ 以下のもので最大の番号の点を $r_i$ とする:

このとき、点 $i$ と組にできる点の個数は、$i+1, i+2, \ldots, r_i$ の $r_i - i$ 個であるから、答えは

となる。

ここで重要なのが、$r_i$ は単調増加するということである。

なぜなら、組 $(i, r_i)$ の距離が $1$ 以下であるなら、組 $(i+1, r_i)$ の距離も $1$ 以下であり、

が成り立つからである。

したがって、 $i = 1, 2, \ldots, N$ に対して、尺取り法の要領で $r_i$ を単調増加に求めることができる。

? i j という質問の答えについて、

• Yes: $r_i \geq j$ であることがわかるので、$r_i$ を右に動かすことができる。
• No: $r_i < j$ であることがわかるので、今の $i$ の探索を終了して $i$ を右に動かすことができる。

という動きをすれば、質問回数は最大でも $2(N-1)$ 回で済む。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.template <typename T>
7.inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
8. 
9.// ======================================== //
10. 
11.bool query(int i, int j) {
12.    cout << "? " << i << " " << j << endl;
13.    cout << flush;
14. 
15.    string res;
16.    cin >> res;
17. 
18.    return res == "Yes";
19.}
20. 
21.int main()
22.{
23.    int N;
24.    cin >> N;
25. 
26.    int ans = 0;
27.    int right = 1;
28.    rep(left, 1, N + 1) {
29.        chmax(right, left);
30. 
31.        while (right + 1 <= N) {
32.            if (query(left, right + 1)) {
33.                right++;
34.            }
35.            else {
36.                break;
37.            }
38.        }
39. 
40.        ans += right - left;
41.    }
42. 
43.    cout << "! " << ans << endl;
44.    cout << flush;
45. 
46.    return 0;
47.}

https://atcoder.jp/contests/abc466/submissions/77357893

atcoder.jp

実装時間: 10分

コメント

かなり久々のインタラクティブ問題でぎょっとしたが、尺取り法そのままで解くことができ一安心。