問題文

長さ N の正整数列 A が与えられます。 A の中に含まれる要素のうち、 A に含まれる個数が 10 個以下であるものが存在するか判定してください。

制約

• 1 \leq N \leq 2\times 10^5
• 1 \le A_i \le 100
• 入力は全て整数

入力例 1

6
10 20 10 20 30 30

出力例 1

Yes

例えば 10 は、A に含まれる要素であり、かつ含まれる個数は 10 個以下です。

入力例 2

55
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5

出力例 2

No

問題文

内部を含む円 C の円周上に、点 1, 2, \cdots , N がこの順に等間隔に並んでいます。

C を点 a,b を通る直線、点 c,d を通る直線の 2 本で同時に切断したとき、 C はいくつの部分に分割されますか？

制約

• 3 \leq N \leq 100
• 1 \leq a,b,c,d \leq N
• a \neq b
• c \neq d
• (a,b) \neq (c,d)
• (a,b) \neq (d,c)
• 入力は全て整数

入力例 1

4
1 3
2 4

出力例 1

4

図のように、円 C は 4 つの部分に分割されます。ただし図の {\rm p}1 \ldots 4 は、点 1 \ldots 4 を指します。

入力例 2

100
41 31
59 65

出力例 2

3

円 C は 3 つの部分に分割されます。

入力例 3

5
1 3
5 3

出力例 3

3

2 つの点が同じ位置にある場合もあることに注意してください。

問題文

長さ N の整数列 A が与えられます。あなたは以下の操作を 0 回以上任意の回数行えます。

• 相異なる整数 1 \le i,j,k \le N を選ぶ。 A_k を A_i + A_j に置き換える。

10^{100} \le A_1 とすることが可能か判定してください。

制約

• 3 \leq N \leq 2 \times 10^5
• |A_i| \le 10^9
• 入力は全て整数

入力例 1

3
1 2 3

出力例 1

Yes

例えば、 (i,j,k)=(2,3,1) として 1 回操作すると A=(5,2,3) となります。(14:53 修正)

適切に操作を行うと、条件を達成することができます。

入力例 2

3
-1 -2 -3

出力例 2

No

入力例 3

4
3 1 4 -15

出力例 3

Yes

問題文

xy 平面上に点 P(X_1, Y_1) があります。あなたは P に対して以下の操作を 0 回以上任意の回数行えます。

• \lvert a \rvert \le K を満たす実数 a を選び、 P の現在の座標を (x, y) として、 P を (x+a, y-a) または (x+a, y+a) に動かす。

P を点 (X_2, Y_2) に移動させるために必要な操作回数の最小値を求めてください。

制約

• 1 \leq K \leq 10^9
• -10^9 \leq X_1, Y_1, X_2, Y_2 \leq 10^9
• 入力は全て整数

入力例 1

1
0 0
3 2

出力例 1

4

移動の一例として、 (0, 0) \to (1, 1) \to (1.8, 1.8) \to (2.3, 1.3) \to (3, 2) が考えられます。

また、 3 回以下の操作で P を (3, 2) に動かすことはできないため、 4 を出力します。

入力例 2

3
141 592
653 589

出力例 2

171

問題文

N 頂点 M 辺の連結無向グラフが与えられます。 i\ (1 \le i \le M) について、 i 番目の辺は頂点 A_i と頂点 B_i をつなぐ辺です。

全ての辺をちょうど K 回ずつ通るウォークが存在するか判定してください。

制約

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min(\frac{N(N-1)}{2} , 2\times 10^5)
• 1 \le K \le 10^9
• 1 \le A_i < B_i \le N
• 1 \le i < j \le M について、 (A_i,B_i) \neq (A_j,B_j)
• 与えられるグラフは連結
• 入力は全て整数

入力例 1

3 3 3
1 2
2 3
1 3

出力例 1

Yes

1 → 2 → 3 → 1 → 2 → 3 → 1 → 2 → 3 → 1 のウォークが条件を満たします。

入力例 2

4 3 3
1 2
2 3
2 4

出力例 2

No

問題文

長さ N の非負整数列 a=(a_1,a_2,\dots ,a_N) であって、以下の条件を満たすものが存在するか判定し、存在するならば一つ構築してください。

• 0 \le a_i \le 10^9\ (1 \le i \le N)
• a_i \neq a_j\ (1 \le i < j \le N)
• 任意の a の連続とは限らない空でない部分列について、その部分列の中央値がその部分列の平均値以下である。

なお、数列 x に対する中央値は、数列 x の要素を昇順に並べた列を y=(y_1,y_2,\ldots,y_n) とするとき、 y_{\lfloor (n+1)/2 \rfloor} で定義されます。

制約

• 1 \leq N \leq 2 \times 10^5
• 入力は全て整数

