問題文

整数 N と、長さ N の整数列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) が与えられます。

AliceとBobはそれぞれ N 枚のカードを持っています。

Aliceの持っているカードのうち、i 番目のカードには A_i が書かれています。

Bobの持っているカードのうち、i 番目のカードには B_i が書かれています。

AliceもBobも、お互いの持っているカードの内訳を知っています。

これから、N ラウンドのカードゲームを行います。はじめ、Alice、Bobともに得点は 0 です。各ラウンドでは、以下のことが起こります。

• AliceとBobが同時にカードを出す。Aliceが出したカードに書かれている整数を a 、Bobが出したカードに書かれている整数を b とする。a,b の値に応じて、得点が以下のように変動する。
  • a\ne b のとき、より大きい整数が書かれたカードを出したほうが |a-b| の得点を得る。
  • a=b のとき、両者とも得点を得ない。
• その後、出されたカード計 2 枚を審判が食べる。

N ラウンド終了した際、得点が大きいほうが勝ちます。ただし、両者の得点が同じ場合は引き分けとします。

両者が最適に行動したとき、引き分けになるか、引き分けにならないならばどちらが勝つか判定してください。

制約

• 1 \leq N\leq 2\times 10^5
• -10^9\leq A_i\leq 10^9 (1\leq i\leq N)
• -10^9\leq B_i\leq 10^9 (1\leq i\leq N)
• 入力はすべて整数

入力例 1

4
2 0 2 5
0 4 0 1

出力例 1

Alice

例えば、ゲームは以下のように進行します。

• Aliceが 2 の書かれたカードを、Bobが 0 の書かれたカードを出す。Aliceが |2-0|=2 の得点を得る。
• Aliceが 2 の書かれたカードを、Bobが 4 の書かれたカードを出す。Bobが |2-4|=2 の得点を得る。
• Aliceが 0 の書かれたカードを、Bobが 0 の書かれたカードを出す。両者とも得点を得ない。
• Aliceが 5 の書かれたカードを、Bobが 1 の書かれたカードを出す。Aliceが |5-1|=4 の得点を得る。

最終的なAliceの得点は 6 、Bobの得点は 2 で、Aliceの勝ちです。

これは両者が最適に行動しているとは限りませんが、両者が最適に行動してもAliceが勝つことが示せます。

入力例 2

1
3
3

出力例 2

Draw

明らかに引き分けです。

問題文

長さ n の数列 a と正整数 k に対して、以下の条件が成り立つとき、 a を k-連続な数列と定義します。

• すべての i\ (1 \le i \le n) に対して、ある正整数対 (l,r) が存在し、 l\le i < r かつ k \le r-l かつ a_l=a_{l+1}=\ldots=a_{r-1} が成り立つ。

例えば、 a=(1,1,1,2,2,2,2,3,3,3) は 3-連続です。特に、 a=() ならば任意の正整数 t に対して t-連続なことに注意してください。

正整数 N,K と長さ N の正整数列 C,W が与えられます。あなたは、以下の操作を 0 回以上任意の回数行えます。

• 整数 i を選ぶ。コスト W_i を払い、 C_i,W_i をそれぞれ C,W から削除する。

C を K-連続にするために必要なコストの総和の最小値を求めてください。

制約

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

部分点

• N \leq 300 を満たすデータセットに正解した場合は、10 点与えられる。
• N \leq 3000 を満たすデータセットに正解した場合は、上記とは別に 10 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 80 点与えられる。

入力例 1

4 2
1 1 2 1
1 2 3 4

出力例 1

3

入力例 2

2 1
1 2
10 10

出力例 2

0

入力例 3

10 2
3 1 4 1 5 9 2 6 5 3
58 97 93 23 84 62 64 33 83 27

出力例 3

337

問題文

整数 M,K が与えられます。 以下の条件をすべて満たす長さ N の正整数列 a=(a_1,a_2,\dots,a_N) のうち、N が最大になるようなものを 1 つ出力してください。

