第二回全国統一プログラミング王決定戦本戦

A - Count Triplets

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋君は A_1, A_2, \cdots, A_N の N 要素からなる整数列 A を持っています。

A_i < A_j > A_k を満たす (i, j, k) (1 \leq i < j < k \leq N) の組の個数を求めてください。

制約

3 \leq N \leq 5000
0 \leq A_i \leq 10^9
入力は全て整数である

入力

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

N
A_1 A_2 \cdots A_N

出力

A_i < A_j > A_k を満たす (i, j, k) (1 \leq i < j < k \leq N) の組の個数を出力せよ。

入力例 1

4
1 2 3 2

出力例 1

条件を満たす組は (i, j, k) = (1, 3, 4), (2, 3, 4) の 2 つがあります。

入力例 2

3
2 2 2

出力例 2

A_i < A_j > A_k を満たす (i, j, k) の組はありません。

入力例 3

10
0 7 7 6 9 8 1 3 2 0

出力例 3

B - NIKKEI String

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は S を NIKKEI 型に分割する方法が何通りあるか気になっています。 S を 6 つの空でない連続する文字列に分割する方法であって、次の条件を満たすものの個数を求めてください。

S を分割してできた文字列を前から順に S_1, S_2, S_3, S_4, S_5, S_6 としたとき、S_2 と S_6 が等しく、かつ S_3 と S_4 が等しい。

制約

6 \leq |S| \leq 500
S は英小文字から成る

入力

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

出力

S を NIKKEI 型に分割する方法の個数を出力せよ。

入力例 1

nikkei

出力例 1

条件を満たす分割は、S_1 = n , S_2 = S_6 = i , S_3 = S_4 = k , S_5 = e のみです。

入力例 2

aabbccccddbb

出力例 2

NIKKEI 型に分割する方法は、

S_1 = aa , S_2 = bb , S_3 = cc , S_4 = cc , S_5 = dd , S_6 = bb
S_1 = aab , S_2 = b , S_3 = cc , S_4 = cc , S_5 = ddb , S_6 = b
S_1 = aa , S_2 = bb , S_3 = c , S_4 = c , S_5 = ccdd , S_6 = bb
S_1 = aab , S_2 = b , S_3 = c , S_4 = c , S_5 = ccddb , S_6 = b

の 4 通りあります。

入力例 3

aaaaaaaaaaaaaaa

出力例 3

C - Largest N

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

H 行 W 列のマス目があり、それぞれのマスは黒または白で塗られています。上から i 行目、左から j 列目のマスをマス (i, j) と呼びます。

マス (a_i, b_i) (1 \leq i \leq K) は白で塗られており、それ以外の H \times W - K マスは黒で塗られています。

1 以上の整数 k に対してマス目がサイズ k の N を含むとは、次の条件をみたす整数 i, j が存在することを言います。

マス (i + t, j) (0 \leq t < k) がすべて黒
マス (i + t, j + t) (0 \leq t < k) がすべて黒
マス (i + t, j + k - 1) (0 \leq t < k) がすべて黒

ただし、この条件に関わる全てのマスが H 行 W 列のマス目に含まれなければなりません。

このマス目に含まれる N のサイズの最大値を求めてください。ただし、どのサイズの N も含まない場合は、0 を出力してください。

制約

1 \leq H, W \leq 3000
0 \leq K \leq \mathrm{min}(H \times W, 2 \times 10^5)
1 \leq a_i \leq H
1 \leq b_i \leq W
(a_i, b_i) \neq (a_j, b_j) (i \neq j)
入力は全て整数である

入力

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

H W K
a_1 b_1
a_2 b_2
:
a_K b_K

出力

マス目に含まれる N のサイズの最大値を出力せよ。

入力例 1

3 4 2
1 3
3 3

出力例 1

