AtCoder Daily Training HARD 2024/03/20 18:00start

E - Long Sequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の正整数のみからなる数列 A=(A_1,\dots,A_N) があります。
A を 10^{100} 回連結した数列を数列 B とします。

B の項を前から順に足したとき、和が初めて X を超えるのは何項目まで足したときですか？
すなわち、以下の式を満たす最小の整数 k を求めてください。

\displaystyle{\sum_{i=1}^{k} B_i \gt X}

制約

1 \leq N \leq 10^5
1 \leq A_i \leq 10^9
1 \leq X \leq 10^{18}
入力は全て整数

入力

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

N
A_1 \ldots A_N
X

出力

答えを出力せよ。

入力例 1

3
3 5 2
26

出力例 1

B=(3,5,2,3,5,2,3,5,2,\dots) です。
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} であり、k が 7 以下のとき条件を満たさないので、8 が答えです。

入力例 2

4
12 34 56 78
1000

出力例 2

Score : 300 points

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

1 \leq N \leq 10^5
1 \leq A_i \leq 10^9
1 \leq X \leq 10^{18}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N
X

Output

Print the answer.

Sample Input 1

3
3 5 2
26

Sample Output 1

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

F - Reversible

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

ボールがいくつか刺さった棒が N 本あり、各ボールには英小文字が 1 個書かれています。

i = 1, 2, \ldots, N について、i 番目の棒に刺さった各ボールの英小文字は、文字列 S_i によって表されます。具体的には、i 番目の棒には文字列 S_i の長さ |S_i| に等しい個数のボールが刺さっており、刺さっているボールの英小文字を、棒のある端から順に並べたものは文字列 S_i と等しいです。

2 つの棒は、一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列と、もう一方の棒に刺さっているボールの英小文字をどちらかの端から並べた列が一致するとき、同じ棒とみなされます。より形式的には、1 以上 N 以下の整数 i, j について、i 本目の棒と j 本目の棒は、S_i が S_j と一致するか、S_i が S_j を前後反転したものと一致するとき、かつそのときに限り、同じとみなされます。

N 本の棒の中に、何種類の異なる棒があるかを出力してください。

制約

N は整数
2 \leq N \leq 2 \times 10^5
S_i は英小文字のみからなる文字列
|S_i| \geq 1
\sum_{i = 1}^N |S_i| \leq 2 \times 10^5

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

6
a
abc
de
cba
de
abc

出力例 1

S_2 = abc が S_4 = cba を前後反転したものと一致するため、2 番目の棒と 4 番目の棒は同じとみなされます。
S_2 = abc が S_6 = abc と一致するため、2 番目の棒と 6 番目の棒は同じとみなされます。
S_3 = de が S_5 = de と一致するため、3 番目の棒と 5 番目の棒は同じとみなされます。

よって、6 本の棒の中に、1 本目の棒、2 本目の棒（ 4, 6 本目の棒と同じ）、3 本目の棒（ 5 本目の棒と同じ）の 3 種類の異なる棒があります。

Score : 300 points

Problem Statement

There are N sticks with several balls stuck onto them. Each ball has a lowercase English letter written on it.

For each i = 1, 2, \ldots, N, the letters written on the balls stuck onto the i-th stick are represented by a string S_i. Specifically, the number of balls stuck onto the i-th stick is the length |S_i| of the string S_i, and S_i is the sequence of letters on the balls starting from one end of the stick.

Two sticks are considered the same when the sequence of letters on the balls starting from one end of one stick is equal to the sequence of letters starting from one end of the other stick. More formally, for integers i and j between 1 and N, inclusive, the i-th and j-th sticks are considered the same if and only if S_i equals S_j or its reversal.

Print the number of different sticks among the N sticks.

Constraints

N is an integer.
2 \leq N \leq 2 \times 10^5
S_i is a string consisting of lowercase English letters.
|S_i| \geq 1
\sum_{i = 1}^N |S_i| \leq 2 \times 10^5

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

6
a
abc
de
cba
de
abc

Sample Output 1

S_2 = abc equals the reversal of S_4 = cba, so the second and fourth sticks are considered the same.
S_2 = abc equals S_6 = abc, so the second and sixth sticks are considered the same.
S_3 = de equals S_5 = de, so the third and fifth sticks are considered the same.

Therefore, there are three different sticks among the six: the first, second (same as the fourth and sixth), and third (same as the fifth).

G - Do use hexagon grid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

以下のような、無限に広い六角形のグリッドがあります。最初、全てのマスは白です。