• 1 \leq a_i \leq M (1\leq i\leq N)
• i \neq j のとき、a_i \neq a_j (1 \leq i,j \leq N)
• a からどのように K 個以上 N 個以下の要素を選んでも、それらの最大公約数は 1 になる

制約

• 1 \leq M \leq 2 \times 10^{5}
• 2 \leq K \leq 5
• 入力は全て整数

部分点

• K=2,3,4,5 を満たすデータセットに正解した場合、それぞれ 10,20,30,40 点が与えられる。

入力例 1

11 5

出力例 1

10
1 2 3 4 5 7 8 9 10 11 

a = (1,2,3,4,5,7,8,9,10,11) は、条件を満たします。また、条件を満たす長さ 11 以上の整数列 a は存在しないため、最大の長さは 10 です。

問題文

整数 S,T が与えられます。以下の条件をすべて満たす整数列の組 (a,b) が存在するか判定し、存在するならば一つ構築してください。

• a の長さを n とし、 b の長さを m としたとき、 1 \le n,m \le 100

• a,b の要素の絶対値は 10^8 を超えない

• \displaystyle \sum_{i=1}^{n} a_i = S かつ \displaystyle \sum_{i=1}^{m} b_i = T

• \displaystyle \sum_{i=1}^{n} a_i^2 = \sum_{i=1}^{m} b_i^2

制約

• -10^8 \leq S, T \leq 10^8
• 入力は全て整数

部分点

• -100 \leq S, T \leq 100 を満たすデータセットに正解した場合は、10 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 90 点与えられる。

入力例 1

5 7

出力例 1

Yes
1
5
2
3 4

入力例 2

0 0

出力例 2

Yes
1
0
1
0

問題文

遊園地「パ研ランド」には、N 個の地点があり、i 番目の地点の高度は H_i です。また、園内には M 本のジェットコースター用レールが敷かれており、i 番目のレールは地点 U_i と V_i を双方向に結んでいます。

あなたは、これらのレールのいくつかを使って、以下の条件を満たすジェットコースターの経路を構築しようと考えています。

• 通る地点の順序を v_0, v_1, \dots, v_n とすると、v_0 = v_n が成り立つ。
• すべての i (1 \leq i \leq n) について、v_{i-1} と v_i を直接結ぶレールが存在する。

また、ジェットコースターの 楽しさ を以下の式で定義します。

\[ \frac{1}{n} \sum_{i=1}^{n} \max(0, H_{v_{i-1}} - H_{v_i}) \]

楽しさの最大値を求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_{i} \lt V_{i} \leq N (1 \leq i \leq M)
• i \neq j ならば、 (U_{i}, V_{i}) \neq (U_{j}, V_{j})
• 入力は全て整数

入力例 1

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

出力例 1

1.5

例えば、 4, 3, 2, 1, 4 の順番で通るジェットコースターは問題文中の条件を満たします。その楽しさは、

• H_4 - H_3 = 1
• H_3 - H_2 = 1
• H_2 - H_1 = 1
• H_1 - H_4 = -3

であることから、 (\max(0, 1) + \max(0, 1) + \max(0, 1) + \max(0, -3)) を 4 で割った値、すなわち 0.75 になります。
楽しさが最大となるように経路を構築すれば、その値は 1.5 になります。

入力例 2

4 2 
1 1 2 3 
1 2 
3 4 

出力例 2

0.5 

遊園地の地点の組であって、レールのみでは接続されていないようなものが存在する可能性もあります。

問題文

二次元平面上に R 個の赤い点、G 個の緑の点、B 個の青い点があります。

i 番目の赤い点は (RX_i,RY_i) にあります。

i 番目の緑の点は (GX_i,GY_i) にあります。

i 番目の青い点は (BX_i,BY_i) にあります。

複数の点が同じ座標にある可能性もあります。

