UTPC 2022

A - Shuffle and GCD

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

正整数 N に対して、f(N) を以下で定めます。

N の各桁の数字を並び替えて得られる整数の集合を S とする。ただし、並び替えた結果先頭に 0 が続く場合 leading zero として解釈する。例えば、N=102 のとき S=\lbrace 12,21,102,120,201,210\rbrace である。S の要素全てを割り切る最大の整数を f(N) とする。

10^{18} 以下の正整数 K が与えられます。 f(N)=K を満たすような 10^{18} 以下の正整数 N が存在するか判定し、存在する場合 1 つ求めてください。

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

制約

入力は全て整数
1 \leq T \leq 10^4
1 \leq K \leq 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

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

出力

T 行出力せよ。 i\ (1\leq i \leq T) 行目には i 番目のテストケースについて、f(N)=K となる条件を満たす N が存在する場合そのような N を一つ出力し、存在しない場合 -1 を出力せよ。解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

2
3
10

出力例 1

123
-1

1 番目のテストケースについて、N=123 のとき S=\lbrace{123,132,213,231,312,321\rbrace} であり S の全ての要素を割り切る最大の整数は 3 です。したがって f(N)=3 であり、この出力は条件を満たします。

2 番目のテストケースについて、f(N)=10 を満たす 10^{18} 以下の正整数 N が存在しないことが証明できます。

B - Cross Laser Beam

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

2 次元平面上に nok0 君と N 匹のスライムがいます。はじめ nok0 君の座標は (0, 0)、i\ (1\le i\le N) 番目のスライムの座標は (X_i, Y_i) です。 nok0 君は平面上の任意の地点で何度でも以下の行動ができます。

x 軸正負方向、y 軸正負方向の合計 4 方向に同時にビームを打つ。nok0 君と等しい x 座標または y 座標をもつスライムが消滅する。

nok0 君は平面上を任意の方向に連続的に移動することができます。nok0 君が平面上にいるすべてのスライムを消滅させるのに必要な移動距離の最小値を求めてください。

制約

入力は全て整数
1 \le N \le 2000
|X_i|, |Y_i| \le 10^8

入力

入力は以下の形式で標準入力から与えられる。

N  
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

答えを 1 行に出力せよ。真の値との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。

入力例 1

出力例 1

3.605551275463989

nok0 君は次のように移動とビームの発射を行うことができます。

(0, 0) から (1, 1.5) に移動してビームを打つ。1 番目のスライムが消滅する。
(1, 1.5) から (2, 3) に移動してビームを打つ。2 番目と 3 番目のスライムが消滅する。

これが最適な移動の方法で、移動距離の合計は \sqrt{13} = 3.605551275\ldots となります。

入力例 2

1
100000000 -100000000

出力例 2

100000000.000000000000000

入力例 3

18
2092413 29557322
-83061793 -86609930
41750783 34587912
94366440 62086679
42714686 -18841496
10264522 -60895144
94721140 -72749181
-68416594 -56662164
85327102 82520146
-97103434 30343456
54136952 -27352836
-38212546 92787647
-72073444 28721824
32088712 -55984481
-38640098 22126296
84969832 -72730101
-4649799 14505075
92214627 89508662

出力例 3

225535157.051134686276782

C - Nim is Time-consuming

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

UT 君と PC 君は Nim というゲームで遊んでいます。N 個の正整数 A_1, A_2,\ldots, A_N に対し、\mathrm{Nim}(A_1, A_2, \ldots, A_N) とは次のゲームのことを指します。

いくつかの石からなる N 個の山があり、はじめ i\ (1\le i\le N) 番目の山には A_i 個の石がある。UT 君から始めて、2 人は交互に以下の操作を 1 回ずつ繰り返す。

(操作) 石が 1 個以上残っている山を 1 つ選ぶ。その山から石を 1 個以上取り除く。

石が全て取り除かれた時点でゲームを終了し、最後に操作を行ったプレイヤーを勝ち、もう一方のプレイヤーを負けとする。
ゲーム開始時点からゲーム終了時点までに 2 人が行った操作の回数の合計を T としたとき、勝ったプレイヤーが 10^{100}-T 点、負けたプレイヤーが T-10^{100} 点を得る。

