AtCoder Daily Training HARD 2024/04/18 16:30start

E - Extra Character

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。

挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。

制約

1 \leq |S| \leq 5\times 10^5
S は英小文字からなる
T は S に英小文字を 1 つ挿入して作られた文字列である

入力

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

S
T

出力

答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。

入力例 1

atcoder
atcorder

出力例 1

T の先頭から 5 番目の文字 r が挿入された文字です。

入力例 2

million
milllion

出力例 2

T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。

入力例 3

vvwvw
vvvwvw

出力例 3

Score : 300 points

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

1 \leq |S| \leq 5\times 10^5
S consists of lowercase English letters.
T is obtained by inserting a lowercase English letter into S.

Input

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

S
T

Output

Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.

Sample Input 1

atcoder
atcorder

Sample Output 1

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

F - Inverse of Permutation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

1,2,\dots,N が 1 回ずつ現れる長さ N の数列を「長さ N の順列」と呼びます。
長さ N の順列 P = (p_1, p_2,\dots,p_N) が与えられるので、以下の条件を満たす長さ N の順列 Q = (q_1,\dots,q_N) を出力してください。

全ての i (1 \leq i \leq N) に対して Q の p_i 番目の要素が i である。

ただし、条件を満たす Q は必ずただ 1 つ存在することが証明できます。

制約

1 \leq N \leq 2 \times 10^5
(p_1,p_2,\dots,p_N) は長さ N の順列である。
入力は全て整数である。

入力

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

N
p_1 p_2 \dots p_N

出力

数列 Q を空白区切りで 1 行で出力せよ。

q_1 q_2 \dots q_N

入力例 1

3
2 3 1

出力例 1

3 1 2

以下に説明する通り、 Q=(3,1,2) は条件を満たす順列です。

i = 1 のとき p_i = 2, q_2 = 1
i = 2 のとき p_i = 3, q_3 = 2
i = 3 のとき p_i = 1, q_1 = 3

入力例 2

3
1 2 3

出力例 2

1 2 3

全ての i (1 \leq i \leq N) に対して p_i = i が成り立つときは P = Q になります。

入力例 3

5
5 3 2 4 1

出力例 3

5 3 2 4 1

Score : 300 points

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

