AtCoder Daily Training HARD 2024/04/24 18:00start

E - Final Day

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 人の生徒が 4 日間にわたる試験を受けています。

それぞれの日に行われる試験は 300 点満点です。すなわち、4 日間を通した試験の満点は 1200 点です。

現在 3 日目までの試験が終わり、これから 4 日目の試験が行われようとしています。i \, (1 \leq i \leq N) 番目の生徒は j \, (1 \leq j \leq 3) 日目の試験で P_{i, j} 点獲得しました。

それぞれの生徒について、4 日目の試験後に上位 K 位以内に入っていることがあり得るかどうか判定してください。
ただし、4 日目の試験後の生徒の順位は、その生徒よりも 4 日間の合計点が高い生徒の人数に 1 を加えた値として定めます。

制約

1 \leq K \leq N \leq 10^5
0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
入力は全て整数である。

入力

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

N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、i 番目の生徒が 4 日目の試験後に上位 K 位以内に入っていることがあり得るならば Yes と、そうでないならば No と出力せよ。

入力例 1

3 1
178 205 132
112 220 96
36 64 20

出力例 1

Yes
Yes
No

4 日目に全員が 100 点を取ると、1 番目の生徒が 1 位になります。 4 日目に 2 番目の生徒が 100 点を取り、それ以外の生徒が 0 点を取ると、2 番目の生徒が 1 位になります。 3 番目の生徒が 1 位になることはあり得ません。

入力例 2

2 1
300 300 300
200 200 200

出力例 2

Yes
Yes

入力例 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

出力例 3

Yes
Yes
No
Yes

Score : 300 points

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

1 \leq K \leq N \leq 10^5
0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain Yes if it is possible that the i-th student is ranked in the top K after the fourth day, and No otherwise.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

F - Dice Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？

1\le A_i \le M (1 \le i \le N)
\displaystyle\sum _{i=1}^N A_i \leq K

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。

制約

1 \leq N, M \leq 50
N \leq K \leq NM
入力は全て整数

入力

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

N M K

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

2 3 4

出力例 1

条件を満たす数列は以下の 6 つです。

(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(3,1)

入力例 2

31 41 592

出力例 2

798416518

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

Score : 300 points

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

1\le A_i \le M (1 \le i \le N)
\displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

1 \leq N, M \leq 50
N \leq K \leq NM
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

The following six sequences satisfy the conditions.

(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(3,1)

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.

G - 8 Puzzle on Graph

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は道端であるパズルを拾いました。
このパズルは、9 個の頂点と M 本の辺からなる無向グラフ、および、8 つのコマで構成されます。

グラフの 9 つの頂点はそれぞれ頂点 1、頂点 2、\ldots、頂点 9 と呼ばれ、 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。
8 つのコマはそれぞれコマ 1、コマ 2、\ldots、コマ 8 と呼ばれ、 j = 1, 2, \ldots, 8 について、コマ j は頂点 p_j に置かれています。ここで、すべてのコマはそれぞれ異なる頂点に置かれていることが保証されます。コマが置かれていない「空の頂点」がただ一つ存在することに注意してください。

高橋君はこのパズルに対して下記の操作を好きな回数（ 0 回でもよい）だけ行うことができます。

空の頂点に隣接する頂点に置かれたコマを 1 つ選び、選んだコマを空の頂点に移動する。

高橋君は上記の操作を繰り返して、このパズルを「完成」させようとしています。パズルは、下記の状態を満たしたときに完成となります。

j = 1, 2, \ldots, 8 について、コマ j は頂点 j に置かれている。

高橋君がパズルを完成させることが可能かどうかを判定し、可能な場合はそのために必要な操作回数の最小値を出力してください。

制約

0 \leq M \leq 36
1 \leq u_i, v_i \leq 9
与えられるグラフは多重辺、自己ループを持たない
1 \leq p_j \leq 9
j \neq j' \Rightarrow p_j \neq p_{j'}
入力はすべて整数

入力

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

M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
p_1 p_2 \ldots p_8

出力

高橋君がパズルを完成させることが可能な場合は、そのために必要な操作回数の最小値を出力せよ。高橋君がパズルを完成させることが不可能な場合は、-1 を出力せよ。

入力例 1

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

出力例 1

下記の手順によって、5 回の操作でパズルを完成させることができます。

コマ 2 を頂点 9 から頂点 1 に移動する。
コマ 3 を頂点 2 から頂点 9 に移動する。
コマ 2 を頂点 1 から頂点 2 に移動する。
コマ 1 を頂点 3 から頂点 1 に移動する。
コマ 3 を頂点 9 から頂点 3 に移動する。

一方、5 回未満の操作でパズルを完成させることはできません。よって、5 を出力します。
与えられるグラフは連結とは限らないことに注意してください。

入力例 2

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

出力例 2

パズルは初めから完成しています。よって、完成させるために必要な操作回数の最小値は 0 回です。

入力例 3

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

出力例 3

-1

操作の繰り返しによってパズルを完成させることができないので、-1 を出力します。

入力例 4

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

出力例 4

Score : 400 points

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and M edges, and eight pieces.

The nine vertices of the graph are called Vertex 1, Vertex 2, \ldots, Vertex 9. For each i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
The eight pieces are called Piece 1, Piece 2, \ldots, Piece 8. For each j = 1, 2, \ldots, 8, Piece j is on Vertex p_j.
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

For each j = 1, 2, \ldots, 8, Piece j is on Vertex j.

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

0 \leq M \leq 36
1 \leq u_i, v_i \leq 9
The given graph has no multi-edges or self-loops.
1 \leq p_j \leq 9
j \neq j' \Rightarrow p_j \neq p_{j'}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
p_1 p_2 \ldots p_8