1 \le A_i \le M\ (1\le i\le N) を満たす長さ N の整数列 (A_1, A_2, \ldots, A_N) は M^N 通りありますが、その全てに対して、2 人は 1 回ずつ \mathrm{Nim}(A_1, A_2, \ldots, A_N) を遊びます。

それぞれが全てのゲームで獲得する点数の合計を最大化するように行動したとき、これら M^N 回のゲームの操作回数の合計は何回になるでしょうか？答えは非常に大きくなる可能性があるので、998244353 で割った余りを求めてください。

制約

入力は全て整数
1 \le N \le 10^{9}
1 \le M \le 500

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

答えを 1 行に出力せよ。

入力例 1

2 2

出力例 1

2 人は以下の 4 つのゲームを行います。

\mathrm{Nim}(1, 1)
\mathrm{Nim}(1, 2)
\mathrm{Nim}(2, 1)
\mathrm{Nim}(2, 2)

それぞれが最善を尽くした場合、各ゲームの操作回数はそれぞれ 2、3、3、4 になります。これらの合計である 12 を出力します。

入力例 2

4 5

出力例 2

入力例 3

1 222

出力例 3

入力例 4

987654321 456

出力例 4

897555885

答えの値を 998244353 で割った余りを出力してください。

D - Balance

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

N 個のおもりが手元にあります。i 番目のおもりの重さを P_i としたとき、(P_1, \dots, P_N) は (1, \dots, N) の順列となることが分かっていますが、P_i の具体的な値は分かっていません。また、-2N 以上 2N 以下の整数の目盛りがついた棒が、位置 0 のところでつるされています。目盛りがついている位置には穴が開いており、それぞれの穴には 1 個までおもりをぶら下げることができます。はじめはおもりが 1 つもぶら下がっておらず、棒はつりあっています。

zkou くんは最終的に、手元にある N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせたいです。あなたは zkou くんに以下のいずれかの操作をするよう指示できます。

手元にあるおもりを 1 つ選び、おもりがまだぶら下がっていない穴にぶら下げる。
棒にぶら下がっているおもりを 1 つ選び、手元に戻す。

zkou くんは操作を終えるたびに、棒が左右どちらに傾いたか、あるいはつりあったかを、あなたに伝えます。 10000 回以下の指示で、手元にある N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせてください。なお、制約下で常につりあわせる方法が存在することが証明できます。

棒の傾きとつりあいについて

棒に k 個のおもりがのっていて、j 番目のおもりが重さ w_j で位置 x_j にあるとき、棒のモーメント M を M = \sum_{j = 1}^{k} w_j x_j と定義します。M > 0 なら棒が右に傾き、M = 0 なら棒はつりあい、M < 0 なら棒が左に傾きます。

制約

入力は全て整数
1 \leq N \leq 3000

部分点

1 \leq N \leq 100 を満たすデータセットに正解した場合は 30 点が与えられる。

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

最初に、N を標準入力から受け取ってください。

次に、手元にある N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせるまで、zkou くんに操作を指示できます。その際、以下の形式で標準出力に出力してください。

手元にある i 番目のおもりを選び、おもりがまだぶら下がっていない位置 x の穴にぶら下げるとき：

1 i x

ここで、i, x は 1\leq i\leq N, -2N\leq x\leq 2N を満たす整数である必要があります。

棒にぶら下がっている i 番目のおもりを手元に戻すとき：

2 i

ここで、i は 1\leq i\leq N を満たす整数である必要があります。

この指示への返答は以下の形式で標準入力から与えられます。

ここで、S は以下のいずれかの文字列です。

Right：棒は操作後に右に傾いた。
Balanced：棒は操作後につりあった。
Left：棒は操作後に左に傾いた。
-1：不正な出力が行われた。

-1 が入力に与えられた場合、すぐにプログラムを終了してください。出力が不正とみなされる原因の例としては、以下が挙げられます。

出力の形式が異なっていた。
指示回数が上限を超えた。
既に棒にぶら下がっているおもりを棒にぶら下げる指示を出した。
手元にあるおもりを手元に戻す指示を出した。
既におもりがぶら下がっている穴に別のおもりをぶら下げる指示を出した。