ある六角形のマスは 2 つの整数 i,j を用いて (i,j) と表されます。
マス (i,j) は以下の 6 つのマスと隣接します。

(i-1,j-1)
(i-1,j)
(i,j-1)
(i,j+1)
(i+1,j)
(i+1,j+1)

高橋くんは、 N 個のマス (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) を黒く塗りました。
黒いマスがいくつの連結成分をなすか求めてください。
ただし、ある 2 つの黒いマスが同じ連結成分に属するとは、この 2 つの黒いマスの間をいくつかの隣接する黒いマスを辿って移動できることを指します。

制約

入力は全て整数
1 \le N \le 1000
|X_i|,|Y_i| \le 1000
(X_i,Y_i) は相異なる

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

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

入力例 1

出力例 1

高橋くんがマスを黒く塗った後、グリッドは下図の状態になります。

黒いマスがなす連結成分は以下の 3 つです。

(-1,-1)
(1,0),(2,0)
(0,1),(0,2),(1,2)

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

We have an infinite hexagonal grid shown below. Initially, all squares are white.

A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:

(i-1,j-1)
(i-1,j)
(i,j-1)
(i,j+1)
(i+1,j)
(i+1,j+1)

Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.

Constraints

All values in the input are integers.
1 \le N \le 1000
|X_i|,|Y_i| \le 1000
The pairs (X_i,Y_i) are distinct.

Input

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

After Takahashi paints cells black, the grid looks as shown below.

The black squares form the following three connected components:

(-1,-1)
(1,0),(2,0)
(0,1),(0,2),(1,2)

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

H - Maximize Rating

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

高橋君は N 回コンテストに参加し、i 回目に参加したコンテストにおいてパフォーマンス P_i を獲得しました。
高橋君はこの中から (1 つ以上) いくつかのコンテストを選び、それらの結果から計算される高橋君のレートを最大にしたいと考えています。

コンテストをうまく選んだとき、高橋君のレートとしてあり得る最大の値を求めてください。

ただし、高橋君のレート R は、高橋君の選んだコンテストの数が k 個であり、選んだコンテストにおけるパフォーマンスが 参加した順に それぞれ (Q_1,Q_2,\ldots,Q_k) であるとき、

\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}

によって計算されます。

制約

1\leq N\leq 5000
1\leq P_i\leq 5000
入力はすべて整数

入力

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

N
P_1 P_2 \ldots P_N

出力

高橋君のレートとしてあり得る最大の値を出力せよ。
出力は、真の値との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。

入力例 1

3
1000 600 1200

出力例 1

256.735020470879931

高橋君が 1 回目と 3 回目のコンテストを選んだ時、レートは、

\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502...

となり、この時レートが最大となります。

入力例 2

3
600 1000 1200

出力例 2

261.423219407873376

1,2,3 回目のコンテストすべてを選んだとき、レートが最大となります。

入力例 3

1
100

出力例 3

-1100.000000000000000

レートは負になることもあります。

Score : 475 points

Problem Statement

Takahashi participated in N contests and earned a performance P_i in the i-th contest.
He wants to choose some (at least one) contests from these and maximize his rating calculated from the results of those contests.

Find the maximum possible rating he can achieve by optimally choosing the contests.

Here, Takahashi's rating R is calculated as the following, where k is the number of chosen contests and (Q_1, Q_2, \ldots, Q_k) are the performances in the chosen contests in the order he participated:

\displaystyle R=\frac{\sum_{i=1}^k (0.9)^{k-i}Q_i}{\sum_{i=1}^k (0.9)^{k-i}}-\frac{1200}{\sqrt{k}}.

Constraints

1\leq N\leq 5000
1\leq P_i\leq 5000
All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Print the maximum possible rating that Takahashi can achieve.
Your output will be considered correct if the absolute or relative error from the true value is at most 10^{-6}.

Sample Input 1

3
1000 600 1200

Sample Output 1

256.735020470879931

If Takahashi chooses the first and third contests, his rating will be:

\displaystyle R=\frac{0.9\times 1000+ 1.0\times 1200}{0.9+1.0}-\frac{1200}{\sqrt{2}}=256.73502....

This is the maximum possible rating.

Sample Input 2

3
600 1000 1200

Sample Output 2

261.423219407873376

The rating is maximized when all the first, second, and third contests are selected.

Sample Input 3

1
100

Sample Output 3

-1100.000000000000000

The rating can also be negative.

I - Minimum Bounding Box 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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