入力例 1

3

出力例 1

Yes
2024 3 26

問題文

長さ N の整数列 A が与えられます。

頂点 u と頂点 v を結ぶ辺の重みが A_u\times A_v である完全グラフ G の最小全域木の重みを求めてください。

制約

• 2 \leq N \leq 2\times 10^5
• |A_i| \le 10^6
• 入力は全て整数

入力例 1

3
1 2 3

出力例 1

5

頂点 1 と頂点 2 を結ぶ辺の重みは 1\times 2=2 、

頂点 1 と頂点 3 を結ぶ辺の重みは 1\times 3=3 、

頂点 2 と頂点 3 を結ぶ辺の重みは 2\times 3=6 です。

よって 1 と 2 を結ぶ辺、 1 と 3 を結ぶ辺で全域木を作るのが最小で、この木の重みは 5 になります。

入力例 2

4
1 1 -1 -1

出力例 2

-3

問題文

パ研王国には N 個の村と M 本の道路があります。 i\ (1 \le i \le M) 本目の道路は村 A_i, B_i を双方向に結んでいて、どの状態であっても渡るのに 1 分かかります。

最初、すべての道路に氷が張ってあります。 C_i = -1 の場合は氷はとけず、 1 \le C_i の場合、 C_i 分後に氷がとけます。

国王であるパケン君は最初村 1 にいて、道路を何本か通ることで村 N まで移動したいです。パケン君は任意の村で待機することもできます。また、パケン君は用心深いため、氷の張ってある道をなるべく通りたくないです。氷の張ってある道を通る時間を最小化して街 N に移動するとき、かかる時間の最小値を求めてください。

制約

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min(\frac{N(N-1)}{2} , 2\times 10^5)
• 1 \le A_i < B_i \le N
• 1 \le i < j \le N について、 (A_i,B_i)\neq (A_j,B_j)
• C_i=-1 または 1 \le C_i \le 10^9
• 入力は全て整数
• 村 1 から村 N まで道路を何本か使い到達できる

入力例 1

3 3
1 3 -1
1 2 3
2 3 1

出力例 1

5

村 1 から直接村 3 に行くと、かかる時間は 1 分ですが氷の道を必ず通ることとなります 。 しかし、村 2 を経由することで氷の道を通らず村 3 に行くことができます。この場合パケン君は村 1 で 3 分待機する必要があります。

入力例 2

4 5
1 2 1
2 4 -1
1 3 -1
3 4 3
2 3 3

出力例 2

5

問題文

正整数 K と長さ N の正整数列 A が与えらえます。あなたはこの数列に対して以下の操作を 5\times 10^5 回以下行えます。

• 整数 i\ (1 \le i \le N-1) を選ぶ。 A_i と A_{i+1} を swap したのち、 A_{i+1} に K を加算する。

最終的な数列が昇順、すなわち A_1 \le A_2 \le \ldots \le A_N となっているような操作列を一つ見つけてください。なお、この制約下においてこのような操作列が存在することが示せます。

制約

• 1 \leq N \leq 1000
• 1 \le K \le 10^9
• 1 \le A_i \le 10^9
• 入力は全て整数

入力例 1

4 1
1 3 1 2

出力例 1

2
2
3

iを2,3の順に選んで2回操作を行うことでA=(1,1,2,5)を得ることができます。

入力例 2

8 2
3 1 4 1 5 9 2 6

出力例 2

15
1
2
3
4
5
6
7
2
3
5
6
4
5
3
4

問題文

整数列 p に対して、以下の操作の結果できる数列 q を f(p) と定義します。

• 空の数列 q を用意する。

• i=1,2,\ldots,|p| の順に、現在 q に p_i が存在しなければ、 q の末尾に p_i を挿入する。

正整数 N,K が与えられます。以下の条件を満たす長さ N の正整数列 a の個数を 998244353 で割った余りを求めてください。

• 1 \le a_i \le K\ (1 \le i \le N)
• f(a) = f(\mathrm{rev}(a)) が成り立つ。ただし、 \mathrm{rev}(a) = (a_N,a_{N-1},\ldots,a_1) である。

制約

• 1 \leq N,K \leq 2000
• 入力は全て整数

入力例 1

3 2

出力例 1

4

条件を満たす a は (1,1,1),(1,2,1),(2,1,2),(2,2,2) の 4 通りです。

入力例 2

10 26

出力例 2

413643776

問題文

正整数 M と、長さ N の非負整数列 A=(A_1,A_2,\dots ,A_N) が与えられます。ここで、0 \leq A_i \leq 2^M-1 が保証されます。また、最初 X=0 である整数 X があります。

あなたは、 A の要素を自由に並べ替えた後、以下の操作を i=1,2,\ldots,N の順で行います。