N 個のおもりをすべて棒にぶら下げて、なおかつ棒をつりあわせることができたら、以下の形式で 0 を標準出力に出力し、プログラムを終了してください。N 個のおもりがすべて棒にぶら下がっており、なおかつ棒がつりあっている場合、AC となります。

注意点

出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
答えを出力したら（または -1 を受け取ったら）直ちにプログラムを正常終了してください。そうしなかった場合、ジャッジ結果は不定です。
特に、余計な改行や空白の出力も不正なフォーマットの出力とみなされるので注意してください。

入出力例

以下は N = 2 かつ (P_1, P_2) = (2, 1) の場合の入出力例です。

入力	出力	説明
`2`		`N` が与えられます。
	`1 2 -4`	`2` 番目のおもりを位置 `-4` にぶら下げます。
`Left`		棒は左に傾きました。
	`1 1 3`	`1` 番目のおもりを位置 `3` にぶら下げます。
`Right`		棒は右に傾きました。
	`2 1`	`1` 番目のおもりを手元に戻します。
`Left`		棒は左に傾きました。
	`1 1 2`	`1` 番目のおもりを位置 `2` にぶら下げます。
`Balanced`		棒はつりあいました。
	`0`	おもりをすべて棒にぶら下げつつ棒をつりあわせました。`0` を出力してプログラムを終了してください。

E - Parallel Swapping

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ N の順列 P=(P_1,P_2,\ldots,P_N), Q=(Q_1,Q_2,\ldots,Q_N) があります。はじめ P_i = Q_i = i (1 \leq i \leq N) です。この 2 つの順列に対して、以下の操作を 0 回以上好きなだけ繰り返します。

1 \le i \le M を満たす整数 i を選ぶ。P の a_i 番目と b_i 番目の要素を入れ替え、Q の c_i 番目と d_i 番目の要素を入れ替える。

操作後の P, Q の状態の組としてありうるものの個数を 998244353 で割ったあまりを求めてください。

制約

入力は全て整数
2 \leq N \leq 5000
0 \leq M \leq 5000
1 \le a_i, b_i, c_i, d_i \le N
a_i < b_i
c_i < d_i
i \neq j ならば (a_i, b_i, c_i, d_i) \neq (a_j, b_j, c_j, d_j)

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1 c_1 d_1
\vdots
a_M b_M c_M d_M

出力

答えを 1 行に出力せよ。

入力例 1

3 1
1 2 2 3

出力例 1

ありうる P, Q の状態の組は P=(1, 2, 3), Q=(1, 2, 3) と P=(2, 1, 3), Q=(1, 3, 2) の 2 つです。

入力例 2

出力例 2

入力例 3

2 0

出力例 3

F - K inversions

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) と整数 K が与えられます。

以下の疑似コードで表されるアルゴリズムを実行した場合、(1) の式は何回実行されますか？

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N - i - K + 2; j++) {
        if ((P[j], P[j + 1], ..., P[j + K - 1]) が昇順に並んでいない) {
            (P[j], P[j + 1], ..., P[j + K - 1]) を昇順に並び替える ... (1)
        }
    }
}

制約

入力は全て整数
2 \leq K \leq N \leq 2\times 10^5
P は (1,2,\ldots,N) の順列

入力

入力は以下の形式で標準入力から与えられる。

N K
P_1 P_2 \ldots P_N

出力

答えを 1 行に出力せよ。

入力例 1

4 2
1 3 4 2

出力例 1

(i, j) = (1, 1) のとき、(P_1, P_2) = (1, 3) で、(1) 式は実行されません。

(i, j) = (1, 2) のとき、(P_2, P_3) = (3, 4) で、(1) 式は実行されません。

(i, j) = (1, 3) のとき、(P_3, P_4) = (4, 2) で、(1) 式が実行され、(P_3, P_4) = (2, 4)に変化します。

(i, j) = (2, 1) のとき、(P_1, P_2) = (1, 3) で、(1) 式は実行されません。

(i, j) = (2, 2) のとき、(P_2, P_3) = (3, 2) で、(1) 式が実行され、(P_2, P_3) = (2, 3)に変化します。

(i, j) = (3, 1) のとき、(P_1, P_2) = (1, 2) で、(1) 式は実行されません。

