AtCoder Daily Training HARD 2024/03/21 18:30start

E - ABC conjecture

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

配点 : 300 点

問題文

正の整数 N が与えられます。

A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。

制約

1 \leq N \leq 10^{11}
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

5745290566750

Score : 300 points

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

1 \leq N \leq 10^{11}
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

Sample Output 2

Sample Input 3

100000000000

Sample Output 3

5745290566750

F - String Delimiter

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

配点 : 300 点

問題文

英小文字、,、" からなる長さ N の文字列 S が与えられます。S に含まれる " の個数は偶数であることが保証されています。

S に含まれる " の個数を 2K 個とすると、各 i=1,2,\ldots,K について 2i-1 番目の " から 2i 番目の " までの文字のことを 括られた文字 と呼びます。

あなたの仕事は、 S に含まれる , のうち、括られた文字 でないもの を . で置き換えて得られる文字列を答えることです。

制約

N は 1 以上 2\times 10^5 以下の整数
S は英小文字、,、" からなる長さ N の文字列
S に含まれる " の個数は偶数

入力

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

N
S

出力

答えを出力せよ。

入力例 1

8
"a,b"c,d

出力例 1

"a,b"c.d

S のうち "a,b" が括られた文字であり、c,d は括られた文字ではありません。

S に含まれる , のうち、括られた文字でないのは S の左から 7 番目の文字なので、7 番目の文字を . で置き換えたものが答えとなります。

入力例 2

5
,,,,,

出力例 2

.....

入力例 3

20
a,"t,"c,"o,"d,"e,"r,

出力例 3

a."t,"c."o,"d."e,"r.

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

N is an integer between 1 and 2\times 10^5, inclusive.
S is a string of length N consisting of lowercase English letters, ,, and ".
S contains an even number of ".

Input

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

N
S

Output

Print the answer.

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

G - Snuke Panic (1D)

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

配点 : 400 点

問題文

高橋君はすぬけ君たちを捕まえようとしています。

数直線上の座標 0,1,2,3,4 の 5 箇所に穴があり、すぬけ君たちの巣につながっています。

これから N 匹のすぬけ君が穴から出てきます。i 番目のすぬけ君は時刻 T_i に座標 X_i の穴から出てきて、大きさは A_i であることがわかっています。

高橋君は時刻 0 に座標 0 におり、数直線上を単位時間あたり 1 以下の速さで移動することができます。
すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。

高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。

制約

1 \leq N \leq 10^5
0 < T_1 < T_2 < \ldots < T_N \leq 10^5
0 \leq X_i \leq 4
1 \leq A_i \leq 10^9
入力に含まれる値は全て整数である

入力

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

N
T_1 X_1 A_1
T_2 X_2 A_2
\vdots
T_N X_N A_N

出力

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

入力例 1

出力例 1

次のように行動するのが最適です。

座標 0 で待機し、時刻 1 に 1 番目のすぬけ君を捕まえる
座標 4 へ移動し、時刻 5 に 3 番目のすぬけ君を捕まえる

1 番目と 2 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。

入力例 2

出力例 2

高橋君はすぬけ君を 1 匹も捕まえることができません。

入力例 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

出力例 3

2978279323

Score : 400 points

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

1 \leq N \leq 10^5
0 < T_1 < T_2 < \ldots < T_N \leq 10^5
0 \leq X_i \leq 4
1 \leq A_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
T_1 X_1 A_1
T_2 X_2 A_2
\vdots
T_N X_N A_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The optimal strategy is as follows.

Wait at coordinate 0 to catch the first Snuke at time 1.
Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

Sample Output 2

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323

H - Digit Sum Divisible

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

配点 : 525 点

問題文

正整数 n の桁和を、n を 10 進法で表したときの各桁の和として定義します。例えば 2024 の桁和は 2+0+2+4=8 です。
正整数 n が n の桁和で割り切れる時、n を 良い整数 と呼びます。例えば 2024 はその桁和である 8 で割り切れるので良い整数です。
正整数 N が与えられます。N 以下の良い整数は全部で何個ありますか？

制約

1 \leq N \leq 10^{14}
N は整数

入力

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

出力

N 以下の良い整数の個数を出力せよ。

入力例 1

出力例 1

20 以下の良い整数は 1,2,3,4,5,6,7,8,9,10,12,18,20 の 13 個です。

入力例 2

出力例 2

入力例 3

9876543210

出力例 3

547452239

Score: 525 points

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits in the decimal notation of n. For example, the digit sum of 2024 is 2+0+2+4=8.
A positive integer n is called a good integer when n is divisible by its digit sum. For example, 2024 is a good integer because it is divisible by its digit sum of 8.
You are given a positive integer N. How many good integers are less than or equal to N?

Constraints

1 \leq N \leq 10^{14}
N is an integer.

Input

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

Output

Print the number of good integers less than or equal to N.

Sample Input 1

Sample Output 1

There are 13 good integers less than or equal to 20: 1,2,3,4,5,6,7,8,9,10,12,18,20.

Sample Input 2

Sample Output 2

Sample Input 3

9876543210

Sample Output 3

547452239

I - Stamp Game

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

配点 : 500 点

問題文

縦 H 行、横 W 列のマス目があります。上から i 行目、左から j 列目のマスをマス (i, j) と呼びます。
1 \leq i \leq H かつ 1 \leq j \leq W を満たす整数の組 (i, j) それぞれについて、マス (i, j) には正整数 A_{i, j} が書かれています。また、すべてのマスは白色に塗られています。

