【AtCoder】ABC 444 C - AtCoder Riko

C - AtCoder Riko

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

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 582 / NoviSteps: ??? / 配点: 350 点

問題概要

長さ $N$ の正整数列 $A$ が与えられる。 以下のようなことが起こりうる正整数 $L$ をすべて求めよ。

カップの中に長さ $L$ のAtCoderりこが何本か入っている。 高橋君がこのカップをシェイクしたところ、それぞれのAtCoderりこは以下のいずれかの状態になった。

• 長さが $L$ である $1$ 本のAtCoderりことしてそのまま残った。
• 長さの和が $L$ であるような $2$ 本のAtCoderりこに分かれた。ただし、各 AtCoderりこの長さは正整数である。

カップをシェイクした後、カップの中には $N$ 本のAtCoderりこが入っており、$i$ 本目の AtCoderりこの長さは $A_i$ であった。

制約

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 条件を満たすような $L$ が少なくとも $1$ つ存在する
• 入力される値は全て整数

考察

シェイクすることで折れたAtCoderりこは、長さとしては短くなるので、 $A$ の要素の中で小さいものになるはず。

したがって、 $A$ を昇順ソートすることによって、折れたAtCoderりこは前方に、 折れていないAtCoderりこは後方にまとまることが期待できる。

折れたAtCoderりこの本数を $m$ とすると($m$ は偶数)、 $A$ の最初の $m$ 本が折れたAtCoderりこ、 残りの $N-m$ 本が折れていないAtCoderりことなる。

$m = 0$ (折れたAtCoderりこが $0$ 本) の場合

このとき、全てのAtCoderりこは長さ $L$ のままであるはずである。

$A$ はソートされているはずなので、 $A_1$ と $A_N$ が等しければ、 $L = A_1$ が成立する。

$2 \leq m \leq N$ (折れたAtCoderりこが $2$ 本以上) の場合

$L = A_1 + A_{m}$ が候補となる。

$m < N$ のとき、折れていないAtCoderりこが存在し、その長さは $L$ と等しくなければならない。 これは先ほどと同様に、 $A_{m+1}$ と $A_N$ が $L$ と等しいかどうかを確認することで判定できる。

さらに、折れたAtCoderりこが $m$ 本あるとき、 $i$ 番目に短いAtCoderりこと $m-i+1$ 番目に短い(折れた $m$本の中で $i$ 番目に長い)AtCoderりこがペアになって長さ $L$ になるはずである。

したがって、 $i = 1, 2, \cdots, \frac{m}{2}$ について、 $A_{i} + A_{m-i+1} = L$ であるかどうかを確認すればよい。

これらの条件を満たす $L$ は本問の答えとして成立する。

答えとなる $L$ は複数存在する可能性があるため、setなどを用いて重複を排除しつつ格納しておくとよい。

実装例

実装は0-indexedで行っていることに注意。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define all(x) (x).begin(), (x).end()
5.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
6. 
7.using ll = long long;
8. 
9.// ======================================== //
10. 
11.int main()
12.{
13.    int N;
14.    cin >> N;
15.    vector<ll> A(N);
16.    rep(i, 0, N) cin >> A[i];
17. 
18.    sort(all(A));
19. 
20.    set<ll> ans;
21. 
22.    if (A[0] == A[N - 1])
23.        ans.insert(A[0]);
24. 
25.    for (int m = 2; m <= N; m += 2)
26.    {
27.        ll L = A[0] + A[m - 1];
28.        if (m < N)
29.        {
30.            if (A[m] != L || A[N - 1] != L)
31.                continue;
32.        }
33. 
34.        bool flag = true;
35.        rep(i, 1, m / 2)
36.        {
37.            if (A[i] + A[m - 1 - i] != L)
38.            {
39.                flag = false;
40.                break;
41.            }
42.        }
43. 
44.        if (flag)
45.            ans.insert(L);
46.    }
47. 
48.    for (auto &&x : ans)
49.    {
50.        cout << x << " ";
51.    }
52.    cout << endl;
53. 
54.    return 0;
55.}

https://atcoder.jp/contests/abc444/submissions/73070639

atcoder.jp

実装時間: 25分

コメント

AtCoderりこ、ネーミングもうちょっと何とかならんかったんか？？？ 言いにくすぎだろ。