問題文

技術室奥プログラミングコンテストの伝統は残り続け、西暦 2021 年以降、西暦 10000 年まで毎年 8 月に技術室奥プログラミングコンテストが開催されるとします。

このとき、西暦 N 年に開催される技術室奥プログラミングコンテストは第何回であるか出力してください。

ただし、 N < 2021 かつ西暦 N 年に技術室奥プログラミングコンテストが開催されないことが現時点(このコンテストの開催時点)で分かっている場合、 -1 と出力してください。

制約

• 1 \leq N \leq 10000
• 入力は全て整数

入力例 1

2021

出力例 1

6

今年の技術室奥プログラミングコンテストは第 6 回です。

入力例 2

1

出力例 2

-1

西暦 1 年には技術室奥プログラミングコンテストは開催されていません。

入力例 3

2015

出力例 3

1

入力例 4

5947

出力例 4

3932

原案: Cyanmond

問題文

パ研には N 人の部員がいます。それぞれの部員には 0 以上 2 \times 10^5 以下の整数で表される色がついており、i 番目の部員の色は A_i です。

カラフルなものが大好きな魔法少女の oliverx3 は、以下の呪文を唱えることができます:

• 部員を 1 人選び、その部員の色を 0 \leq x \leq 2 \times 10^5 を満たす整数 x に変える。ここで、呪文を唱える前と後では選ばれた部員の色は異なっている必要がある。

oliverx3 は今からちょうど M 回呪文を唱えます。

M 回の呪文を唱え終わったあとの、最終的な N 人の色の種類数として考えられる最大値を求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq A_i \leq 2\times 10^5\ (1 \leq i \leq N)
• 入力は全て整数

入力例 1

6 2
1 1 1 2 4 4

出力例 1

5

たとえば、以下のように呪文を唱えることで 6 人の色の種類数を 5 にできます。

• 3 番目の部員の色を 1 から 3 に変える。
• 5 番目の部員の色を 4 から 10^5 に変える。

6 人の色の種類数を 5 より大きくすることはできないので、5 を出力します。

入力例 2

7 0
0 1 2 3 4 5 6

出力例 2

7

oliverx3 は呪文を一度も唱えることができませんが、パ研はもともとカラフルだったようです。

原案: oliverx3

問題文

パ研では、その優れた技術力によって新型握力計が開発されています。この新型は、なんとグラム単位で握力を測ることが可能です！

さて、かめ君は新型握力計のテストを任されました。かめ君は 2N-1 人のパ研部員を呼びつけ、握力を測りました。

i 人目の部員の計測結果は A_i によって以下のように表されます。

• A_i \neq -1 であるとき、i 人目の部員の握力は A_i グラムである。
• A_i = -1 であるとき、i 人目の部員の握力は機器の不備によって不明である。

ただし、1 人目の計測の前にかめ君は機器をチェックをしたので A_1 \neq -1 であることは保証されています。

ところで、1 人目の部員である Cyanmond 君は平凡が大好きです。彼は目立ちたくないので、A を書き換えることで書類上のパ研の握力の中央値を自分の握力に近づけようと思っています。

具体的には、次のように書き換えます。

• A_i = -1 である計測結果それぞれを好きな正整数に書き換える。ここで、A_i = -1 である計測結果は必ず書き換える必要がある。

Cyanmond 君が適切に計測結果を書き換えることで、書類上のパ研部員の握力の中央値を彼の握力と等しくできるならば Yes を、そうでなければ No を出力してください。

制約

• 1 \leq N \leq 10^5
• A_i = -1 または 1 \leq A_i \leq 10^9
• A_1 \neq -1
• 入力は全て整数

入力例 1

3
20000 25000 -1 -1 18000

出力例 1

Yes

例えば、次のような書き換え方があります。

• 3 人目の部員の握力を 20000 グラム、4 人目の部員の握力を 21000 グラムに書き換える

このように書き換えると、書類上のパ研部員の握力の中央値は Cyanmond 君の握力と等しくなります。