1 \leq N \leq 2 \times 10^5
(p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 \dots p_N

Output

Print the sequence Q in one line, with spaces in between.

q_1 q_2 \dots q_N

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

For i = 1, we have p_i = 2, q_2 = 1.
For i = 2, we have p_i = 3, q_3 = 2.
For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

G - Dance

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

1, 2, \ldots, 2N と番号づけられた 2N 人の人が舞踏会に参加します。彼らは N 個の 2 人組にわかれてダンスを踊ります。

2 人組を構成する人のうち、番号の小さい方の人が人 i 、番号の大きい方の人が人 j のとき、その 2 人組の「相性」は A_{i, j} です。
N 個の 2 人組の相性がそれぞれ B_1, B_2, \ldots, B_N であるとき、「舞踏会全体の楽しさ」はそれらのビットごとの排他的論理和である B_1 \oplus B_2 \oplus \cdots \oplus B_N です。

「 2N 人の参加者が N 個の 2 人組に分かれる方法」を自由に選べるとき、「舞踏会全体の楽しさ」としてあり得る最大値を出力してください。

制約

1 \leq N \leq 8
0 \leq A_{i, j} < 2^{30}
入力はすべて整数

入力

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

N
A_{1, 2} A_{1, 3} A_{1, 4} \cdots A_{1, 2N}
A_{2, 3} A_{2, 4} \cdots A_{2, 2N}
A_{3, 4} \cdots A_{3, 2N}
\vdots
A_{2N-1, 2N}

出力

舞踏会全体の楽しさとしてあり得る最大値を出力せよ。

入力例 1

出力例 1

人 i と人 j からなる 2 人組を \lbrace i, j\rbrace で表します。 4 人が 2 個の 2 人組にわかれる方法は下記の 3 通りです。

\lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace という 2 組にわかれる。このとき、舞踏会全体の楽しさは A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6 です。
\lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace という 2 組にわかれる。このとき、舞踏会全体の楽しさは A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3 です。
\lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace という 2 組にわかれる。このとき、舞踏会全体の楽しさは A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4 です。

よって、舞踏会全体の楽しさとしてあり得る最大値は 6 です。

入力例 2

1
5

出力例 2

人 1 と人 2 からなる 2 人組のみが作られ、このときの舞踏会全体の楽しさは 5 です。

入力例 3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

出力例 3

1073289207

Score : 400 points

Problem Statement

2N people numbered 1, 2, \ldots, 2N attend a ball. They will group into N pairs and have a dance.

If Person i and Person j pair up, where i is smaller than j, the affinity of that pair is A_{i, j}.
If the N pairs have the affinity of B_1, B_2, \ldots, B_N, the total fun of the ball is the bitwise XOR of them: B_1 \oplus B_2 \oplus \cdots \oplus B_N.

Print the maximum possible total fun of the ball when the 2N people can freely group into N pairs.

Constraints

1 \leq N \leq 8
0 \leq A_{i, j} < 2^{30}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_{1, 2} A_{1, 3} A_{1, 4} \cdots A_{1, 2N}
A_{2, 3} A_{2, 4} \cdots A_{2, 2N}
A_{3, 4} \cdots A_{3, 2N}
\vdots
A_{2N-1, 2N}

Output

Print the maximum possible total fun of the ball.

Sample Input 1

Sample Output 1

Let \lbrace i, j\rbrace denote a pair of Person i and Person j. There are three ways for the four people to group into two pairs, as follows.

Group into \lbrace 1, 2\rbrace, \lbrace 3, 4\rbrace. The total fun of the ball here is A_{1, 2} \oplus A_{3, 4} = 4 \oplus 2 = 6.
Group into \lbrace 1, 3\rbrace, \lbrace 2, 4\rbrace. The total fun of the ball here is A_{1, 3} \oplus A_{2, 4} = 0 \oplus 3 = 3.
Group into \lbrace 1, 4\rbrace, \lbrace 2, 3\rbrace. The total fun of the ball here is A_{1, 4} \oplus A_{2, 3} = 1 \oplus 5 = 4.

Therefore, the maximum possible total fun of the ball is 6.

Sample Input 2

1
5

Sample Output 2

There will be just a pair of Person 1 and Person 2, where the total fun of the ball is 5.

Sample Input 3

5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

Sample Output 3

1073289207

H - Transition Game

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。ここで、各 A_i (1\leq i\leq N) は 1\leq A_i \leq N をみたします。

高橋君と青木君が N 回ゲームを行います。i=1,2,\ldots,N 回目のゲームは次のようにして行われます。

青木君が正整数 K_i を指定する。
青木君の指定した K_i を聞いた後、高橋君は 1 以上 N 以下の整数 S_i を選び、黒板に書く。
その後、 K_i 回次の操作を繰り返す。
- 黒板に x が書かれているとき、それを消し、A_x を新しく書く。

K_i 回の操作の後で黒板に書かれている整数が i ならば i 回目のゲームは高橋君の勝ち、そうでないならば青木君の勝ちとなります。
ここで、K_i,S_i は i=1,2,\ldots,N に対して独立に選ぶ事ができます。

両者が、自身が勝つために最善の行動をとったとき、N 回のゲームのうち高橋君が勝つ回数を求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq A_i\leq N
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

両者が最善の行動をとったとき、N 回のゲームのうち高橋君が勝つ回数を出力せよ。

入力例 1

3
2 2 3

出力例 1

1 回目のゲームにおいて、青木君が K_1=2 を指定したとき、高橋君は S_1 として、1,2,3 のいずれを選んでも勝つことはできません。

例えば、高橋君が最初に黒板に S_1=1 と書いたとすると、2 回の操作で黒板に書かれている数は順に 1\to 2(=A_1) 、2\to 2(=A_2) と変化し、
最終的に黒板に書かれている数は 2(\neq 1) であるため、青木君の勝ちとなります。

一方、2,3 回目のゲームにおいては、青木君の指定した K_i の値によらず、高橋君はそれぞれ 2,3 を最初に黒板に書くことで勝つ事ができます。

よって、両者が、自分が勝つために最善の行動をとったとき、高橋君が勝つゲームは 2,3 回目の 2 回であるため、2 を出力します。

入力例 2

2
2 1

出力例 2

1 回目のゲームにおいて、高橋君は、青木君が指定した K_1 が奇数のときは 2、偶数のときは 1 を最初に黒板に書く事で勝つ事ができます。

同様に 2 回目のゲームにおいても勝つ方法が存在するため、1,2 回目のゲームのいずれでも高橋君は勝利する事ができ、2 が答えとなります。

Score : 500 points

Problem Statement

You are given a sequence of N numbers: A=(A_1,A_2,\ldots,A_N). Here, each A_i (1\leq i\leq N) satisfies 1\leq A_i \leq N.

Takahashi and Aoki will play N rounds of a game. For each i=1,2,\ldots,N, the i-th game will be played as follows.

Aoki specifies a positive integer K_i.
After knowing K_i Aoki has specified, Takahashi chooses an integer S_i between 1 and N, inclusive, and writes it on a blackboard.
Repeat the following K_i times.
- Replace the integer x written on the blackboard with A_x.

If i is written on the blackboard after the K_i iterations, Takahashi wins the i-th round; otherwise, Aoki wins.
Here, K_i and S_i can be chosen independently for each i=1,2,\ldots,N.

Find the number of rounds Takahashi wins if both players play optimally to win.

Constraints

1\leq N\leq 2\times 10^5
1\leq A_i\leq N
All values in the input are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Find the number of rounds Takahashi wins if both players play optimally to win.

Sample Input 1

3
2 2 3

Sample Output 1

In the first round, if Aoki specifies K_1=2, Takahashi cannot win whichever option he chooses for S_1: 1, 2, or 3.

For example, if Takahashi writes S_1=1 on the initial blackboard, the two operations will change this number as follows: 1\to 2(=A_1), 2\to 2(=A_2). The final number on the blackboard will be 2(\neq 1), so Aoki wins.

On the other hand, in the second and third rounds, Takahashi can win by writing 2 and 3, respectively, on the initial blackboard, whatever value Aoki specifies as K_i.

Therefore, if both players play optimally to win, Takashi wins two rounds: the second and the third. Thus, you should print 2.

Sample Input 2

2
2 1

Sample Output 2

In the first round, Takahashi can win by writing 2 on the initial blackboard if K_1 specified by Aoki is odd, and 1 if it is even.

Similarly, there is a way for Takahashi to win the second round. Thus, Takahashi can win both rounds: the answer is 2.

I - Fishing

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

数直線上を N 匹の魚が泳いでいます。

魚 i の重さは W_i であり、時刻 0 に座標 X_i にいて、正方向に速さ V_i で移動しています。

高橋君は 0 以上の実数 t を自由に選び、時刻 t に一度だけ以下の行動を行います。
行動：実数 x を自由に選ぶ。現在の座標が x 以上 x+A 以下である魚を全て捕まえる。

捕まえることができる魚の重さの合計の最大値を求めてください。

制約

1 \leq N \leq 2000
1 \leq A \leq 10^4
1 \leq W_i\leq 10^4
0 \leq X_i\leq 10^4
1 \leq V_i\leq 10^4
入力は全て整数

入力

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

N A
W_1 X_1 V_1
W_2 X_2 V_2
\vdots
W_N X_N V_N

出力

答えを出力せよ。

入力例 1

出力例 1

時刻 0.25 に魚 1,2,3 はそれぞれ座標 25, 17.5, 22.5 にいます。よって、この時刻に x=16 として行動すると全ての魚を捕まえることができます。

入力例 2

3 10
100 100 100
1 10 30
10 20 10

出力例 2

時刻 0 に x=100 として行動するのが最適解の一つです。

入力例 3

4 10
1000 100 10
100 99 1
10 0 100
1 1 1

出力例 3

時刻 1 に x=100 として行動するのが最適解の一つです。

Score : 500 points

Problem Statement

On a number line, there are N fish swimming.

Fish i, which has a weight of W_i, is at the coordinate X_i at time 0 and moves at a speed of V_i in the positive direction.

Takahashi will choose an arbitrary real number t greater than or equal to 0 and do the following action at time t just once.
Action: Choose an arbitrary real number x. Catch all fish whose coordinates are between x and x+A, inclusive.

Find the maximum total weight of fish that he can catch.

Constraints

1 \leq N \leq 2000
1 \leq A \leq 10^4
1 \leq W_i\leq 10^4
0 \leq X_i\leq 10^4
1 \leq V_i\leq 10^4
All values in the input are integers.

Input

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

N A
W_1 X_1 V_1
W_2 X_2 V_2
\vdots
W_N X_N V_N

Output

Print the answer.

Sample Input 1

Sample Output 1

At time 0.25, fish 1, 2, and 3 are at the coordinates 25, 17.5, and 22.5, respectively. Thus, the action done at this time with x=16 catches all the fish.

Sample Input 2

3 10
100 100 100
1 10 30
10 20 10

Sample Output 2

One optimal choice is to do the action at time 0 with x=100.

Sample Input 3

4 10
1000 100 10
100 99 1
10 0 100
1 1 1

Sample Output 3

One optimal choice is to do the action at time 1 with x=100.