Output

If it is possible for Takahashi to complete the puzzle, find the minimum number of operations needed to do so. Otherwise, print -1.

Sample Input 1

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

Sample Output 1

The following procedure completes the puzzle in five operations.

Move Piece 2 from Vertex 9 to Vertex 1.
Move Piece 3 from Vertex 2 to Vertex 9.
Move Piece 2 from Vertex 1 to Vertex 2.
Move Piece 1 from Vertex 3 to Vertex 1.
Move Piece 3 from Vertex 9 to Vertex 3.

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print 5.
Note that the given graph may not be connected.

Sample Input 2

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

Sample Output 2

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is 0.

Sample Input 3

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

Sample Output 3

-1

No sequence of operations can complete the puzzle, so we should print -1.

Sample Input 4

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

Sample Output 4

H - Unfair Sugoroku

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君と青木君がすごろくをします。
高橋君ははじめ地点 A、青木君ははじめ地点 B にいて、交互にサイコロを振ります。
高橋君が振るサイコロは 1, 2, \ldots, P の出目が一様ランダムに出るサイコロで、青木君が振るサイコロは 1, 2, \ldots, Q の出目が一様ランダムに出るサイコロです。
地点 x にいるときに自分の振ったサイコロの出目が i であるとき、地点 \min(x + i, N) に進みます。
地点 N に先に着いた人をすごろくの勝者とします。
高橋君が先にサイコロを振るとき、高橋君が勝つ確率を \text{mod }998244353 で求めてください。

確率 \text{mod }998244353 とは

