Tokio Marine & Nichido Fire Insurance Programming Contest 2024（AtCoder Beginner Contest 355)

A - Who Ate the Cake?

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

高橋君のケーキが誰かに食べられてしまいました。ケーキを食べた犯人の候補として、人 1、人 2、人 3 の三人が挙げられています。

犯人の目撃者はりんごさんとすぬけくんの二人がいます。りんごさんは人 A が犯人でないことを覚えており、すぬけくんは人 B が犯人でないことを覚えています。

二人の記憶から犯人を一人に特定できるかどうか判定し、特定できるならばその人の番号を出力してください。

制約

1\leq A,B\leq 3
入力は全て整数

入力

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

A B

出力

二人の記憶から犯人を一人に特定できるならばその人の番号を出力し、特定できないならば -1 を出力せよ。

入力例 1

1 2

出力例 1

二人の記憶から、人 3 が犯人であることが特定できます。

入力例 2

1 1

出力例 2

-1

二人の記憶からでは、人 2,3 のどちらが犯人か特定することができません。よって -1 を出力します。

入力例 3

3 1

出力例 3

Score : 100 points

Problem Statement

Takahashi's cake has been eaten by someone. There are three suspects: person 1, person 2, and person 3.

There are two witnesses, Ringo and Snuke. Ringo remembers that person A is not the culprit, and Snuke remembers that person B is not the culprit.

Determine if the culprit can be uniquely identified based on the memories of the two witnesses. If the culprit can be identified, print the person's number.

Constraints

1 \leq A, B \leq 3
All input values are integers.

Input

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

A B

Output

If the culprit can be uniquely identified based on the memories of the two witnesses, print the person's number; otherwise, print -1.

Sample Input 1

1 2

Sample Output 1

From the memories of the two witnesses, it can be determined that person 3 is the culprit.

Sample Input 2

1 1

Sample Output 2

-1

From the memories of the two witnesses, it cannot be determined whether person 2 or person 3 is the culprit. Therefore, print -1.

Sample Input 3

3 1

Sample Output 3

B - Piano 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) と、長さ M の数列 B=(B_1,B_2,\dots,B_M) が与えられます。ここで、A,B のすべての要素は互いに相異なります。A,B のすべての要素を昇順に並べた長さ N+M の数列 C=(C_1,C_2,\dots,C_{N+M}) において、A に現れる要素が2つ連続するかどうか判定してください。

制約

1\leq N,M \leq 100
1\leq A_i,B_j \leq 200
A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M は相異なる
入力はすべて整数

入力

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

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

出力

A に現れる要素が C において2つ連続するならば Yes を、そうでないなら No を出力せよ。

入力例 1

3 2
3 2 5
4 1

出力例 1

Yes

C=(1,2,3,4,5) です。A に現れる 2,3 が C で連続しているため、Yes を出力します。

入力例 2

3 2
3 1 5
4 2

出力例 2

No

C=(1,2,3,4,5) です。A に現れる要素が C で連続している箇所はないため、No を出力します。

入力例 3

1 1
1
2

出力例 3

No

Score : 200 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N and a sequence B=(B_1,B_2,\dots,B_M) of length M. Here, all elements of A and B are pairwise distinct. Determine whether the sequence C=(C_1,C_2,\dots,C_{N+M}) formed by sorting all elements of A and B in ascending order contains two consecutive elements appearing in A.

Constraints

1 \leq N, M \leq 100
1 \leq A_i, B_j \leq 200
A_1, A_2, \dots, A_N, B_1, B_2, \dots, B_M are distinct.
All input values are integers.

Input

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

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

Output

If C contains two consecutive elements appearing in A, print Yes; otherwise, print No.

Sample Input 1

3 2
3 2 5
4 1

Sample Output 1

Yes

C=(1,2,3,4,5). Since 2 and 3 from A occur consecutively in C, print Yes.

Sample Input 2

3 2
3 1 5
4 2

Sample Output 2

No

C=(1,2,3,4,5). Since no two elements from A occur consecutively in C, print No.

Sample Input 3

1 1
1
2

Sample Output 3

No

C - Bingo 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

縦 N 行、横 N 列のマス目があり、上から i 行目、左から j 列目のマスには整数 N\times (i-1)+j が書かれています。

今から T ターンにわたって相異なる整数が宣言されます。i ターン目には A_i が宣言され、A_i が書かれたマスに印をつけます。初めてビンゴを達成するのは何ターン目か求めてください。ただし、T ターンの中でビンゴを達成しない場合は -1 を出力してください。

ここで、ビンゴを達成するとは以下のいずれかのうち少なくとも一つ満たされることを言います。

マス目の横の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
マス目の縦の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
マス目の対角線の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する

制約