入力例 2

3
1 30000 30000 30000 30000

出力例 2

No

書類を書き換えることはできず、書類上のパ研部員の握力の中央値は Cyanmond 君の握力と等しくありません。

入力例 3

1
25000

出力例 3

Yes

そもそも Cyanmond 君しか握力を測っていません。

原案: Cyanmond

問題文

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

1 \le l \le r \le N を満たすすべての整数対 (l, r) について \displaystyle \left | \sum_{k=l}^{r} A_k \right | を求め、それらの和を 998244353 で割った余りを出力してください。

制約

• 1 \le N \le 2 \times 10^5
• |A_i| \le 10^9 \ (1 \le i \le N)
• 入力は全て整数

入力例 1

3
1 -2 3

出力例 1

10

|1| + |1 + (-2)| + |1 + (-2) + 3| + |(-2)| + |(-2) + 3| + |3| = 1 + 1 + 2 + 2 + 1 + 3 = 10 です。

入力例 2

2
-1 1

出力例 2

2

入力例 3

4
314159265 358979323 846264338 327950288

出力例 3

815701001

998244353 で割った余りを出力することをお忘れなく。

原案: Chippppp

問題文

長さ N の整数列 A=A_1,A_2,\dots,A_N が与えられます。また、整数組 (i, j)\ (1 \leq i < j \leq N) に対して「スコア」を以下のように定義します。

• スコア：A_i + A_j - ((A_i\mathbin{\mathrm{AND}}A_j)\mathbin{\mathrm{XOR}}(A_i\mathbin{\mathrm{OR}}A_j))

ここで a\mathbin{\mathrm{AND}}b は a と b のビットごとの論理積、a\mathbin{\mathrm{XOR}}b は a と b のビットごとの排他的論理和、a\mathbin{\mathrm{OR}}b は a と b のビットごとの論理和をそれぞれ表します。

1 \leq i < j \leq N を満たす全ての整数組 (i, j) についてスコアを求め、その最大値を出力してください。

制約

• 2 \leq N \leq 3\times10^5
• 0 \leq A_i < 2^{31}\ (1 \leq i \leq N)
• 入力は全て整数

入力例 1

3
4 7 3

出力例 1

8

(1,2) のスコアは A_1+A_2-((A_1\mathbin{\mathrm{AND}}A_2)\mathbin{\mathrm{XOR}}(A_1\mathbin{\mathrm{OR}}A_2))=4+7-(4\mathbin{\mathrm{XOR}}7)=4+7-3=8 で、これが最大です。

入力例 2

5
8 17 20 31 3

出力例 2

40

原案: Ebishu0309

問題文

N 個のマスが左右一列に並んでいます。左から i 番目のマスをマス i と呼ぶことにします。はじめ、すべてのマスは白く塗られています。

カエルは現在マス 1 におり、以下の行動を繰り返してマス N までたどり着こうとしています。

• カエルがいるマスを i として、マス i+1, i+2, \ldots, i+K のいずれかにジャンプする。ただし、存在しないマスや黒く塗られているマスには移動できない。

さて、これを聞いたいたずらっ子のオタマジャクシは、マス 1, N を除くいくつかのマスを黒く塗ることにしました。

黒く塗るマスの選び方として考えられるものは 2^{N-2} 通りありますが、そのすべてについてカエルがマス N にたどり着く移動方法の数を求め、その総和を 998244353 で割ったあまりを出力してください。

制約

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

入力例 1

4 2

出力例 1

5

オタマジャクシは、マス 2, 3 のうちのいくつかのマスを黒く塗ります。

• マス 2 が白色でマス 3 も白色の場合、カエルには 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, 1 \rightarrow 2 \rightarrow 4, 1 \rightarrow 3 \rightarrow 4 の 3 通りの移動方法があります。
• マス 2 が白色でマス 3 が黒色の場合、カエルには 1 \rightarrow 2 \rightarrow 4 の 1 通りの移動方法があります。
• マス 2 が黒色でマス 3 が白色の場合、カエルには 1 \rightarrow 3 \rightarrow 4 の 1 通りの移動方法があります。
• マス 2 が黒色でマス 3 も黒色の場合、カエルはマス 4 にたどり着けません。

