AtCoder Beginner Contest 297

A - Double Click

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。

高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。

高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。

制約

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
入力はすべて整数

入力

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

N D
T_1 T_2 \dots T_N

出力

高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。

入力例 1

4 500
300 900 1300 1700

出力例 1

高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。

時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。

入力例 2

5 99
100 200 300 400 500

出力例 2

-1

高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。

入力例 3

4 500
100 600 1100 1600

出力例 3

高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。

Score : 100 points

Problem Statement

Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.

If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.

What time was a double click fired for the first time? If no double click was fired, print -1 instead.

Constraints

1 \le N \le 100
1 \le D \le 10^9
1 \le T_i \le 10^9(1 \le i \le N)
T_i < T_{i+1}(1 \le i \le N-1)
All values in the input are integers.

Input

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

N D
T_1 T_2 \dots T_N

Output

If at least one double click was fired, print the time of the first such event; otherwise, print -1.

Sample Input 1

4 500
300 900 1300 1700

Sample Output 1

Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.

A double click had not been fired before time 1300, so 1300 should be printed.

Sample Input 2

5 99
100 200 300 400 500

Sample Output 2

-1

No double click was fired, so print -1.

Sample Input 3

4 500
100 600 1100 1600

Sample Output 3

If multiple double clicks were fired, be sure to print only the first such event.

B - chess960

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

高橋君は chess960 と呼ばれるゲームで遊んでいます。高橋君はランダムに決めた初期配置が chess960 の条件を満たすか確認するプログラムを書くことにしました。

長さ 8 の文字列 S が与えられます。S には K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれます。 S が以下の条件を全て満たしているか判定してください。

S において左から x,y\ (x < y) 文字目が B であるとする。このとき x と y の偶奇が異なる。
K は 2 つの R の間にある。より形式的には、S において左から x,y\ (x < y) 文字目が R であり、 z 文字目が K であるとする。このとき、 x< z < y が成り立つ。

制約

S は長さ 8 の文字列であり、K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれる。

入力

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

出力

S が条件を満たす場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

RNBQKBNR

出力例 1

Yes

B は左から 3 番目、6 番目にあり、3 と 6 は偶奇が異なります。また、K は 2 つの R の間にあります。よって条件を満たします。

入力例 2

KRRBBNNQ

出力例 2

No

K は 2 つの R の間にありません。

入力例 3

BRKRBQNN

出力例 3

No

Score : 200 points

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.
K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Input

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

Output

Print Yes if S satisfies the conditions; print No otherwise.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

C - PC on the Table

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋君は部屋に PC を沢山置こうとしています。そこで最大何台の PC を部屋に置けるか調べるプログラムを書くことにしました。

H 個の長さ W の ., T からなる文字列 S_1,S_2,\ldots,S_H が与えられます。

高橋君は以下の操作を 0 回以上何回でも行うことができます。

1\leq i \leq H, 1 \leq j \leq W-1 を満たす整数であって、 S_i の j 番目の文字も j+1 番目の文字も T であるようなものを選ぶ。 S_i の j 番目の文字を P で置き換え、S_i の j+1 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を出力してください。

制約

1\leq H \leq 100
2\leq W \leq 100
H と W は整数である
S_i は ., T からなる長さ W の文字列

入力

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

H W 
S_1
S_2
\vdots
S_H

出力

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を改行区切りで出力せよ。

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

入力例 1

2 3
TTT
T.T

出力例 1

PCT
T.T

可能な操作回数の最大値は 1 です。

例えば、 (i,j)=(1,1) として操作を行うと、S_1 が PCT に変化します。

入力例 2

3 5
TTT..
.TTT.
TTTTT

出力例 2

PCT..
.PCT.
PCTPC

Score : 300 points

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

1\leq H \leq 100
2\leq W \leq 100
H and W are integers.
S_i is a string of length W consisting of . and T.

Input

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

H W 
S_1
S_2
\vdots
S_H

Output

Print a sequence of strings, S_1,S_2,\ldots,S_H, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.

If multiple solutions exist, print any of them.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

D - Count Subtractions

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

正整数 A,B が与えられます。

あなたは、A=B になるまで以下の操作を繰り返します。

A,B の大小関係に応じて、次の 2 個のうちどちらかの処理を行う。
- A > B ならば、A を A-B で置き換える。
- A < B ならば、B を B-A で置き換える。

A=B になるまで、操作を何回行うか求めてください。ただし、有限回の操作で A=B になることが保証されます。

制約