2\leq N\leq 2\times 10^3
1\leq T\leq \min(N^2,2\times 10^5)
1\leq A_i\leq N^2
i\neq j ならば A_i\neq A_j
入力は全て整数

入力

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

N T
A_1 A_2 \ldots A_T

出力

T ターンの中でビンゴを達成するならば初めてビンゴを達成するターンを、そうでないならば -1 を出力せよ。

入力例 1

3 5
5 1 8 9 7

出力例 1

マス目の状態は以下のように変化します。初めてビンゴを達成するのは 4 ターン目です。

入力例 2

3 5
4 2 9 7 5

出力例 2

-1

5 ターンの中でビンゴを達成できないので -1 を出力してください。

入力例 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

出力例 3

Score : 300 points

Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

There exists a row in which all N cells are marked.
There exists a column in which all N cells are marked.
There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

2 \leq N \leq 2 \times 10^3
1 \leq T \leq \min(N^2, 2 \times 10^5)
1 \leq A_i \leq N^2
A_i \neq A_j if i \neq j.
All input values are integers.

Input

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

N T
A_1 A_2 \ldots A_T

Output

If Bingo is achieved within T turns, print the turn number on which Bingo is achieved for the first time; otherwise, print -1.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

D - Intersecting Intervals

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 個の実数の区間が与えられます。i\,(1 \leq i \leq N) 番目の区間は [l_i,r_i] です。i 番目の区間と j 番目の区間が共通部分を持つような組 (i,j)\,(1\leq i < j \leq N) の個数を求めてください。

制約

2 \leq N \leq 5 \times 10^5
0 \leq l_i < r_i \leq 10^9
入力はすべて整数

入力

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

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N

出力

答えを出力せよ。

入力例 1

出力例 1

与えられた区間は [1,5], [7,8], [3,7] です。このうち，1 番目と 3 番目、 2 番目と 3 番目の区間が共通部分を持つため、答えは 2 です。

入力例 2

出力例 2

入力例 3

2
1 2
3 4

出力例 3

Score : 400 points

Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

Constraints

2 \leq N \leq 5 \times 10^5
0 \leq l_i < r_i \leq 10^9
All input values are integers.

Input

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

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N

Output

Print the answer.

Sample Input 1

Sample Output 1

The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.

Sample Input 2

Sample Output 2

Sample Input 3

2
1 2
3 4

Sample Output 3

E - Guess the Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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

正整数 N および 0 以上 2^N 未満の整数 L,R(L\leq R) が与えられます。ジャッジシステムは、0 以上 99 以下の整数からなる長さ 2^N の数列 A = (A_0, A_1, \dots, A_{2^N-1}) を隠し持っています。

あなたの目標は A_L+A_{L+1}+\dots+A_{R} を 100 で割った余りを求めることです。ただし、あなたは数列 A の要素の値を直接知ることはできません。その代わりに、ジャッジシステムに対して以下の質問を行うことができます。

2^i(j+1)\leq 2^N を満たすように非負整数 i,j を選ぶ。l=2^ij,r=2^i(j+1)-1 として A_l+A_{l+1}+\dots+A_{r} を 100 で割った余りを聞く。

どのような A であっても A_L+A_{L+1}+\dots+A_{R} を 100 で割った余りを特定することができる質問回数の最小値を m とします。m 回以内の質問を行って A_L+A_{L+1}+\dots+A_{R} を 100 で割った余りを求めてください。

制約

1\leq N\leq 18
0\leq L\leq R\leq 2^N-1
入力は全て整数

入出力

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

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

N L R

次に、A_L+A_{L+1}+\dots+A_{R} を 100 で割った余りを特定できるまで質問を繰り返してください。質問は、以下の形式で標準出力に出力してください。

? i j

ここで、i,j は以下を満たす必要があります。

i,j は非負整数
2^i(j+1)\leq 2^N

これに対する応答は、次の形式で標準入力から与えられます。

ここで、T は質問に対する答えで、l=2^ij,r=2^i(j+1)-1 としたとき A_l+A_{l+1}+\dots+A_{r} を 100 で割った余りです。

ただし、i,j が制約を満たしていないか、質問回数が m 回を超えた場合は T は -1 となります。

ジャッジが -1 を返した場合、プログラムはすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。

A_L+A_{L+1}+\dots+A_{R} を 100 で割った余りが特定出来たら、S を A_L+A_{L+1}+\dots+A_{R} を 100 で割った余りとして以下の形式で出力してください。その後、ただちにプログラムを終了してください。

! S

注意点

出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
対話の途中で誤った出力形式による出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。

入出力例

以下は、N=3,L=1,R=5,A=(31,41,59,26,53,58,97,93) の場合の入出力例です。この場合 m=3 であるため、質問を 3 回まで行うことができます。

