問題一覧 > 通常問題

No.3531 Erase Pair

レベル : / 実行時間制限 : 1ケース 0.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : yu23578 / テスター : aa36 Yoyoyo8128 yt142857 Germanium32 GaLLium
ProblemId : 13080 / yukicoder contest 聖光学院プログラミングコンテスト2026 day2 (順位表) / 自分の提出
問題文最終更新日: 2026-05-04 21:28:47
yukicoder contest 聖光学院プログラミングコンテスト2026 day2の他の問題:

注意

この問題の実行制限時間は $500 \mathrm{ms}$ です。

問題文

$T$ 個のテストケースに対して、以下の問題に解答してください。

長さ $N$ の整数列 $A$ が与えられます。聖くんはこの数列を使って以下のゲームをします。

$|A| \ge 2$ である時、以下の操作を行う。
  • 整数 $i,j(1 \le i < j \le |A|)$ を選び、 $A$ の中に $A_i + A_j$ が含まれないならば、 $A_i$ と $A_j$ を $A$ から取り除き、残った要素をそのままの順番でつなげる。

$|A| \le 1$ になるまで操作を行うことが出来るならば Yes を、出来ないならば No を出力してください。ただし、 $|A|$ で数列 $A$ の長さを表すこととします。

制約

  • $1 \le T \le 2 \times 10^5$
  • $2 \le N \le 2 \times 10^5$
  • $|A_i| \le 10^9$
  • 各テストケースにおける $N$ の総和は $2 \times 10^5$ 以下
  • 入力はすべて整数

入力

$T$
$Testcase_1$
$Testcase_2$
$Testcase_3$
$\vdots$
$Testcase_T$

各テストケースは以下の形式で与えられる。 

$N$
$A_1\ A_2\ A_3\ \cdots\ A_N$

出力

$T$ 行に出力してください。
$i$ 行目には、 $Testcase_i$ に対する答えを出力してください。

サンプル

サンプル1
入力
3
3
3 1 4
4
2 0 2 6
4
-1 9 -5 8
出力
Yes
No
Yes

$1$ つ目のテストケースに関して、例えば $A_1 + A_3 = 7$ で、 $7$ は $A$ に含まれていないため、 $A_1$ と $A_3$ のペアを消して $|A| \le 1$ を達成できます。
また、 $A_1 + A_2 = 4 = A_3$ より $A_1$ と $A_2$ のペアを消すことは出来ません。

$2$ つ目のテストケースに関して、 $A_2 + A_4 = 6 = A_4$ より、 $A_2$ と $A_4$ のペアを消すことは出来ません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。