1 \le A,B \le 10^{18}
入力はすべて整数

入力

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

A B

出力

答えを出力せよ。

入力例 1

3 8

出力例 1

始め、A=3,B=8 です。操作は以下のように行われます。

A<B であるため、B を B-A=5 で置き換える。A=3,B=5 となる。
A<B であるため、B を B-A=2 で置き換える。A=3,B=2 となる。
A>B であるため、A を A-B=1 で置き換える。A=1,B=2 となる。
A<B であるため、B を B-A=1 で置き換える。A=1,B=1 となる。

よって、操作回数は 4 回です。

入力例 2

1234567890 1234567890

出力例 2

入力が 32bit 整数型に収まらないことがあることに注意してください。

入力例 3

1597 987

出力例 3

Score : 400 points

Problem Statement

You are given positive integers A and B.

You will repeat the following operation until A=B:

compare A and B to perform one of the following two:
- if A > B, replace A with A-B;
- if A < B, replace B with B-A.

How many times will you repeat it until A=B? It is guaranteed that a finite repetition makes A=B.

Constraints

1 \le A,B \le 10^{18}
All values in the input are integers.

Input

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

A B

Output

Print the answer.

Sample Input 1

3 8

Sample Output 1

Initially, A=3 and B=8. You repeat the operation as follows:

A<B, so replace B with B-A=5, making A=3 and B=5.
A<B, so replace B with B-A=2, making A=3 and B=2.
A>B, so replace A with A-B=1, making A=1 and B=2.
A<B, so replace B with B-A=1, making A=1 and B=1.

Thus, you repeat it four times.

Sample Input 2

1234567890 1234567890

Sample Output 2

Note that the input may not fit into a 32-bit integer type.

Sample Input 3

1597 987

Sample Output 3

E - Kth Takoyaki Set

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

AtCoder 王国では、N 種類のたこ焼きが売られています。i 種類目のたこ焼きの値段は A_i 円です。

高橋君は、合計で 1 個以上のたこ焼きを買います。このとき、同じたこ焼きを複数個買うことも許されます。

高橋君が支払う金額としてあり得るもののうち、安い方から K 番目の金額を求めてください。ただし、同じ金額を支払う方法が複数存在する場合は 1 回だけ数えます。

制約

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

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

4 6
20 25 30 100

出力例 1

AtCoder 王国で売られている 4 種類のたこ焼きは、それぞれ 20 円、25 円、30 円、100 円です。

高橋君の支払う金額としてあり得るものは、安い方から 6 個を列挙すると 20 円、25 円、30 円、40 円、45 円、50 円となります。よって、答えは 50 円です。

合計で 1 個以上たこ焼きを買う必要があることに注意してください。

入力例 2

2 10
2 1

出力例 2

同じ金額の買い方が何通りかあっても、重複してカウントしないことに注意してください。

入力例 3

10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

出力例 3

5705443819

Score : 500 points

Problem Statement

In AtCoder Kingdom, N kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the i-th kind is sold for A_i yen.

Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.

Find the K-th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.

Constraints

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

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4 6
20 25 30 100

Sample Output 1

The four kinds of takoyakis sold in AtCoder Kingdom cost 20 yen, 25 yen, 30 yen, and 100 yen.

The six lowest prices that Takahashi may pay are 20 yen, 25 yen, 30 yen, 40 yen, 45 yen, and 50 yen. Thus, the answer is 50.

Note that at least one takoyaki must be bought.

Sample Input 2

2 10
2 1

Sample Output 2

Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.

Sample Input 3

10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

Sample Output 3

5705443819

F - Minimum Bounding Box 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

縦 H 行、横 W 列のグリッドがあります。

このグリッドから一様ランダムに K 個のマスを選びます。選んだマスを全て含むような（グリッドの軸に辺が平行な）最小の長方形に含まれるマスの個数がスコアとなります。

得られるスコアの期待値を \text{mod }998244353 で求めてください。

有理数 \text{mod }998244353 とは

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

1\leq H,W \leq 1000
1\leq K \leq HW
入力はすべて整数

入力

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

H W K

出力

答えを出力せよ。

入力例 1

2 2 2

出力例 1

665496238

マス (1,1) とマス (2,2) が選ばれた場合、またはマス (1,2) とマス (2,1) が選ばれた場合の 2 通りではスコアは 4 となります。また、それ以外の 4 通りではスコアは 2 となります。

よって得られるスコアの期待値は \frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3} であり、665496238 \times 3 \equiv 8\pmod{998244353} なので 665496238 が答えとなります。