全部で (1) 式が 2 回実行されたので、答えは 2 です。

入力例 2

6 3
5 1 6 4 3 2

出力例 2

入力例 3

20 7
10 17 8 1 16 13 14 5 20 19 4 15 18 3 11 2 12 9 7 6

出力例 3

G - K flipping

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

黒板に N 個の整数 A_1, A_2, \ldots, A_N が書かれています。あなたは次の操作を N - 1 回行います。

黒板に書かれている数を 2 つ選んで消す。消した数を x と y として、K - x - y を新たに黒板に書く。

N - 1 回の操作を終えた後、黒板にはただ一つの整数が残りますが、この整数として考えられる最大値はいくつですか？

制約

入力は全て整数
2 \le N \le 2 \times 10^5
1 \le K \le 10^9
1 \le A_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N

出力

答えを 1 行に出力せよ。

入力例 1

4 3
1 2 3 4

出力例 1

例えば以下のような操作をすることで 7 が残ります。

1 と 2 を選んで黒板から消し、3 - 1 - 2 = 0 を黒板に書く
3 と 4 を選んで黒板から消し、3 - 3 - 4 = -4 を黒板に書く
0 と -4 を選んで黒板から消し、3 - 0 - (-4) = 7 を黒板に書く

7 よりも大きい数が最後に残ることはないので、答えは 7 となります。

入力例 2

4 7
1 2 3 4

出力例 2

例えば以下のような操作をすることで 5 が残ります。

1 と 2 を選んで黒板から消し、7 - 1 - 2 = 4 を黒板に書く
4 と 4 を選んで黒板から消し、7 - 4 - 4 = -1 を黒板に書く
3 と -1 を選んで黒板から消し、7 - 3 - (-1) = 5 を黒板に書く

5 よりも大きい数が最後に残ることはないので、答えは 5 となります。

入力例 3

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

出力例 3

H - Digit Slot

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

整数 N が与えられます。あなたは、整数 N に対して以下の操作を 1 回だけ行えます。

操作 : N の桁のうち、いくつかの桁を選び（ 0 個でも良い）、それらを全て独立に 0 ~ 9 のいずれかに等確率で置き換える。ただし、先頭に 0 が続く場合 leading zero として解釈する。

あなたの目的は、出来るだけ高い確率で N の値を操作前よりも大きくすることです。最適な戦略をとった場合に操作前の N よりも大きい数を得られる確率を \text{mod } 998244353 で求めてください。

確率 \text{mod } 998244353 の定義

この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが証明できます。

このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。

制約

N は 1 以上 10^{200000} 未満の整数
N の先頭には余分な 0 は含まれない

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを 1 行に出力せよ。

入力例 1

出力例 1

509104621

この場合、2 桁目と 3 桁目を選ぶのが最適で、 \frac{97}{100} の確率で 502 よりも大きい値を得ることができます。

このとき、100\times 509104621 \equiv 97 \pmod{998244353} が成り立つので、答えとして 509104621 を出力してください。

入力例 2

出力例 2

698771048

この場合、3 桁目を選ぶのが最適で、 \frac{9}{10} の確率で 520 よりも大きい値を得ることができます。

I - Which must be deleted?

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

(, ) のみからなる文字列のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。

空文字列
ある「正しい括弧列」A が存在して (, A, ) をこの順につなげた文字列
ある空でない「正しい括弧列」A,\ B が存在して A,\ B をこの順につなげた文字列

長さ 4N で (, ) のみからなる文字列 S と 2N 個の 2 整数の組 (L_i, R_i)\ (1\leq L_i < R_i \leq 4N) が与えられます。ここで、(L_1,L_2,\dots,L_{2N}) は (1,2,\dots,2N) の、(R_1,R_2,\dots,R_{2N}) は (2N+1,2N+2,\dots,4N) の順列です。

i=1, 2,\dots,2N の順に S の L_i,\ R_i 文字目のいずれかに印をつけた後、印をつけた文字のみを左から順に読み、長さ 2N の文字列として解釈したものを S' とします。

S' を「正しい括弧列」にできるか判定してください。

T 個のテストケースについて答えてください。

制約