関数 \text{dist},\text{tri} を以下のように定義します。

• \text{dist}((x_1,y_1),(x_2,y_2))=|x_1-x_2|+|y_1-y_2|
• \text{tri}(r,g,b)=\text{dist}((RX_r,RY_r),(GX_g,GY_g))+\text{dist}((GX_g,GY_g),(BX_b,BY_b))+\text{dist}((BX_b,BY_b),(RX_r,RY_r))

Q 個のクエリを処理してください。i 番目のクエリでは整数の組 (x_i,y_i,z_i) が与えられるので、以下の値を求めてください。

• 以下の条件をすべて満たす整数の組 (s,t,u) についての \text{tri}(s,t,u) の最大値
  • x_i=-1 なら 1\leq s\leq R 、x_i\neq -1 なら s=x_i
  • y_i=-1 なら 1\leq t\leq G 、y_i\neq -1 なら t=y_i
  • z_i=-1 なら 1\leq u\leq B 、z_i\neq -1 なら u=z_i

制約

• 1\leq R,G,B
• R+G+B\leq 200000
• 0\leq RX_i,RY_i,GX_i,GY_i,BX_i,BY_i\leq 10^9
• 1\leq Q\leq 200000
• 1\leq x_i\leq R または x_i=-1
• 1\leq y_i\leq G または y_i=-1
• 1\leq z_i\leq B または z_i=-1
• 入力はすべて整数

入力例 1

4 2 2
2 0
2 5
0 4
0 1
1 3
0 0
1 7
0 0
7
1 2 2
1 -1 2
3 -1 -1
-1 -1 -1
-1 2 -1
-1 2 2
4 2 2

出力例 1

4
10
16
18
18
14
2

• 2 番目のクエリについて、\text{tri}(1,1,2) が最大です。
• 3 番目のクエリについて、\text{tri}(3,2,1) が最大です。
• 4 番目のクエリについて、\text{tri}(2,2,1) が最大です。
• 5 番目のクエリについて、\text{tri}(2,2,1) が最大です。

問題文

( または ) のみからなる文字列 S が与えられます。以下の問題を解いてください。

• 0 で初期化された変数 x と、長さ 0 の数列 h がある。以下の操作を 0 回以上好きな回数行う。
  • h に x を追加する。その後、以下のどちらかを行う。
    • x を x+1 で置き換える。
    • S の x+1 文字目から y 文字目までを取り出した文字列が正規括弧列であるような y を好きに選び、x を y で置き換える。この操作は x\leq |S|-1 のときのみ行うことができる。
• 操作を終了したときに x=|S| となっているとき、最終的な h としてありうるものの個数を 998244353 で割ったあまりを求めよ。

制約

• S は ( または ) のみからなる長さ 1 以上 200000 以下の文字列

入力例 1

(()())

出力例 1

6

最終的な h としてありうるものは以下の 6 通りです。

• (0)
• (0,1,5)
• (0,1,3,5)
• (0,1,3,4,5)
• (0,1,2,3,5)
• (0,1,2,3,4,5)

問題文

N 枚の整数が書かれたカードがあります。i 枚目のカードには A_i が書かれています。

Alice と Bob はこの N 枚のカードでゲームをします。最初、すべてのカードは山にあります。Alice を先手として、交互に山からカードがなくなるまで以下の操作を繰り返します。

• 山にあるカードを 1 枚選び、そのカードを山から取り出して自分の手札にする

最終的に、自分の手札の全てのカードに書かれた整数の排他的論理和をスコアとします。スコアが大きい方の人が勝ちです。スコアが同じ時は引き分けとします。

両者が最適に行動したとき、引き分けになるか、引き分けにならないならばどちらが勝つか判定してください。

Q 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq N \leq 2 \times 10^{5} (1 \leq i \leq N)
• 0 \leq A_i \leq 10^{18} (1 \leq i \leq N)
• N の総和は 2 \times 10^{5} 以下
• 入力は全て整数