答えは 3 + 1 + 1 + 0 = 5 です。

入力例 2

6 1

出力例 2

1

カエルは 1 マスずつしか進めないので、一つでもオタマジャクシに黒く塗られたマスがあるとマス N にたどり着けません。

入力例 3

64 26

出力例 3

677439847

998244353 で割ったあまりを出力することに注意してください。

原案: NatsubiSogan

問題文

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

A, B の最長共通部分列 (LCS) の長さを求めてください。

なお、この問題においては以下のことが保証されます。

• 任意の整数 x について、A_i=x なる i は高々 2 つしか存在しない。

制約

• 1 \leq N,M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9\ (1 \leq i \leq M)
• 任意の整数 x について、A_i=x なる i は高々 2 つまでしか存在しない
• 入力は全て整数

入力例 1

3 3
1 2 2
2 1 2

出力例 1

2

(1,2), 或いは (2,2) が A と B の最長共通部分列です。

入力例 2

2 3
1 3
2 4 6

出力例 2

0

このように、A と B の最長共通部分列が空になる場合もあります。

入力例 3

6 5
3 1 5 3 1 4
10 4 9 10 2

出力例 3

1

原案: penguinman

問題文

ここに N 個の箱があり、i 個目の箱には A_i 個のビー玉が入っています。

Cyanmond 君は、箱に入っているビー玉の数をなるべく均等にするために次の行動をします。

• まず X 個の箱を選ぶ。選んだ全ての箱に B 個のビー玉を追加する。
• その後 Y 個の箱を選ぶ。選んだ全ての箱に C 個のビー玉を追加する。

この行動を終えた後、箱に入っているビー玉の個数の最大値を D、最小値を E とします。適切に箱を選んだ時の D - E として考えられる最小値を求めてください。

制約

• 2 \leq N \leq 2.5 \times 10^5
• 0 \leq X,Y \leq N
• 1 \leq A_{i},B,C \leq 10^{18}
• 入力は全て整数

入力例 1

5 1 2
7 3
17 7 13 16 18

出力例 1

2

例えば、次のような入れ方が考えられます。

• 2 個目の箱に 7 個のビー玉を追加した後、2 個目の箱と 3 個目の箱に 3 個のビー玉を追加する。

この場合、最終的なビー玉の個数の最大値は 18、最小値は 16 となり、D-E は 2 です。

D-E を 2 より小さくする選び方は存在しないので、2 を出力します。

入力例 2

3 2 2
50 100
10 10 15

出力例 2

95

原案: Cyanmond

問題文

正整数 N が与えられます。 0 \le k < N を満たす整数 k のうち、 k^2 \equiv 1 \pmod N を満たすものの個数を求めてください。

1 つの入力につき T 個のケースが与えられるので、それぞれについて答えを求めてください。

制約

• 入力は全て整数
• 1 \le T \le 1000
• 2 \le N \le 10^9

入力例 1

3
3
14
1592

出力例 1

2
2
8

1^2 \equiv 1 \pmod 3, 2^2 \equiv 1 \pmod 3 です。

原案 : turtle0123__

問題文

縦 N+1 マス、横 N+1 マスのグリッドがあります。左上のマスを (0,0) 、 (0,0) から下に i マス、右に j マス進んだマスを (i,j) とします。

マス (i,j)\ (0 \leq i,j \leq N) には A_{i,j} 個のクッキーが置かれています。

以下の操作を 2 回行います。

• (0,0) から (N,N) までの最短経路を選び、経路上のマスにあるクッキーをすべて食べる。

ここで、 (0,0) から (N,N) までの最短経路とは、 (0,0) から縦または横に隣り合うマスに移動することを繰り返して (N,N) に到達する経路のうち、通るマスの個数が最小となるものをいいます。

