問題一覧 > 通常問題

No.2518 Adjacent Larger

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 : ShirotsumeShirotsume / テスター : MasKoaTSMasKoaTS fky_fky_
1 ProblemId : 10062 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-25 16:29:16

問題文

正整数 $N$ と、長さ $N$ の非負整数列 $A = (A_1, \dots, A_N)$ が与えられます。

$(1, \dots, N)$ を並べ替えてできる長さ $N$ の順列 $P$ であって、以下の条件を満たすものが存在するか判定してください。

  • $1 \leq i \leq N$ を満たす任意の整数 $i$ について、以下が成り立つ。
    • $P_{i - 1}, P_{i + 1}$ のうち、$P_i$ より大きい要素の個数は $A_i$ 個

ただし、$P_0$ は $P_N$ を、$P_{N + 1}$ は $P_1$ をそれぞれ指すものとします。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 入力はすべて整数
  • $1 \leq T \leq 10^4$
  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \leq 2$
  • 1 つの入力ファイルにおいて、$N$ の総和は $2 \times 10^5$ 以下

    • 入力

    入力は標準入力から与えられる。1 行目にテストケースの個数 $T$ が与えられる。

    $T$

    次に、各テストケースが以下の形式で与えられる。

    $N$
$A_1$ $\dots$ $A_N$

    出力

    それぞれのテストケースについて、条件を満たす順列 $P$ が存在するなら Yes、存在しないなら No を出力せよ。

    サンプル

    サンプル1
    入力
    3
4
2 0 1 1
4 
2 2 0 0
7
1 1 1 1 1 1 1
    出力
    Yes
No
No

    3 つのテストケースが与えられています。

    1 つめのテストケースについて、例えば $P = (1, 4, 3, 2)$ としたときに問題文の条件を満たします。これは次のように確かめられます：

    • $P_0 = 2, P_2 = 4$ のうち $P_1 = 1$ より大きい要素の個数は $2$ 個
    • $P_1 = 1, P_3 = 3$ のうち $P_2 = 4$ より大きい要素の個数は $0$ 個
    • $P_2 = 4, P_4 = 2$ のうち $P_3 = 3$ より大きい要素の個数は $1$ 個
    • $P_3 = 3, P_5 = 1$ のうち $P_4 = 2$ より大きい要素の個数は $1$ 個

    条件を満たす $P$ が存在するため、答えは Yes となります。

    2 つめと 3 つめのテストケースについて、条件に合う $P$ は存在しません。よって、答えは No となります。

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