入力される数値はすべて整数
1 \leq T \leq 1000
1 \leq N \leq 2000
S は (, ) のみからなる長さ 4N の文字列
1 \leq L_i \leq 2N < R_i \leq 4N
(L_1,L_2,\dots,L_{2N}) は (1,2,\dots,2N) の順列
(R_1,R_2,\dots,R_{2N}) は (2N+1,2N+2,\dots,4N) の順列
1 つの入力に含まれるテストケースについて、 N の総和は 2000 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

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

N
S
L_1 R_1
L_2 R_2
\vdots
L_{2N} R_{2N}

出力

T 行出力せよ。 i\ (1\leq i \leq T) 行目には i 番目のテストケースについて、S' を「正しい括弧列」にできる場合は Yes を、できない場合は No を出力せよ。

入力例 1

3
1
()()
1 3
2 4
2
))()((()
1 6
2 5
3 7
4 8
8
))()))))()())((((()))(()(()))(((
8 26
2 25
1 18
4 22
7 17
12 32
10 31
5 30
15 27
9 23
13 19
11 24
14 29
6 28
16 20
3 21

出力例 1

Yes
No
Yes

1 番目のテストケースについて、 L_1=1 文字目と R_2=4 文字目に印をつけると S' は () となり、これは「正しい括弧列」です。

2 番目のテストケースについて、どのように印をつけても S' は「正しい括弧列」になりません。

J - Divide and Sort

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

(1,2,\ldots,N) の順列 P = (P_1,P_2,\ldots,P_N) が与えられます。あなたは以下の操作を 0 回以上 15 回以下行うことができます。

1\leq l \leq r \leq N かつ r-l+1 が奇数であるような整数組 (l,r) を選び、数列 (P_l,P_{l+1},\ldots,P_r) の中央値を M とする。このとき P_x = M なる整数 x が一意に定まる。P の l 番目から x-1 番目を（存在すれば）昇順に並び替え、x+1 番目から r 番目を（存在すれば）昇順に並び替える。

操作によって P を昇順に並び替えられるか判定し、可能な場合はそのような操作列を一つ求めてください。

中央値とは

長さ 2n - 1 の数列の中央値は、数列を昇順に並び替えたとき、前から n 番目の要素の値として定義されます。例えば、(5, 4,2) の中央値は 4 、(3,1,5,2,4) の中央値は 3 、(9) の中央値は 9 です。

制約

入力は全て整数
1 \leq N \leq 2\times 10^5
P は (1,2,\ldots,N) の順列

部分点

1 \leq N \leq 7 を満たすデータセットに正解した場合は 10 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N
P_1 P_2 \ldots P_N

出力

15 回以下の操作により P を昇順に並び替えられない場合 -1 を出力せよ。

そうでない場合、1 行目に操作を行う回数 k を出力せよ。ここで k は 0 以上 15 以下の整数でなくてはならない。

次に、k 行にわたって操作列を出力せよ。

i\ (2\leq i \leq k +1) 行目には、i-1 回目の操作で選んだ l,r を空白区切りで出力せよ。

解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

5
2 1 3 5 4

出力例 1

1
1 5

l=1,r=5 として操作をします。

数列 (2,1,3,5,4) の中央値は 3 であり、P_x=3 なる x は 3 です。よって P の l=1 番目から x-1=2 番目を昇順に並び替え、 x+1=4 番目から r=5 番目を昇順に並び替えます。

この操作により、 P は (1,2,3,4,5) となり確かに昇順に並び替えられています。

入力例 2

4
1 2 3 4

出力例 2

2
1 3
2 4

15 回以内の操作であれば、操作回数を最小化する必要はありません。

入力例 3

2
2 1

出力例 3

-1

15 回以内の操作で P を昇順に並び替えられない場合、 -1 を出力してください。

K - Grid Coloring

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

2N\times 2M のグリッド状のマス目があります。上から i 行目、左から j 列目のマス目を (i,j) で表します。はじめ、各マスの色はすべて白色です。

これから以下の条件を満たすように NM 個のマス目を赤く塗ります。

赤く塗られたマス目 (i,j) について i+j は偶数である。
赤く塗られたマス目は端点を共有しない。厳密には、赤く塗られた 2 つの異なるマス目 (i,j),(k,l) であって、|i-k|\leq 1 かつ |j-l| \leq 1 を満たすものが存在しない。
K 個のマス目 (X_i,Y_i) は必ず赤く塗る。

条件を満たすように NM 個のマス目を赤く塗る方法の数を 998244353 で割ったあまりを求めてください。

制約

入力は全て整数
1 \leq N,M \leq 3000
0 \leq K \leq \min(NM,10^5)
1\leq X_i \leq 2N, 1 \leq Y_i \leq 2M
(X_i,Y_i) は相異なる
X_i+Y_i は偶数

入力

入力は以下の形式で標準入力から与えられる。

N M K
X_1 Y_1
X_2 Y_2
\vdots
X_K Y_K

出力

答えを 1 行に出力せよ。

入力例 1

2 2 1
3 1

出力例 1

例えばマス目 (1,1),(2,4),(3,1),(4,4) を赤く塗ると条件を満たします（下図左）。

一方、マス目 (1,1),(2,4),(3,1),(3,3) を赤く塗るとマス目 (2,4),(3,3) が端点を共有してしまっているため、条件を満たしません（下図右）。

入力例 2

1 2 2
1 1
2 2

出力例 2

入力例 3

出力例 3

908257345

L - Small RPS Tournament

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 人が参加するじゃんけん大会が開催されます。参加者は、人 1、人 2、\ldots、人 N と呼ばれます。どの参加者もそれぞれ得意な手を持っていて、毎試合得意な手のみを出します。

参加者の得意な手は、R, P, S からなる長さ N の文字列 S によって表されます。人 i の得意な手は、S の i 文字目 S_i です。ここで文字 R はグーを、P はパーを、S はチョキを表します。

大会では、人 1、人 2、\ldots、人 N をこの順に横一列に並べた後、0 回以上の「試合」を行います。「試合」は、次のように行われます。

列で隣り合っている 2 人であって、じゃんけんをしたときにあいこにならないような 2 人を無作為に選び、じゃんけんをさせる。負けたほうの人を列から抜けさせる。

「試合」が行えなくなった時点で、列に残っている人全員の優勝となります。特に、列に残っている人が 1 人だけになった場合、その人の単独優勝となります。

単独優勝する可能性のある人の人数を求めてください。

じゃんけんのルール

じゃんけんの結果は、2 人の出した手に応じて次のように決まります。

一方がグーで他方がチョキのとき、グーを出した人が勝ち、チョキを出した人は負け
一方がチョキで他方がパーのとき、チョキを出した人が勝ち、パーを出した人は負け
一方がパーで他方がグーのとき、パーを出した人が勝ち、グーを出した人は負け
両者が同じ手を出したとき、あいこ（引き分け）

制約

N は整数
2 \leq N \leq 3 \times 10^5
S は R, P, S からなる長さ N の文字列

部分点

この問題には複数の部分点が設定されている。

2 \leq N \leq 50 を満たすデータセットに正解した場合は 10 点が与えられる。
2 \leq N \leq 3000 を満たすデータセットに正解した場合は 50 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを 1 行に出力せよ。

入力例 1

4
RSPR

出力例 1

たとえば次のような手順で大会が行われると、人 3 が単独優勝します。

人 1 と人 2 がじゃんけんをして、人 1 が勝つ。
人 1 と人 3 がじゃんけんをして、人 3 が勝つ。
人 3 と人 4 がじゃんけんをして、人 3 が勝つ。

ほかにも、人 1 は単独優勝する可能性があります。一方、人 2 と人 4 は単独優勝する可能性がありません。

入力例 2

3
RSR

出力例 2

必ず 2 人以上が残ってしまいます。

入力例 3

6
SRPPSR

出力例 3

M - Minimize XOR by Redistribution

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ n の非負整数列 X=(X_1,X_2,\dots,X_n) に対し f(X) を、Y_1+Y_2+\dots+Y_n=X_1+X_2+\dots+X_n を満たす長さ n の非負整数列 Y=(Y_1,Y_2,\dots,Y_n) 全てにおける Y_1 \oplus Y_2 \oplus \dots \oplus Y_n の最小値とします。ただしここで、\oplus はビット単位 \mathrm{XOR} 演算を表します。

長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。 A の空でない部分列 B は 2^N-1 個考えられますが、それらすべてに対する f(B) の総和を 998244353 で割ったあまりを求めてください。

ビット単位 \mathrm{XOR} 演算とは

非負整数 A, B のビット単位 \mathrm{XOR}、A \oplus B は、以下のように定義されます。

A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

入力は全て整数
1 \leq N \leq 2000
0 \leq A_i < 2^{20}

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを 1 行に出力せよ。

入力例 1

3
0 1 2

出力例 1

A の空でない部分列 B は B=(0),(1),(2),(0,1),(0,2),(1,2),(0,1,2) の 7 個存在します。

例えば B=(0,2) のとき、1+1=0+2,\ 1 \oplus 1 = 0 であるため f(B)=0 です。

上記の 7 個の A の部分列に対する f(B) は順に 0,1,2,1,0,3,1 となるため、答えは 0+1+2+1+0+3+1=8 となります。

入力例 2

15
99412 355422 750910 993699 41414 435678 325371 637849 939332 512546 112254 175315 865362 459658 311661

出力例 2

N - 01 String Game

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

整数 N と、0 と 1 のみからなる長さ N の文字列 T が与えられます。 0 と 1 のみからなる、長さ 2N の文字列 S = s_1 s_2 \ldots s_{2N} と T を用いて、Alice と Bob がゲームをします。二人は Alice から始めて、S の全ての文字に印がつくまで交互に以下の操作をします。

1 \le i \le 2N を満たす整数 i であって、s_i にまだ印がついていないようなものを選ぶ。その後、
- Alice の手番であれば、その桁に o の印をつける。
- Bob の手番であれば、その桁に x の印をつける。

ゲームが終了した時に、o の印がついている桁だけを左から読み、N 文字の文字列として解釈したものが、辞書順で T 以上であれば Alice の勝利、そうでなければ Bob の勝利です。

開始時に用いる文字列 S として考えられるものは 2^{2N} 通りあります。このうち、両者がそれぞれ自身が勝つために最適な戦略をとる場合に、 Alice が勝つようなものの個数を 998244353 で割ったあまりを求めてください。

制約

N は整数
1 \le N\le 2 \times 10^5
T は 0, 1 のみからなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
T

出力

答えを 1 行に出力せよ。

入力例 1

1
0

出力例 1

0 または 1 からなる長さ 2 の全ての文字列が該当します。

入力例 2

1
1

出力例 2

01, 10, 11 の 3 つが該当します。

入力例 3

12
011011000111

出力例 3

13225655

O - Move to Rest

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

頂点 1 を根とする、N 頂点の根付き木があります。頂点 i (2 \le i \le N) の親は P_i です。頂点 1 には椅子が 10^{100} 個置いてあり、それ以外の頂点には椅子が 1 個ずつ置いてあります。それぞれの椅子には、人が 1 人まで座ることができます。

これから M 人の人たちが順番にこの木に休憩しに訪れます。i = 1, 2, \dots, M の順に、i 番目の人は以下の行動をとります。

頂点 A_i に訪れる。その後、空いている椅子がある頂点にたどり着くまで根の方向に向かって進む。空いている椅子がある頂点にたどり着いたら、その椅子に座り行動を終了する。

全員が行動を終了するまでに i 番目の人が通る辺の本数を d_i としたときに、d_1 + d_2 + \dots + d_M の値を求めてください。

制約

入力は全て整数
1 \le N, M \le 10^6
1 \le P_i < i
1 \le A_i \le N

入力

入力は以下の形式で標準入力から与えられる。

N
P_2 \ldots P_N
M
A_1 \ldots A_M

出力

答えを 1 行に出力せよ。

入力例 1

出力例 1

1 番目の人は頂点 1 から訪れて、そのまま頂点 1 の椅子に座ります。 2, 3 番目の人はそれぞれ頂点 2, 3 の椅子に座ります。 4 番目の人は頂点 2 を訪れますが、頂点 2 の椅子には既に 2 番目の人が座っているので頂点 1 に移動します。頂点 1 の椅子は余っているので、その椅子に座り行動を終了します。

d_1 = d_2 = d_3 = 0, d_4 = 1 なので、出力すべき値は 1 です。

入力例 2

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