各操作後、選ばれた経路上のマスにあるクッキーの個数は 0 個になります。

食べることのできるクッキーの個数の最大値を求めてください。

制約

• 1 \leq N \leq 200
• 0 \leq A_{i,j} \leq 10^5\ (0 \leq i,j \leq N)
• A_{0,0} = A_{N,N} = 0
• 入力は全て整数

入力例 1

2
0 1 1
1 2 1
1 1 0

出力例 1

7

次のような操作で、 7 個のクッキーを食べることができます。

入力例 2

9
0 25273 26794 66830 40997 84165 45980 5843 80656 61575
87941 16379 8963 54856 64123 92048 30508 13499 63597 47707
23578 11427 93616 82855 28147 98207 67964 93434 32977 63765
51357 17333 43635 41603 984 97559 50230 50827 8012 67522
18345 2692 3452 69676 20584 88882 29554 11120 45476 1931
86655 70278 16349 93974 65638 22263 52541 55849 87916 18224
77866 70308 34053 17087 11677 84733 22083 66162 98308 2293
23288 68456 52353 44462 22185 20880 73802 87851 50133 56588
69248 59757 31414 72695 79497 30822 15037 76133 21699 45443
32105 6492 8375 65971 7857 72820 86156 24248 92835 0

出力例 2

2151343

原案 : anmichi

問題文

Noboru 君はダイヤルキーを買いました。このダイヤルキーは 1 から N までの番号が振られた N 個のダイヤルからなり、各ダイヤルには 0 以上 9 以下の数字が設定されます。現在、全てのダイヤルの数字は 0 で初期化されています。

このダイヤルキーのパスワードは長さ N の数列 A で表され、 1 \leq i \leq N を満たす全ての i についてダイヤル i の数字が A_i に一致した時に限り、ダイヤルキーは開きます。

Noboru 君の目標は、以下の操作を 0 回以上繰り返してダイヤルキーを開いた状態にすることです。

操作 : 1 \leq l \leq r \leq N を満たす整数 l, r を選び、以下のどちらかを行う。

• ダイヤル l,l+1,\ldots,r の数字にそれぞれ 1 を足す。ただし、操作前の数字が 9 である場合は 1 を足す代わりにそれを 0 で置き換える。

• ダイヤル l,l+1,\ldots,r の数字からそれぞれ 1 を引く。ただし、操作前の数字が 0 である場合は 1 を引く代わりにそれを 9 で置き換える。

彼はできるだけ少ない操作回数で目標を達成したいです。操作回数の最小値を求めてください。

制約

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 9 (1 \leq i \leq N)
• 入力は全て整数

入力例 1

3
2 1 9

出力例 1

3

例えば、次のような操作手順が考えられます。

1. l=1, r=1 とし、それぞれのダイヤルの数字に 1 を足す。ダイヤルの数字は 1,0,0 となる。

2. l=1, r=2 とし、それぞれのダイヤルの数字に 1 を足す。ダイヤルの数字は 2,1,0 となる。

3. l=3, r=3 とし、それぞれのダイヤルの数字から 1 を引く。ダイヤルの数字は 2,1,9 となる。

2 回以下の操作でダイヤルキーを開いた状態にすることはできないため、 3 を出力します。

入力例 2

6
3 1 4 1 5 9

出力例 2

11

入力例 3

1
0

出力例 3

0

ダイヤルキーは既に開いているため、Noboru 君は一度も操作を行う必要がありません。

原案: Noboru2020

問題文

縦 2 マス、横 NM マスからなる長方形の形をしたマス目があります。

このマス目を 2N 個の「M マスでできた多角形」によって隙間なく、かつ重複なく敷き詰めることを考えます。ここで、ある M マスの集合はそれに含まれるマス目全体が連結であるとき、またその時に限り「M マスでできた多角形」と呼ばれるものとします。

回転や反転を行うことで初めて一致するような敷き詰め方は区別するものとして、敷き詰め方の総数を 998244353 で割った余りを求めてください。