入力例 1

3
1
1
2
100 100
3
20090926 20250401 33550336

出力例 1

Alice
Draw
Bob

1 個目のテストケースについては、以下のような操作が考えられます。

Alice が 1 のカードを自分の手札にします。Alice のスコアが 1 で、Bob のスコアが 0 となり、Alice の勝ちです。

2 個目のテストケースについては、以下のような操作が考えられます。

Alice が 100 のカードを自分の手札にします。次に、Bob が 100 のカードを自分の手札にします。Alice のスコアが 100 で、Bob のスコアが 100 となり、引き分けになります。

問題文

T 個のテストケースについて、以下の問題に答えてください。

長さ N の正整数列 A が与えられます。長さ N-1 の整数列 S=(S_1,S_2,\dots,S_{N-1}),T=(T_1,T_2,\dots,T_{N-1}) であって、以下の条件を満たすものが存在するか判定してください。

• 以下の条件を満たす正整数列 B は B=A のみである。
  • 任意の整数 i (1 \leq i \leq N-1) について、B_{S_i} と B_{T_i} の積は A_{S_i}A_{T_i} である。

制約

• 1 \leq T \leq 5
• 2 \leq N \leq 18
• 1 \leq A_i \leq 10^9
• 入力は全て整数

入力例 1

4
3
1 2 3
5
13 16 27 25 23
6
13 1 12 10 8 10
4
7 6 9 3

出力例 1

Yes
Yes
Yes
No

問題文

正整数 N が与えられます。

総和が N であるような正整数列 s について、スコア を s の総積と定義します。

スコアのとりうる最大値を m とします。スコアが m になるような s の個数を 998244353 で割ったあまりを求めてください。

制約

• 1 \leq N\leq 10^9
• N は整数

部分点

• N \leq 30 を満たすデータセットに正解した場合は、10 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 90 点与えられる。

入力例 1

4

出力例 1

2

s としてありうるものは 8 個存在し、それぞれスコアは以下のようになります。

• s=(1,1,1,1)：スコアは 1
• s=(1,1,2)：スコアは 2
• s=(1,2,1)：スコアは 2
• s=(2,1,1)：スコアは 2
• s=(1,3)：スコアは 3
• s=(2,2)：スコアは 4
• s=(3,1)：スコアは 3
• s=(4)：スコアは 4

スコアのとりうる最大値は 4 で、スコアが 4 となる s は 2 個存在します。よって、答えは 2 です。

入力例 2

2

出力例 2

1

入力例 3

1000000000

出力例 3

428670605

s の個数を 998244353 で割ったあまりを求めることを忘れないでください。

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) と 0,1 からなる長さ N-1 の数列 C が与えられます。

ここで、与えられる順列 P は以下の条件を満たすことが保証されます。

• 整数 i\ (1 \le i \le N-1) について、 i が奇数ならば P_i < P_{i+1} を、 i が偶数ならば P_i > P_{i+1} を満たす。

あなたは、最初すべての要素が -1 である長さ N-1 の数列 b を用意して、以下の二種類の操作を任意の順番で 300000 回以下任意の回数行うことができます。

• type 1 : 整数 i\ (1 \le i \le N-1) を選ぶ。 P_i と P_{i+1} を swap する。
• type 2 : 整数 i\ (1 \le i \le N-1) を選ぶ。 P_i < P_{i+1} ならば b_i = 0, P_i > P_{i+1} ならば b_i=1 と置き換える。

b=C とすることが可能か判定し、可能ならば操作方法を一つ示してください。

制約

• 2 \leq N \leq 2 \times 10^{5}
• P は (1,2,\ldots, N) の順列
• 整数 i\ (1 \le i \le N-1) について、 i が奇数ならば P_i < P_{i+1} 、 i が偶数ならば P_i > P_{i+1}
• C_i \in \lbrace 0,1 \rbrace \ (1 \le i \le N-1)
• 入力は全て整数