この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod {998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。

制約

2 \leq N \leq 100
1 \leq A, B < N
1 \leq P, Q \leq 10
入力はすべて整数

入力

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

N A B P Q

出力

答えを出力せよ。

入力例 1

4 2 3 3 2

出力例 1

665496236

高橋君が最初の手番で 2 あるいは 3 の出目を出すと、高橋君は地点 4 に進んで高橋君が勝利します。
高橋君が最初の手番で 1 の出目を出すと、高橋君は地点 3 に進み、青木君は次の手番で必ず地点 4 に進んで青木君が勝利します。
よって、高橋君が勝つ確率は \frac{2}{3} です。

入力例 2

6 4 2 1 1

出力例 2

サイコロの出目は常に 1 です。
このとき高橋君が地点 5 に進み、次いで青木君が地点 3 に進み、次いで高橋君が地点 6 に進むので、高橋君は必ず勝ちます。

入力例 3

100 1 1 10 10

出力例 3

264077814

Score : 500 points

Problem Statement

Takahashi and Aoki will play a game of sugoroku.
Takahashi starts at point A, and Aoki starts at point B. They will take turns throwing dice.
Takahashi's die shows 1, 2, \ldots, P with equal probability, and Aoki's shows 1, 2, \ldots, Q with equal probability.
When a player at point x throws his die and it shows i, he goes to point \min(x + i, N).
The first player to reach point N wins the game.
Find the probability that Takahashi wins if he goes first, modulo 998244353.

How to find a probability modulo 998244353

It can be proved that the sought probability is always rational. Additionally, the constraints of this problem guarantee that, if that probability is represented as an irreducible fraction \frac{y}{x}, then x is indivisible by 998244353.
Here, there is a unique integer z between 0 and 998244352 such that xz \equiv y \pmod {998244353}. Report this z.

Constraints

2 \leq N \leq 100
1 \leq A, B < N
1 \leq P, Q \leq 10
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N A B P Q

Output

Print the answer.

Sample Input 1

4 2 3 3 2

Sample Output 1

665496236

If Takahashi's die shows 2 or 3 in his first turn, he goes to point 4 and wins.
If Takahashi's die shows 1 in his first turn, he goes to point 3, and Aoki will always go to point 4 in the next turn and win.
Thus, Takahashi wins with the probability \frac{2}{3}.

Sample Input 2

6 4 2 1 1

Sample Output 2

The dice always show 1.
Here, Takahashi goes to point 5, Aoki goes to point 3, and Takahashi goes to point 6, so Takahashi always wins.

Sample Input 3

100 1 1 10 10

Sample Output 3

264077814

I - Earn to Advance

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

縦 N 行横 N 列のグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。

高橋君は最初マス (1,1) におり、所持金は 0 です。

高橋君はマス (i,j) にいるとき、1 回の行動で以下のいずれかを行うことができます。

同じマスにとどまり、所持金を P_{i,j} 増やす。
所持金から R_{i,j} 払ってマス (i,j+1) に移動する。
所持金から D_{i,j} 払ってマス (i+1,j) に移動する。

所持金が負になる移動、グリッドの外に出る移動はできません。

高橋君が最適に行動したとき、何回の行動でマス (N,N) にたどり着くことができますか。

制約

2 \leq N \leq 80
1 \leq P_{i,j} \leq 10^9
1 \leq R_{i,j},D_{i,j} \leq 10^9
入力は全て整数である

入力

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

N
P_{1,1} \ldots P_{1,N}
\vdots
P_{N,1} \ldots P_{N,N}
R_{1,1} \ldots R_{1,N-1}
\vdots
R_{N,1} \ldots R_{N,N-1}
D_{1,1} \ldots D_{1,N}
\vdots
D_{N-1,1} \ldots D_{N-1,N}

出力

答えを出力せよ。

入力例 1

出力例 1

以下のようにして 8 回の行動でマス (3,3) にたどり着くことができます。

マス (1,1) にとどまり、所持金を 1 増やす。所持金は 1 になる。
所持金から 1 払ってマス (2,1) に移動する。所持金は 0 になる。
マス (2,1) にとどまり、所持金を 3 増やす。所持金は 3 になる。
マス (2,1) にとどまり、所持金を 3 増やす。所持金は 6 になる。
マス (2,1) にとどまり、所持金を 3 増やす。所持金は 9 になる。
所持金から 4 払ってマス (2,2) に移動する。所持金は 5 になる。
所持金から 3 払ってマス (3,2) に移動する。所持金は 2 になる。
所持金から 2 払ってマス (3,3) に移動する。所持金は 0 になる。

入力例 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

出力例 2

4000000004

Score: 550 points

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

Takahashi is initially at square (1,1) with zero money.

When Takahashi is at square (i,j), he can perform one of the following in one action:

Stay at the same square and increase his money by P_{i,j}.
Pay R_{i,j} from his money and move to square (i,j+1).
Pay D_{i,j} from his money and move to square (i+1,j).

He cannot make a move that would make his money negative or take him outside the grid.

If Takahashi acts optimally, how many actions does he need to reach square (N,N)?

Constraints

2 \leq N \leq 80
1 \leq P_{i,j} \leq 10^9
1 \leq R_{i,j},D_{i,j} \leq 10^9
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_{1,1} \ldots P_{1,N}
\vdots 
P_{N,1} \ldots P_{N,N}
R_{1,1} \ldots R_{1,N-1}
\vdots
R_{N,1} \ldots R_{N,N-1}
D_{1,1} \ldots D_{1,N}
\vdots
D_{N-1,1} \ldots D_{N-1,N}

Output

Print the answer.

Sample Input 1

Sample Output 1

It is possible to reach square (3,3) in eight actions as follows:

Stay at square (1,1) and increase money by 1. His money is now 1.
Pay 1 money and move to square (2,1). His money is now 0.
Stay at square (2,1) and increase money by 3. His money is now 3.
Stay at square (2,1) and increase money by 3. His money is now 6.
Stay at square (2,1) and increase money by 3. His money is now 9.
Pay 4 money and move to square (2,2). His money is now 5.
Pay 3 money and move to square (3,2). His money is now 2.
Pay 2 money and move to square (3,3). His money is now 0.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Sample Output 2

4000000004