制約

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

入力例 1

2 3

出力例 1

11

例えば、次のような敷き詰め方があります。

入力例 2

3 4

出力例 2

169

入力例 3

100 150

出力例 3

944278885

998244353 で割った余りを出力することに注意してください。

原案: cpcznksutbeoa

問題文

N 頂点の根付き木があります。頂点には 1, 2, \ldots, N の番号がつけられています。この木の根は頂点 1 であり、頂点 i (2 \leq i \leq N) の親は頂点 P_i です。また、頂点 i には数 A_i が書かれています。

M 個の駒があります。駒には 1, 2, \ldots, M の番号がつけられています。駒 i は現時点では頂点 V_i に置かれています。

あなたは、次の操作を 0 回以上の任意の回数行えます。

• 二つの駒 p と q を選ぶ。駒 p が置かれている頂点を u とし、駒 q が置かれている頂点を v とする。駒 p を、頂点 u と v の最近共通祖先に移動させる。

全ての操作を終えた後に駒 i が置かれている頂点を t_i とします。このときのスコアは \sum_{i=1}^{M} A_{t_i} で定められます。スコアの最大値を求めてください。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 2 \leq M \leq 2 \times 10^5
• 1 \leq V_i \leq N (1 \leq i \leq M)
• 入力は全て整数

入力例 1

5
1 1 3 3
6 2 9 1 7
3
2 4 5

出力例 1

24

次のように操作するのが最善です。

1. 駒 p として駒 1 を選び、駒 q として駒 2 を選ぶ。駒 1 が頂点 2 から頂点 1 に移動する。
2. 駒 p として駒 2 を選び、駒 q として駒 3 を選ぶ。駒 2 が頂点 4 から頂点 3 に移動する。
3. 駒 p として駒 3 を選び、駒 q として駒 2 を選ぶ。駒 3 が頂点 5 から頂点 3 に移動する。

最終的に \lbrace t_i \rbrace = (1, 3, 3) となるので、スコアは 6 + 9 + 9 = 24 です。

入力例 2

3
1 1
1 100 100
4
2 3 3 2

出力例 2

400

一度も操作しないのが最善です。二つ以上の駒が同じ頂点に置かれていることもあることに注意してください。

入力例 3

6
1 2 2 3 4
1 5 6 2 8 8
8
4 1 5 6 2 3 1 3

出力例 3

40

原案: Forested

問題文

左右一列に N 個のマスが並べられており、左から順に 1,2,\ldots,N と番号が振られています。これからこれらのマスの上を aspi くんが移動します。

aspi くんははじめマス 1 におり、以下の行動を繰り返します。

• 現在いるマスの番号を i とする。以下の条件をすべて満たす非負整数の組 (a,b) を 1 つ選び、a \times K+b マス右に進む。このとき、コスト C_i がかかる。
  • 0 \leq a \leq A_i
  • 0 \leq b \leq B_i
  • a \times K + b \leq N-i

aspi くんはマス N まで移動したいです。移動が可能かを判定し、可能なら必要な合計コストの最小値を求めてください。

制約

• 1 \leq K \lt N \leq 2 \times 10^5
• 0 \leq A_i \leq N (1 \leq i \leq N-1)
• 0 \leq B_i \lt K (1 \leq i \leq N-1)
• 1 \leq C_i \leq 10^9 (2 \leq i \leq N-1)
• 入力は全て整数

入力例 1

5 2
1 1 3
1 0 2
0 1 3
5 1 1

出力例 1

4

例えば以下のように移動するとよいです。

• マス 1 から、(a,b)=(1,1) としてマス 4 に移動する。このとき、コスト C_1=3 がかかる。
• マス 2 から、(a,b)=(0,1) としてマス 5 に移動する。このとき、コストは C_4=1 かかる。

上記の移動方法における合計コストは 4 であり、これより合計コストの小さくなる移動方法は存在しないため答えは 4 です。