• X \ \mathrm{or} \ A_i \neq 2^M-1 ならば、 X を X \ \mathrm{or} \ A_i に置き換える。

操作後の X としてありうるものの個数を求めてください。

制約

• 1 \leq N \leq 2\times 10^5
• 1 \le M \le 30
• 0 \le A_i < 2^M
• 入力は全て整数

入力例 1

3 3
4 3 6

出力例 1

2

操作後の X として考えられるものは、3,6 の 2 通りです。

例えば 、A=(4,3,6) の場合、操作は以下のようにして行われます。

• X \ \mathrm{or} \ A_1 = 0 \ \mathrm{or} \ 4 = 4 ≠ 2^3-1 なので、X を 4 で置き換える。
• X \ \mathrm{or} \ A_2 = 4 \ \mathrm{or} \ 3 = 7 = 2^3-1 なので、操作を行わない。
• X \ \mathrm{or} \ A_3= 4 \ \mathrm{or} \ 6 = 6 ≠ 2^3-1 なので、X を 6 で置き換える。

よって、最終的な X の値は 6 となります。

入力例 2

5 1
1 1 1 1 1

出力例 2

1

入力例 3

8 4
3 5 14 0 10 3 6 12

出力例 3

4

問題文

長さ N の整数列 A が与えられます。以下の条件を満たす (0,1,\ldots,N-1) の順列 P を考えます。

• 1 \le i \le N について、 A_i \neq -1 ならば、 A_i = P_i

そのような順列 P についての以下の値として考えられる最小の値を求めてください。

• \displaystyle \sum_{i=1}^N \sum_{j=i}^N \mathrm{mex}(P_i,P_{i+1},\ldots,P_j)

ただし、 \mathrm{mex}(x_1,x_2,\ldots,x_n) は、 x の中に含まれない最小の非負整数を表します。

制約

• 1 \leq N \leq 2\times 10^5
• 1 \le i \le N について、 A_i = -1 または 0 \le A_i < N
• 1 \le i < j \le N について、 A_i, A_j \neq -1 ならば A_i \neq A_j
• 入力は全て整数

入力例 1

3
0 2 1

出力例 1

5

\mathrm{mex}(0)+\mathrm{mex}(0,2)+\mathrm{mex}(0,2,1)+\mathrm{mex}(2)+\mathrm{mex}(2,1)+\mathrm{mex}(1)=1+1+3+0+0+0=5 です。

入力例 2

3
0 -1 -1

出力例 2

5

問題文

正整数 N が与えられます。長さ N の (1,2,\ldots,N) の順列 p について、以下の値を最大化する p を 1 つ求めてください。

• (p_1 + 1) \oplus (p_2 + 2) \oplus \ldots \oplus (p_N + N)

ただし \oplus はビット単位 \mathrm{XOR} 演算を表します。

制約

• 1 \leq N \leq 2\times 10^5
• 入力は全て整数

入力例 1

3

出力例 1

2 1 3

(2+1) \oplus (1+2) \oplus (3+3) = 6 です。値を 6 より大きくすることができないので、これを出力します。

入力例 2

1

出力例 2

1

入力例 3

5

出力例 3

2 3 4 5 1

問題文

縦 H cm、横 W cm の長方形のチョコレートがあります。

• チョコのいずれかの辺に平行な直線でチョコを (それぞれが正の面積になるように) 切断し、片方を食べる。 ただし、残されたチョコの辺の長さは全て正整数であり、かつ面積が K \mathrm{cm}^2 以上でなければならない。

Alice が先手で、操作ができなくなったほうが負けです。勝つのはどちらでしょうか。

Q 個のテストケースに対して答えてください。

制約

• 1 \le Q \le 2\times 10^5
• 1 \leq H,W \leq 10^9
• 1 \le K \le H\times W
• 入力は全て整数

入力例 1

3
3 4 3
2 2 3
1000 800 3000

出力例 1

Alice
Bob
Alice

1 つ目のケースについて、例えば次のような進行が考えられます。

• Alice が縦 3 cm、横 3 cm となるようチョコレートを切断し、残りを食べる。残ったチョコレートの面積は 9 \mathrm{cm}^2 である。
• Bob が縦 2 cm、横 3 cm となるようチョコレートを切断し、残りを食べる。残ったチョコレートの面積は 6 \mathrm{cm}^2 である。
• Alice が縦 1 cm、横 3 cm となるようチョコレートを切断し、残りを食べる。残ったチョコレートの面積は 3 \mathrm{cm}^2 である。
• Bob はどのように切断しても残りのチョコレートの面積を 3 \mathrm{cm}^2 以上にすることはできないため、Alice の勝ちとなる。