マス目は以下の状態になっています。(# が黒、. が白で塗られていることを表しています)

##.#  
####  
##.#

このとき、i = 1, j = 2 とすれば k = 3 に対して条件を満たすのでこのマス目はサイズ 3 の N を含み、これが最大です。

入力例 2

出力例 2

マス目は以下の状態になっています。

..  
..

どのサイズの N も含まれないので、0 を出力してください。

入力例 3

2 2 2
1 1
2 2

出力例 3

マス目は以下の状態になっています。

.#  
#.

i = 2, j = 1 または i = 1, j = 2 とすれば k = 1 に対して条件を満たします。

入力例 4

出力例 4

マス目は以下の状態になっています。

##.#  
##.#  
#.##  
#..#

D - 木、

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

すけぬくんは n+1 頂点の木 T を持っています。この木 T の頂点には整数がひとつずつ書かれていて、それぞれ 1,2,..., n+1 です。木 T には辺が n 本あり、i 番目の辺は i が書かれた頂点と v_i が書かれた頂点をつないでいます。

ぬすけくんは、すけぬくんが目を離している隙に、木 T に以下のようないたずらをしました。

木 T の頂点のうち、次数が 1 である頂点を 1 つ選んで取り除き、隠しておく
残った n 個の頂点に書かれた整数をすべて消す
残った n 個の頂点それぞれに新しく整数 1,2,..., n をひとつずつ書き加える

ぬすけくんのいたずらのあとの木を T' と呼ぶことにします。木 T' には辺が n-1 本あり、 i 番目の辺は i が書かれた頂点と u_i が書かれた頂点をつないでいます。

ぬすけくんのいたずらに気がついたすけぬくんは、ぬすけくんが隠し持っている頂点にかかれている整数を言い当てたくなりました。このような整数としてありうるものをすべて求め、昇順に出力してください。

制約

2\leq n \leq 2\times 10^5
i=1, 2, \dots, n について 1\leq v_i \leq n+1
i=1, 2, \dots, n-1 について 1\leq u_i \leq n
T （辺 (1, v_1), (2, v_2), \dots, (n, v_{n}) からなるグラフ）は木を成す
T' （辺(1, u_1), (2, u_2), \dots, (n-1, u_{n-1})からなるグラフ）は木を成す
ぬすけくんが隠し持っている頂点としてありうるものが 1 つ以上存在する
入力は全て整数である

入力

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

n
v_1 v_2 \dots v_n
u_1 u_2 \dots u_{n-1}

出力

ぬすけくんが隠し持っている頂点に書かれている可能性のある整数すべてを、昇順に空白区切りで一行に出力してください。

入力例 1

10
2 9 2 2 2 2 6 7 10 11
2 3 4 10 4 5 4 4 4

出力例 1

8 11

次数 1 の頂点は 1,3,4,5,8,11 が書かれた頂点です。

例えば、 11 が書かれている頂点を隠したあと、次のように新しく整数を書き加えれば、木 T' と一致します。

また、8 が書かれている頂点を隠したあと、次のように新しく整数を書き加えれば、木 T' と一致します。

これ以外の頂点を隠したときはどのように整数を書いても木 T' にすることができないため、答えはこれらを小さい順に並べた 8 11 となります。

入力例 2

5
6 1 1 1 1
5 5 5 5

出力例 2

2 3 4 5 6

次数 1 の頂点は 2,3,4,5,6 が書かれた頂点です。どれを取り除いたとしても、うまく整数を書き加えれば木 T' と同じものが作れるので、これらをすべて出力してください。

入力例 3

5
4 3 4 5 6
2 3 4 5

出力例 3

ぬすけくんが隠し持っている頂点には 1 が書かれていることは、すけぬくんにはお見通しです。

E - Notorious B.I.T.

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 800 点

問題文

すぬけ君は長さ N のビット列 S を審査会に提出しようとしています。ここで、ビット列とは 0 と 1 のみからなる文字列を意味します。

審査基準は M 個あり、i\ (1 \leq i \leq M) 番目の審査基準は以下の通りです。

S の L_i 文字目から R_i 文字目までを切り出した部分文字列のうちに 1 が含まれる。

ビット列が満たす審査基準の個数が、そのビット列に対するスコアとなります。

すぬけ君のライバルであるスメケ君は、すぬけ君の提出するビット列 S を Q 回変更することにしました。j\ (1 \leq j \leq Q) 回目の変更では先頭から X_j 文字目を、0 ならば 1 に、1 ならば 0 に変更します。

あなたの仕事はスメケ君の代わりに、Q 回ある変更それぞれの後にできるビット列のスコアを求めることです。

制約

1 \leq N \leq 2 \times 10^5
1 \leq M \leq 10^5
1 \leq Q \leq 2 \times 10^5
S は 0, 1 からなる長さ N の文字列である
1 \leq L_i \leq R_i \leq N
1 \leq X_j \leq N
S 以外の入力はすべて整数である

入力

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

N M Q
S
L_1 R_1
:
L_M R_M
X_1
:
X_Q

出力

Q 行出力してください。i 行目には、i 番目までの変更を施してできるビット列のスコアを出力してください。

入力例 1

出力例 1

1 つ目のクエリの後、ビット列は 010 になり、これは全ての審査条件を満たします。
2 つ目のクエリの後、ビット列は 000 になり、これはどの審査条件も満たしません。
3 つ目のクエリの後、ビット列は 100 になり、これは 1, 3 番目の審査条件を満たします。
4 つ目のクエリの後、ビット列は 101 になり、これは 1, 3, 4 番目の審査条件を満たします。

入力例 2

50 10 10
10010000000001000000001000000000000000000100000000
2 25
11 33
20 31
21 26
26 50
4 42
23 40
2 8
36 37
15 18
20
1
4
49
14
10
23
37
42
20

出力例 2

F - Jumping over 2

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

1 から N の順に番号がついた N 個のマスが一直線に並んでいます。このうち B_1, ..., B_K の K マスには障害物があり、入ることができません。

高橋君は今からマス 1 をスタートして、マス N へ向かおうとしています。

ただし、高橋君が行うことのできる移動方法には制限があります。1 回の移動では、高橋君がマス x にいるとき x + D_1, x + D_2, ..., x + D_M のいずれかのマスに限って移動することができます。

障害物のあるマスや、N 個のマス以外に跳ぶことはできません。

高橋君が 1 回の移動でマス x からマス y に移動するとき、次の条件を満たす最小の非負整数 i のコストがかかります。

x + 1 以上 y 以下の整数のいずれも 2^i で割り切れない。

マスからマスへの移動を繰り返してマス 1 からマス N に到達する経路のコストは、各移動にかかるコストの和です。

有り得る全ての経路についてのコストの和を 998244353 で割ったあまりを求めてください。

制約

3 \leq N \leq 2 \times 10^5
1 \leq K \leq N-2
1 \leq M \leq N-1
1 < B_1 < B_2 < \cdots < B_K < N
0 < D_1 < D_2 < \cdots < D_M < N
入力は全て整数である

入力

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

N K M
B_1 B_2 \cdots B_K
D_1 D_2 \cdots D_M

出力

有り得る全ての経路についてのコストの和を 998244353 で割ったあまりを出力せよ。

入力例 1

3 1 2
2
1 2

出力例 1

可能な経路はマス 1 からマス 3 に移動するもののみです。

条件を満たす最小の非負整数が 2 であることが次のように確かめられるため、マス 1 からマス 3 への移動のコストは 2 です。

2^1 = 2 では 2 が割り切れるため、1 は条件を満たさない。
2^2 = 4 では 2, 3 のいずれも割り切れないので、2 は条件を満たす。

よって、この経路のコストは 2 です。

入力例 2

4 1 3
3
1 2 3

出力例 2

可能な経路は以下の 2 通りがあります。

マス 1 からマス 4 に移動する。この経路のコストは 3 です。
マス 1 からマス 2 に移動し、マス 2 からマス 4 に移動する。この経路のコストは 2 + 3 = 5 です。

よって、全ての経路についてのコストの和は 8 です。

入力例 3

4 2 2
2 3
1 2

出力例 3

そもそもマス 4 にたどり着けないので、0 を出力してください。

入力例 4

10 2 4
2 7
1 2 3 9

出力例 4

G - Road Trip

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

N 頂点の無向木があり、頂点には 1 から N の、辺には 1 から N-1 の番号がついています。辺 i は頂点 A_i と頂点 B_i を結んでおり、C_i の重みを持ちます。重みの値は負である可能性もあることに注意してください。

この木の連結な部分グラフを「運転部分木」と呼び、特に頂点 u と頂点 v を含むものを「u-v 運転部分木」とします。ある運転部分木が持つ辺の重みの合計を、その運転部分木の「楽しさ」とします。

Q 個の整数組 (U_i, V_i) が与えられるので、各 i に対して次の質問に答えてください。

U_i-V_i 運転部分木の楽しさとしてあり得る最大値は何か。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i < B_i \leq N\ (1 \leq i \leq N - 1)
与えられるグラフは木を成す
-10^9 \leq C_i \leq 10^9\ (1 \leq i \leq N - 1)
1 \leq Q \leq 2 \times 10^5
1 \leq U_i < V_i \leq N\ (1 \leq i \leq Q)
入力はすべて整数である

入力

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

N
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
U_1 V_1
:
U_Q V_Q

出力

Q 行出力してください。i 行目には、U_i-V_i 運転部分木の楽しさとしてあり得る最大値を出力してください。

入力例 1

出力例 1

19
16
16

1 つ目の質問に対しては、頂点 2, 3, 4 からなる部分グラフを運転部分木として選ぶと楽しさは 20+(-1) となり、これが 2-3 運転部分木の楽しさのうち最大です。
2 つ目と 3 つ目の質問に対しては、頂点 1, 2, 3, 5, 6, 7 からなる部分グラフを運転部分木として選ぶと楽しさは (-10)+20+1+3+2 となり、どちらの質問でもこれが最大です。

入力例 2

7
1 3 -1100000
2 3 -1010000
3 4 -1001000
1 6 -1000100
5 6 -1000010
6 7 -1000001
3
3 4
5 7
2 6

出力例 2

-1001000
-2000011
-3110100

入力例 3

18
2 8 -133775141
3 16 -311103251
4 11 849496136
9 14 -442278959
8 13 946094213
8 14 714669159
5 8 210787603
5 11 8973730
10 15 581490293
10 16 -347827761
10 11 -126622449
7 11 431568122
6 7 -458490133
6 17 -314331217
1 6 -220056853
1 12 -981864951
12 18 183014767
20
1 15
7 10
6 12
1 18
3 16
4 8
9 12
2 14
1 11
3 8
14 17
4 17
12 18
3 17
1 10
5 9
9 15
4 13
5 11
4 7

出力例 3

H - 逆にする関数

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

1, 2, \dots , m からなる数列 (v_1, v_2, \dots, v_k) と関数 f\colon \{1,\dots,m\} \to \{1,\dots,m\} について、 f が以下の条件を満たすとき、f が (v_1, v_2, \dots, v_k) を逆にする と言います。

数列 (f(v_1), f(v_2), \dots, f(v_k)) はもとの数列をひっくり返した数列 (v_k, v_{k-1}, \dots, v_1) と一致する

1, 2, \dots ,m からなる数列 (a_1, a_2, \dots, a_n) が与えられます。この数列の空でない連続部分列は \frac{n(n+1)}{2} 通りありますが、逆にする関数が何通り存在するかをこれら全てに対して数え上げて、その総和を 998244353 で割ったあまりを求めてください。

注意

関数 f と g について f(i)\neq g(i) となる i\in \{1,\dots,m\} が存在するとき f と g が異なる関数であるとみなす

制約

1\leq n, m \leq 3\times 10^5
各 i=1, 2, \dots, n について 1\leq a_i \leq m
入力はすべて整数である

入力

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

n m
a_1 a_2 \dots a_n

出力

数列の各連続部分列についての逆にする関数の数の合計を 998244353 で割ったあまりを出力してください。

入力例 1

3 3
1 1 2

出力例 1

数列 (1, 1, 2) の連続部分列は (1) と (1, 1) と (1, 1, 2) と (1) と (1, 2) と (2) です。

関数 f が数列 (1) を逆にするための必要十分条件は f(1)=1 で、この条件を満たす \{1, 2, 3\} 上の関数は 9 通りあります。
関数 f が数列 (1, 1) を逆にするための必要十分条件は f(1)=1 で、この条件を満たす \{1, 2, 3\} 上の関数は 9 通りあります。
関数 f が数列 (1, 1, 2) を逆にするための必要十分条件は f(1)=2 かつ f(1)=1 かつ f(2)=1 で、この条件を満たす関数はありません。
関数 f が数列 (1, 2) を逆にするための必要十分条件は f(1)=2 かつ f(2)=1 で、この条件を満たす \{1, 2, 3\} 上の関数は 3 通りあります。
関数 f が数列 (2) を逆にするための必要十分条件は f(2)=2 で、この条件を満たす \{1, 2, 3\} 上の関数は 9 通りあります。

よって、答えは 9 + 9 + 0 + 9 + 3 + 9 = 39 です。

入力例 2

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

出力例 2

326566600

998244353 で割ったあまりを取るのを忘れないようにしてください。

入力例 3

46 128
109 98 111 106 103 46 51 46 58 50 49 51 106 102 108 108 106 111 48 116 117 116 102 117 111 112 100 48 113 107 47 115 102 101 112 100 117 98 48 48 59 116 113 117 117 105

出力例 3

249064602