入力例 2

3 2
0 0 6
1 1 3

出力例 2

-1

aspi くんはマス N まで移動することができません。A_i と B_i が共に 0 になる場合があることに注意してください。

入力例 3

10 4
5 3 892311419
3 1 517634394
9 2 78211774
5 2 247254316
3 3 238811568
3 0 654514160
2 0 680020633
7 2 683514900
9 2 540304649

出力例 3

892311419

この場合、マス 1 からマス 10 に一回の行動で移動するのが最善です。

原案: aspi

問題文

ペンギンくんはこれから N 個の仕事をしなければなりません。i\ (1 \leq i \leq N) 個目の仕事は、明日を 1 日目として L_i 日目から R_i 日目までの R_i-L_i+1 日間からちょうど 1 日を選び、その日を丸一日使って行う必要があります。丸一日使うとある通り、彼は 1 日に複数の仕事をこなすことはできません。

ペンギンくんが i 個目の仕事を D_i 日目に行うとき、彼の かなしさ は以下のように定義されます。

• S=(D_1,D_2,\ldots,D_N) を昇順に並び替えた数列を S' として、\max_{1 \leq i \lt N} (S'_{i+1}-S'_i)

ペンギンくんのかなしさを最小化してください。ただし、そもそもペンギンくんが N 個の仕事全てを行うことができない場合、-1 を出力してください。

制約

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

入力例 1

3
1 3
2 3
3 5

出力例 1

1

例えば、

• 1 個目の仕事を 3 日目に
• 2 個目の仕事を 2 日目に
• 3 個目の仕事を 4 日目に

行うことで、ペンギンくんのかなしさは 1 になります。ペンギンくんは 1 日に複数の仕事を行えないため、これが最小値となります。

入力例 2

3
1 1
2 2
1 2

出力例 2

-1

ペンギンくんは N 個の仕事全てをこなすことができません。

入力例 3

8
157966192 957651261
451709097 715397956
273397483 342666952
165622095 585411299
749846702 972016434
8431836 421375441
459940001 999343267
7784836 829109033

出力例 3

58168536

原案: penguinman

問題文

N 個の頂点 1,2,\ldots,N からなる木があります。i 本目の辺は頂点 A_i と頂点 B_i を結び、C_i = B のとき青色、C_i = R のとき赤色で塗られています。

FirstBlue 君と SecondRed 君がこの木を使ってゲームをします。FirstBlue 君から始めて、2 人は交互に手番をプレイします。それぞれの手番では、以下の操作を行います:

• FirstBlue 君の手番: まだ残っている青色の辺を 1 つ選び、その辺を木から取り除く。
• SecondRed 君の手番: まだ残っている赤色の辺を 1 つ選び、その辺を木から取り除く。

それぞれの手番で木は 2 つに分断されますが、そのうち頂点 1 を含まない方の木は取り除かれます。

先に操作を行えなくなった方が負けです。2 人が最適に行動するとき、どちらが勝つか求めてください。

1 つの入力ファイルにつき、T 個のテストケースを解いてください。

制約

• 1 \leq T \leq 3000
• 1 \leq N \leq 40
• 1 \leq A_i, B_i \leq N
• C_i は B または R
• T, N, A_i, B_i は整数
• 与えられるグラフは木

入力例 1

3
3
1 2 B
2 3 R
6
1 2 B
2 3 R
1 4 B
4 5 R
1 6 R
5
1 2 B
2 3 R
1 4 R
4 5 B

出力例 1

First
Second
Second

1 個目のゲームでは、FirstBlue 君が頂点 1, 2 を結ぶ辺を選んで操作を行うと、頂点 1 のみを含む木になります。このとき、赤色の辺が残っていないため、SecondRed 君は操作を行うことができません。よって FirstBlue 君が勝ちます。
2, 3 個目のゲームでは、FirstBlue 君がどのように行動しても、SecondRed 君が適切に行動することで、必ず SecondRed 君が勝ちます。

原案: oliverx3