高橋君は、縦 h_1 行、横 w_1 列の長方形の黒いスタンプを持っており、青木君は、縦 h_2 行、横 w_2 列の長方形の白いスタンプを持っています。
2 人はこれらのスタンプとマス目を使って対戦ゲームをします。

まず高橋君が、持っている黒いスタンプを 1 回使って、マス目の縦 h_1 行、横 w_1 列の長方形領域を黒色に塗りつぶします。
すなわち、1 \leq i \leq H - h_1 + 1 かつ 1 \leq j \leq W - w_1 + 1 を満たす整数の組 (i, j) を一つ選び、 i \leq r \leq i + h_1 - 1 かつ j \leq c \leq j + w_1 - 1 を満たすすべてのマス (r, c) を黒色に塗りつぶします。

次に青木君が、持っている白いスタンプを 1 回使って、マス目の縦 h_2 行、横 w_2 列の長方形領域を白色に塗りつぶします。
すなわち、1 \leq i \leq H - h_2 + 1 かつ 1 \leq j \leq W - w_2 + 1 を満たす整数の組 (i, j) を一つ選び、 i \leq r \leq i + h_2 - 1 かつ j \leq c \leq j + w_2 - 1 を満たすすべてのマス (r, c) を白色に塗りつぶします。
このとき、青木君が白色に塗るマスがすでに高橋君によって黒色に塗られていた場合は、そのマスの色は白で上書きされます。

上記の通りに高橋君と青木君がスタンプを 1 回ずつ使った後の、黒色に塗られたマスに書かれた整数の合計を、ゲームの「スコア」とします。高橋君はスコアが出来るだけ大きくなるように、青木君はスコアが出来るだけ小さくなるように、それぞれ最適な戦略をとります。ゲームのスコアがいくらになるかを求めて下さい。

制約

2 \leq H, W \leq 1000
1 \leq h_1, h_2 \leq H
1 \leq w_1, w_2 \leq W
1 \leq A_{i, j} \leq 10^9
入力はすべて整数

入力

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

H W h_1 w_1 h_2 w_2
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

高橋君はスコアが出来るだけ大きくなるように、青木君はスコアが出来るだけ小さくなるように、それぞれ最適な戦略をとるときの、ゲームのスコアを出力せよ。

入力例 1

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

出力例 1

ゲームは以下の通りに進行します。

はじめ、すべてのマスは白色で塗られています。
まず高橋君が、持っている縦 2 行横 3 列の黒いスタンプを使って、マス (2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4) の 6 つのマスを黒色で塗りつぶします。
次に青木君が、持っている縦 3 行横 1 列の白いスタンプを使って、マス (1, 4), (2, 4), (3, 4) を白色で塗りつぶします。
最終的に黒色で塗られているマスは、マス (2, 2), (2, 3), (3, 2), (3, 3) の 4 つであるため、ゲームのスコアは 9 + 2 + 3 + 5 = 19 です。

入力例 2

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

出力例 2

青木君がスタンプを使った後、すべてのマスは白色であり、ゲームのスコアは 0 となります。

入力例 3

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19

出力例 3

Score : 500 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
For each pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, (i, j) contains a positive integer A_{i,j}. Additionally, every square is painted white.

Takahashi has a rectangular black stamp that can cover h_1 rows and w_1 columns, and Aoki has a rectangular white stamp that can cover h_2 rows and w_2 columns. Using these stamps and the grid, they will play a game against each other.

First, Takahashi presses his black stamp to paint a rectangular region with h_1 rows and w_1 columns black.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_1 + 1 and 1 \leq j \leq W - w_1 + 1, and paints black every square (r, c) such that i \leq r \leq i + h_1 - 1 and j \leq c \leq j + w_1 - 1.

Second, Aoki presses his white stamp to paint a rectangular region with h_2 rows and w_2 columns white.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_2 + 1 and 1 \leq j \leq W - w_2 + 1, and paints white every square (r, c) such that i \leq r \leq i + h_2 - 1 and j \leq c \leq j + w_2 - 1.
If some of these squares are already painted black by Takahashi, they will also become white.

The game's score is defined as the sum of the integers written on the squares painted black after Takahashi and Aoki press their stamps as described above. Takahashi follows the optimal strategy to make the score as large as possible, while Aoki follows the optimal strategy to make the score as small as possible. What will the game's score be?

Constraints

2 \leq H, W \leq 1000
1 \leq h_1, h_2 \leq H
1 \leq w_1, w_2 \leq W
1 \leq A_{i, j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W h_1 w_1 h_2 w_2
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

Output

Print the game's score when Takahashi follows the optimal strategy to make the score as large as possible and Aoki follows the optimal strategy to make the score as small as possible.

Sample Input 1

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

Sample Output 1

The game will go as follows.

Initially, all squares are painted white.
First, Takahashi presses his 2 \times 3 black stamp to paint the following six squares black: (2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4).
Second, Aoki presses his 3 \times 1 white stamp to paint the following three squares white: (1, 4), (2, 4), (3, 4).
Eventually, the following four squares are painted black: (2, 2), (2, 3), (3, 2), (3, 3), for a score of 9 + 2 + 3 + 5 = 19.

Sample Input 2

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

Sample Output 2

After Aoki presses his stamp, all squares will be white, for a score of 0.

Sample Input 3

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19