入力例 2

10 10 1

出力例 2

入力例 3

314 159 2653

出力例 3

639716353

Score : 500 points

Problem Statement

We have a grid with H rows and W columns.

We choose K cells in this grid uniformly at random. The score is the number of cells in the minimum rectangle (whose edges are parallel to the axes of the grid) that contains all of the chosen cells.

Find the expected score modulo 998244353.

What is rational number modulo 998244353?

We can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, when the value is represented as \frac{P}{Q} by two coprime integers P and Q, we can prove that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find such R.

Constraints

1\leq H,W \leq 1000
1\leq K \leq HW
All values in the input are integers.

Input

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

H W K

Output

Print the answer.

Sample Input 1

2 2 2

Sample Output 1

665496238

The score equals 4 in the following two cases: if cells (1,1) and (2,2) are chosen, or cells (1,2) and (2,1) are chosen. The other four cases yield a score of 2.

Thus, the expected score equals \frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}. Since 665496238 \times 3 \equiv 8\pmod{998244353}, you should print 665496238.

Sample Input 2

10 10 1

Sample Output 2

Sample Input 3

314 159 2653

Sample Output 3

639716353

G - Constrained Nim 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 個の石の山があり、はじめ i 番目の山には石が A_i 個あります。これらの山を使って先手太郎君と後手次郎君でゲームをします。

先手太郎君と後手次郎君は、先手太郎君が先手で交互に以下の操作を行います。

石の山を一つ選び、そこから L 個以上 R 個以下の石を取り除く。

操作が行えなくなった方が負けで、負けなかった方が勝ちです。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定してください。

制約

1\leq N \leq 2\times 10^5
1\leq L \leq R \leq 10^9
1\leq A_i \leq 10^9
入力はすべて整数である。

入力

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

N L R 
A_1 A_2 \ldots A_N

出力

先手太郎君が勝つ場合 First を、後手次郎君が勝つ場合 Second を出力せよ。

入力例 1

3 1 2
2 3 3

出力例 1

First

先手太郎君が最初に 1 番目の山の石を 2 個取り除くことで、必ず勝つことができます。

入力例 2

5 1 1
3 1 4 1 5

出力例 2

Second

入力例 3

7 3 14
10 20 30 40 50 60 70

出力例 3

First

Score : 600 points

Problem Statement

There are N piles of stones. Initially, the i-th pile contains A_i stones. With these piles, Taro the First and Jiro the Second play a game against each other.

Taro the First and Jiro the Second make the following move alternately, with Taro the First going first:

Choose a pile of stones, and remove between L and R stones (inclusive) from it.

A player who is unable to make a move loses, and the other player wins. Who wins if they optimally play to win?

Constraints

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

Input

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

N L R 
A_1 A_2 \ldots A_N

Output

Print First if Taro the First wins; print Second if Jiro the Second wins.

Sample Input 1

3 1 2
2 3 3

Sample Output 1

First

Taro the First can always win by removing two stones from the first pile in his first move.

Sample Input 2

5 1 1
3 1 4 1 5

Sample Output 2

Second

Sample Input 3

7 3 14
10 20 30 40 50 60 70

Sample Output 3

First

Ex - Diff Adjacent

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

正整数列のうち、全ての隣接している 2 項が異なるものを素晴らしい整数列と定めます。

要素の総和が N の素晴らしい整数列全てに対する長さの総和を 998244353 で割ったあまりを求めてください。

制約

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

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

要素の総和が 4 の素晴らしい整数列は、(4),(1,3),(3,1),(1,2,1) の 4 個です。なので、答えはこれらの長さの総和の 1+2+2+3=8 です。

(2,2) や (1,1,2) は総和が 4 ですが、両方 1 項目と 2 項目が等しいため条件を満たしません。

入力例 2

出力例 2

475867236

入力例 3

出力例 3

771773807

Score : 600 points

Problem Statement

A positive-integer sequence is said to be splendid if no two adjacent elements are equal.

Find the sum, modulo 998244353, of the lengths of all splendid sequences whose elements have a sum of N.

Constraints

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

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

There are four splendid sequences whose sum is 4: (4),(1,3),(3,1),(1,2,1). Thus, the answer is the sum of their lengths: 1+2+2+3=8.

(2,2) and (1,1,2) also have a sum of 4 but ineligible because their 1-st and 2-nd elements are the same.

Sample Input 2

Sample Output 2

475867236

Sample Input 3

Sample Output 3

771773807