問題文

N 頂点の根付き木が与えられます。頂点には 1, 2, \ldots, N の番号が付いており、木の根は頂点 1 です。 i (1 \le i \le N-1) 番目の辺は頂点 A_i と頂点 B_i をつないでいます。また、各頂点 i には文字 C_i (1 \le i \le N) が書き込まれています。 C_i は ( か ) のいずれかです。

以下の 3 種類のクエリが Q 個与えられるので、順に処理してください。 j 個目のクエリは以下の通りです。

• T_j=1 のとき : 頂点 X_j に書かれている文字を Y_j に変更する
• T_j=2 のとき : 頂点 S_j を根とする部分木の各頂点について、書かれている文字が ( ならば ) に、 ) ならば ( に変更する
• T_j=3 のとき : 頂点 U_j から頂点 V_j へのパス上の頂点(両端含む)に書かれた文字を順に並べた文字列の(連続とは限らない)部分列のうち、正規括弧列であるものの長さの最大値を出力する。特に、空文字列は常に部分列かつ正規括弧列なので、最大値が必ず存在します。

制約

• 1 \leq N, Q\leq 2\times 10^5
• 1 \le A_i < B_i \le N (1 \leq i \leq N-1)
• C_i=( または C_i=) (1 \leq i \leq N)
• 1 \leq T_j \leq 3 (1 \leq j \leq Q)
• T_j=1 のとき、 1 \le X_j \le N かつ Y_j=( または Y_j=) (1 \leq j \leq Q)
• T_j=2 のとき、 1 \le S_j \le N (1 \leq j \leq Q)
• T_j=3 のとき、 1 \le U_j, V_j \le N (1 \leq j \leq Q)
• 入力は全て、整数か ( か ) のいずれか

入力例 1

5
1 2
2 3
2 4
4 5
( ( ) ) )
4
3 1 5
3 3 4
2 2
3 5 1

出力例 1

4
2
2

木は以下のようになっています。

それぞれのクエリは次のように処理されます。

1. パス上の頂点は (1, 2, 4, 5) であり、頂点に書かれた文字を連結すると (()) になります。これは正規括弧列なので、長さ 4 を出力します。
2. パス上の頂点は (3, 2, 4) であり、頂点に書かれた文字を連結すると )() になります。この部分列で最長の正規括弧列は () なので、長さ 2 を出力します。
3. 頂点 2 の部分木の頂点 2, 3, 4, 5 に書かれた文字が変更され、頂点 1, 2, 3, 4, 5 に書かれた文字はそれぞれ (, ), (, (, ( になります。
4. パス上の頂点は (5, 4, 2, 1) であり、頂点に書かれた文字を連結すると (()( になります。この部分列で最長の正規括弧列は () なので、長さ 2 を出力します。

入力例 2

1
(
3
3 1 1
1 1 )
3 1 1

出力例 2

0
0

入力例 3

10
5 6
2 3
2 5
7 8
4 9
2 7
8 10
2 4
1 7
( ) ) ( ) ) ) ) ( (
20
2 2
1 5 )
3 4 9
2 5
3 8 5
3 8 8
2 8
3 9 9
3 7 5
1 1 )
3 4 8
2 9
2 9
2 2
1 5 (
1 6 (
3 2 9
1 2 )
1 5 )
3 4 5

出力例 3

0
0
0
0
0
2
0
2

問題文

長さ N の整数列 A,B が与えられます。

頂点 u と頂点 v を結ぶ辺の重みが A_u\times A_v + B_u \times B_v である完全グラフ G の最小全域木の重みを求めてください。

制約

• 2 \leq N \leq 5\times 10^4
• |A_i|, |B_i| \le 10^6
• 入力は全て整数

入力例 1

3
1 3 -1
-2 0 -4

出力例 1

0

頂点 1 と頂点 2 を結ぶ辺の重みは 1 \times 3 + (-2) \times 0 = 3 、

頂点 1 と頂点 3 を結ぶ辺の重みは 1 \times (-1) + (-2) \times (-4) = 7 、

頂点 2 と頂点 3 を結ぶ辺の重みは 3 \times (-1) + 0 \times (-4) = -3 です。

よって 1 と 2 を結ぶ辺と 2 と 3 を結ぶ辺で全域木を作るのが最小で、この木の重みは 0 になります。

入力例 2

4
1 1 -1 -1
1 1 -1 -1

出力例 2

-6

(A_i, B_i) = (A_j, B_j) となる i, j (i \neq j) が存在することもあります。

入力例 3

10
-593389 -914534 -534565 -257272 -723595 763395 -272810 -869922 449729 -111959
743146 -30912 -528945 903153 -162840 -807868 227877 -433864 751438 34288

出力例 3

-5395522482698