入力	出力	説明
`3 1 5`		まず整数 `N,L,R` が与えられます。
	`? 0 1`	`(i,j)=(0,1)` として質問を行います。
`41`		`l=1,r=1` であるため、質問の答えは `A_1=41` を `100` で割った余りである `41` です。ジャッジはその値を返します。
	`? 1 1`	`(i,j) = (1,1)` として質問を行います。
`85`		`l=2,r=3` であるため、質問の答えは `A_2+A_3=85` を `100` で割った余りである `85` です。ジャッジはその値を返します。
	`? 1 2`	`(i,j) = (1,2)` として質問を行います。
`11`		`l=4,r=5` であるため、質問の答えは `A_4+A_5=111` を `100` で割った余りである `11` です。ジャッジはその値を返します。
	`! 37`	答えは `37` であるとわかったので、それを出力します。

Score : 500 points

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer N and integers L and R such that 0 \leq L \leq R < 2^N. The judge has a hidden sequence A = (A_0, A_1, \dots, A_{2^N-1}) consisting of integers between 0 and 99, inclusive.

Your goal is to find the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. However, you cannot directly know the values of the elements in the sequence A. Instead, you can ask the judge the following question:

Choose non-negative integers i and j such that 2^i(j+1) \leq 2^N. Let l = 2^i j and r = 2^i (j+1) - 1. Ask for the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100.

Let m be the minimum number of questions required to determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100 for any sequence A. You need to find this remainder within m questions.

Constraints

1 \leq N \leq 18
0 \leq L \leq R \leq 2^N - 1
All input values are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read the integers N, L, and R from Standard Input:

N L R

Then, repeat asking questions until you can determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. Each question should be printed in the following format:

? i j

Here, i and j must satisfy the following constraints:

i and j are non-negative integers.
2^i(j+1) \leq 2^N

The response to the question will be given in the following format from Standard Input:

Here, T is the answer to the question, which is the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100, where l = 2^i j and r = 2^i (j+1) - 1.

If i and j do not satisfy the constraints, or if the number of questions exceeds m, then T will be -1.

If the judge returns -1, your program is already considered incorrect. In this case, terminate the program immediately.

Once you have determined the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100, print the remainder S in the following format and terminate the program immediately:

! S

Notes

At the end of each output, print a newline and flush Standard Output. Otherwise, the verdict may be TLE.
If your output is malformed or your program exits prematurely, the verdict will be indeterminate.
After printing the answer, terminate the program immediately. Otherwise, the verdict will be indeterminate.

Example

Here is an example for N=3, L=1, R=5, and A=(31, 41, 59, 26, 53, 58, 97, 93). In this case, m=3, so you can ask up to three questions.

Input	Output	Description
`3 1 5`		First, the integers `N`, `L`, and `R` are given.
	`? 0 1`	Ask the question with `(i, j) = (0, 1)`.
`41`		`l=1` and `r=1`, so the response is the remainder when `A_1=41` is divided by `100`, which is `41`. The judge returns this value.
	`? 1 1`	Ask the question with `(i, j) = (1, 1)`.
`85`		`l=2` and `r=3`, so the response is the remainder when `A_2 + A_3 = 85` is divided by `100`, which is `85`. The judge returns this value.
	`? 1 2`	Ask the question with `(i, j) = (1, 2)`.
`11`		`l=4` and `r=5`, so the response is the remainder when `A_4 + A_5 = 111` is divided by `100`, which is `11`. The judge returns this value.
	`! 37`	The answer is `37`, so print this value.

F - MST Query

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 550 点

問題文

頂点に 1 から N の番号が、辺に 1 から N-1 の番号が付いた N 頂点 N-1 辺の重み付き無向連結グラフ G が与えられます。辺 i は頂点 a_i と頂点 b_i を結んでおり、その重みは c_i です。

Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。

整数 u_i,v_i,w_i が与えられる。G の頂点 u_i,v_i の間に重み w_i の辺を追加する。その後、G の最小全域木に含まれる辺の重みの和を出力する。

制約

2\leq N\leq 2 \times 10^5
1\leq Q\leq 2 \times 10^5
1\leq a_i\lt b_i\leq N
1\leq u_i\lt v_i\leq N
1\leq c_i,w_i\leq 10
クエリを処理する前のグラフは連結
入力はすべて整数

入力

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

N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q

出力

Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

各クエリで辺を追加した後のグラフを示しています。最小全域木に含まれる辺は赤色で塗られています。

入力例 2

出力例 2

Score : 550 points

Problem Statement

You are given a weighted undirected connected graph G with N vertices and N-1 edges, where vertices are numbered 1 to N and edges are numbered 1 to N-1. Edge i connects vertices a_i and b_i with a weight of c_i.

You are given Q queries to process sequentially. The i-th query is described as follows:

You are given integers u_i, v_i, w_i. Add an edge with weight w_i between vertices u_i and v_i in G. Then, print the sum of the weights of the edges in a minimum spanning tree of G.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq a_i < b_i \leq N
1 \leq u_i < v_i \leq N
1 \leq c_i, w_i \leq 10
The graph is connected before processing the queries.
All input values are integers.

Input

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

N Q
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
u_1 v_1 w_1
\vdots
u_Q v_Q w_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

Here is the graph after adding the edge for each query. The edges included in the minimum spanning tree are colored red.

Sample Input 2

Sample Output 2

G - Baseball

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 650 点

問題文

長さ N の数列 P=(P_1,P_2,\dots,P_N) が与えられます。高橋君と青木君が、数列 P を使ってゲームを行います。

まず、高橋君が、 1,2,\dots,N から K 個の相異なる整数 x_1,x_2,\dots,x_K を選びます。

次に、青木君が、 1,2,\dots,N から 1 つの整数 y を P_y に比例する確率で選びます。すなわち、整数 y が選ばれる確率は \dfrac{P_y}{\sum_{y'=1}^N P_{y'}} です。そして、青木君が \displaystyle \min_{i=1,2,\dots,K} |x_i-y| のスコアを得ます。

高橋君は、青木君が得るスコアの期待値を最小化したいです。高橋君が適切に x_1,x_2,\dots,x_K を選んだときに、青木君が得るスコアの期待値の最小値を \sum_{y'=1}^N P_{y'} 倍した値を求めてください。なお、出力すべき値は整数になることが証明できます。

制約

1 \leq N \leq 5 \times 10^4
1 \leq K \leq N
0 \leq P_i \leq 10^5
1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
入力はすべて整数

入力

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

N K
P_1 P_2 \dots P_N

出力

答えを出力せよ。

入力例 1

5 2
1 1 1 1 1

出力例 1

青木君が 1,2,\dots,N を選ぶ確率はすべて等しく \frac{1}{5} です。

高橋君が x_1=2,x_2=4 と選んだとすると、青木君が得るスコアの期待値は 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5} です。

高橋君が x_1=2,x_2=3 と選んだとすると、青木君が得るスコアの期待値は 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5} です。

高橋君が他の選び方をしても、青木君が得るスコアの期待値は \frac{3}{5} より小さくなりません。よって最小値は \frac{3}{5} であり、これを 5 倍した 3 を出力します。

入力例 2

5 1
0 0 1 0 0

出力例 2

入力例 3

1 1
100

出力例 3

入力例 4

20 7
4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928

出力例 4

Score : 650 points

Problem Statement

You are given a sequence P=(P_1,P_2,\dots,P_N) of length N. Takahashi and Aoki will play a game using the sequence P.

First, Takahashi will choose K distinct integers x_1,x_2,\dots,x_K from 1,2,\dots,N.

Next, Aoki will choose an integer y from 1,2,\dots,N with a probability proportional to P_y. That is, the probability that integer y is chosen is \dfrac{P_y}{\sum_{y'=1}^N P_{y'}}. Then, Aoki's score will be \displaystyle \min_{i=1,2,\dots,K} |x_i-y|.

Takahashi wants to minimize the expected value of Aoki's score. Find the expected value of Aoki's score when Takahashi chooses x_1,x_2,\dots,x_K so that this value is minimized, multiplied by \sum_{y'=1}^N P_{y'}. It is guaranteed that the value to be printed is an integer.

Constraints

1 \leq N \leq 5 \times 10^4
1 \leq K \leq N
0 \leq P_i \leq 10^5
1 \leq \sum_{y'=1}^N P_{y'} \leq 10^5
All input values are integers.

Input

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

N K
P_1 P_2 \dots P_N

Output

Print the answer.

Sample Input 1

5 2
1 1 1 1 1

Sample Output 1

The probabilities of Aoki choosing 1,2,\dots,N are all equal: \frac{1}{5}.

If Takahashi chooses x_1=2 and x_2=4, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} = \frac{3}{5}.

If Takahashi chooses x_1=2 and x_2=3, then the expected value of Aoki's score will be 1 \times \frac{1}{5} + 0 \times \frac{1}{5} + 0 \times \frac{1}{5} + 1 \times \frac{1}{5} + 2 \times \frac{1}{5} = \frac{4}{5}.

No matter how Takahashi chooses, the expected value of Aoki's score cannot be smaller than \frac{3}{5}. Therefore, the minimum value is \frac{3}{5}, so print this value multiplied by 5, which is 3.

Sample Input 2

5 1
0 0 1 0 0

Sample Output 2

Sample Input 3

1 1
100

Sample Output 3

Sample Input 4

20 7
4262 9522 2426 3823 7364 964 2743 2423 1955 5274 3684 847 363 35 278 3220 203 2904 6304 1928