入力例 1

4
3 4 1 2
0 0 0

出力例 1

4
2 1
2 3
1 2
2 2

問題文

正整数 N 及び素数 P が与えられます。\displaystyle\prod_{k=1}^N k^k を P で割った余りを求めてください。

制約

• 1 \leq N \leq 10^8
• 2 \leq P \leq 10^9+9
• P は素数
• 入力は全て整数

入力例 1

3 998244353

出力例 1

108

\displaystyle\prod_{k=1}^3 k^k=1 \times 4 \times 27=108 なので、998244353 で割った余りは 108 です。

入力例 2

1 1000000007

出力例 2

1

入力例 3

100 998244353

出力例 3

598189773

問題文

整数 N,K,X と長さ N の正整数列 R=(R_1,R_2,\dots,R_N) が与えられます。

パ研合宿には、N 人の参加者がいます。参加者には 1,2,\dots,N と番号がつけられていて、参加者 i のレーティングは R_i です。

パ研合宿のコンテストでは、属する参加者のレーティングの総和が X 以下であるようなチームを組むことができます。

i=1,2,\dots,N について、次の条件をすべて満たすチームを組むことが可能か判定してください。

• 参加者 i が属する。
• K 人以上の参加者が属する。

ただし、条件を満たすチームを組むことが可能であったとしても実際にチームが組まれることはありません。

制約

• 2\leq K\leq N\leq 2\times 10^5
• 1\leq X\leq 10^9
• 1\leq R_i\leq 4229 (1\leq i\leq N)
• 入力はすべて整数

部分点

• K=N=2 を満たすデータセットに正解した場合は、1 点が与えられる。
• K=2 を満たすデータセットに正解した場合は、上記とは別に 9 点が与えられる。
• 追加の制約のないデータセットに正解した場合は、上記とは別に 90 点が与えられる。

入力例 1

3 2 6
3 3 4

出力例 1

Yes
Yes
No

K 人以上の参加者が属するチームとしてありうるものは、参加者 1 と参加者 2 からなるチームのみです。

入力例 2

2 2 41
20 25

出力例 2

No
No

入力例 3

10 3 3733
3332 4124 151 292 1044 1373 2626 2599 3405 2933

出力例 3

No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

問題文

頂点に 1 から N の番号が振られた N 頂点 M 辺の単純無向グラフ G が与えられます。i 番目の辺は頂点 A_i と頂点 B_i を結びます。G の各頂点に 1 から N までの整数を 1 つずつ割り振る方法は N! 通りありますが、それらのうち以下の値が最小となるものについて、その値を求めてください。

• G 上のパスであって、パス上の頂点に割り当てられた整数を順に並べたものが単調増加になるもののうち、最大の頂点数

制約

• 1 \leq T \leq 5
• 1 \leq N \leq 20
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
• A_i \neq B_i (1 \leq i \leq M)
• \{ A_i,B_i \} \neq \{ A_j,B_j \} (i \neq j)
• 与えられるグラフは単純
• 入力は全て整数

入力例 1

2
5 7
1 2
1 3
1 5
2 4
3 4
3 5
4 5
20 0

出力例 1

3
1

問題文

整数 N,K が与えられます。

以下の条件をすべて満たす長さ N の正整数列 a=(a_1,a_2,\dots,a_N) を出力してください。

• 1\leq a_i\leq 10^9 (1\leq i\leq N)
• a からどのように 1 個以上 K 個未満の要素を選んでも、それらの最大公約数は 1 より大きくなる
• a からどのように K 個以上 N 個以下の要素を選んでも、それらの最大公約数は 1 になる

ただし、本問題の制約下で条件を満たす a が存在することは証明できます。

制約

• 2\leq K\leq N\leq 5
• 入力はすべて整数

部分点

• N=2,3,4,5 を満たすデータセットに正解した場合、それぞれ 1,4,10,85 点が与えられる。