AtCoder Daily Training MEDIUM 2025/06/26 16:30start

C - Four Hidden

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

英小文字と ? からなる文字列 T と、英小文字のみからなる文字列 U が与えられます。

T は、英小文字のみからなる文字列 S のちょうど 4 文字を ? で置き換えることで得られた文字列です。

S が U を連続部分文字列として含んでいた可能性があるかどうか判定してください。

制約

T は長さ 4 以上 10 以下の英小文字と ? からなる文字列
T にはちょうど 4 つの ? が含まれる
U は長さ 1 以上 |T| 以下の英小文字からなる文字列

入力

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

T
U

出力

S が U を部分文字列として含んでいた可能性があるならば Yes を、そうでないならば No を出力せよ。

入力例 1

tak??a?h?
nashi

出力例 1

Yes

例えば、S が takanashi である場合、これは nashi を連続部分文字列として含みます。

入力例 2

??e??e
snuke

出力例 2

No

? がどのような文字であっても、S は snuke を連続部分文字列として含むことがありません。

入力例 3

????
aoki

出力例 3

Yes

Score : 250 points

Problem Statement

You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.

The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.

Determine whether it is possible that the original string S contained U as a contiguous substring.

Constraints

T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and ?.
T contains exactly four occurrences of ?.
U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.

Input

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

T
U

Output

Print Yes if it is possible that the original string S contained U as a contiguous substring; otherwise, print No.

Sample Input 1

tak??a?h?
nashi

Sample Output 1

Yes

For example, if S is takanashi, it contains nashi as a contiguous substring.

Sample Input 2

??e??e
snuke

Sample Output 2

No

No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.

Sample Input 3

????
aoki

Sample Output 3

Yes

D - Spot the Difference

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

縦 N マス、横 N マスのグリッドが 2 個与えられます。それぞれグリッド A, グリッド B と呼びます。
グリッドの各マスには英小文字が書かれています。
グリッド A の上から i 行目、左から j 列目に書かれている文字は A_{i, j} です。
グリッド B の上から i 行目、左から j 列目に書かれている文字は B_{i, j} です。

2 つのグリッドは 1 ヵ所だけ書かれている文字が異なります。すなわち、A_{i, j} \neq B_{i, j} である N 以下の正整数の組 (i, j) はちょうど 1 個存在します。この (i, j) を求めてください。

制約

1 \leq N \leq 100
A_{i, j}, B_{i, j} は全て英小文字
A_{i, j} \neq B_{i, j} である (i, j) がちょうど 1 個存在する

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

出力

A_{i, j} \neq B_{i, j} である N 以下の正整数の組を (i, j) とする。この時、(i, j) を以下の形式で出力せよ。

i j

入力例 1

3
abc
def
ghi
abc
bef
ghi

出力例 1

2 1

A_{2, 1} = d、B_{2, 1} = b なので A_{2, 1} \neq B_{2, 1} が成り立つため、(i, j) = (2, 1) は問題文の条件を満たします。

入力例 2

1
f
q

出力例 2

1 1

入力例 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

出力例 3

5 9

Score: 150 points

Problem Statement

You are given two grids, each with N rows and N columns, referred to as grid A and grid B.
Each cell in the grids contains a lowercase English letter.
The character at the i-th row and j-th column of grid A is A_{i, j}.
The character at the i-th row and j-th column of grid B is B_{i, j}.

The two grids differ in exactly one cell. That is, there exists exactly one pair (i, j) of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Find this (i, j).

Constraints

1 \leq N \leq 100
A_{i, j} and B_{i, j} are all lowercase English letters.
There exists exactly one pair (i, j) such that A_{i, j} \neq B_{i, j}.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Output

Let (i, j) be the pair of positive integers not greater than N such that A_{i, j} \neq B_{i, j}. Print (i, j) in the following format:

i j

Sample Input 1

3
abc
def
ghi
abc
bef
ghi

Sample Output 1

2 1

From A_{2, 1} = d and B_{2, 1} = b, we have A_{2, 1} \neq B_{2, 1}, so (i, j) = (2, 1) satisfies the condition in the problem statement.

Sample Input 2

1
f
q

Sample Output 2

1 1

Sample Input 3

10
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehfk
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj
eixfumagit
vtophbepfe
pxbfgsqcug
ugpugtsxzq
bvfhxyehok
uqyfwtmglr
jaitenfqiq
acwvufpfvv
jhaddglpva
aacxsyqvoj

Sample Output 3

5 9

E - Avoid Knight Attack

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 N マス、横 N マスの N ^ 2 マスからなるマス目があります。上から i 行目 (1\leq i\leq N) 、左から j 列目 (1\leq j\leq N) のマスをマス (i,j) と呼ぶことにします。

それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。マス目には合計で M 個のコマが置かれており、k 番目 (1\leq k\leq M) のコマはマス (a _ k,b _ k) に置かれています。

あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。

マス (i,j) に置かれているコマは、次のどれかの条件を満たすコマを取ることができます。

マス (i+2,j+1) に置かれている
マス (i+1,j+2) に置かれている
マス (i-1,j+2) に置かれている
マス (i-2,j+1) に置かれている
マス (i-2,j-1) に置かれている
マス (i-1,j-2) に置かれている
マス (i+1,j-2) に置かれている
マス (i+2,j-1) に置かれている

ただし、存在しないマスについての条件は常に満たされないものとします。

たとえば、マス (4,4) に置かれているコマは、以下の図で青く示されたマスに置かれているコマを取ることができます。

あなたがコマを置くことができるマスがいくつあるか求めてください。

制約

1\leq N\leq10 ^ 9
1\leq M\leq2\times10 ^ 5
1\leq a _ k\leq N,1\leq b _ k\leq N\ (1\leq k\leq M)
(a _ k,b _ k)\neq(a _ l,b _ l)\ (1\leq k\lt l\leq M)
入力はすべて整数

入力

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

N M
a _ 1 b _ 1
a _ 2 b _ 2
\vdots
a _ M b _ M

出力

すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。

入力例 1

出力例 1

すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。

よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスは残りの 38 マスです。

入力例 2

1000000000 1
1 1

出力例 2

999999999999999997

10 ^ {18} マスのうち、置くことができないマスはマス (1,1),(2,3),(3,2) の 3 マスのみです。

答えが 2 ^ {32} 以上になる場合があることに注意してください。

入力例 3

出力例 3

Score : 300 points

Problem Statement

There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

Placed on square (i+2,j+1)
Placed on square (i+1,j+2)
Placed on square (i-1,j+2)
Placed on square (i-2,j+1)
Placed on square (i-2,j-1)
Placed on square (i-1,j-2)
Placed on square (i+1,j-2)
Placed on square (i+2,j-1)

Here, conditions involving non-existent squares are considered to never be satisfied.

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

1\leq N\leq10^9
1\leq M\leq2\times10^5
1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
All input values are integers.

Input

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

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

Output

Print the number of empty squares where you can place your piece without it being captured by any existing pieces.

Sample Input 1

Sample Output 1

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining 38 squares.

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999999999999997

Out of 10^{18} squares, only 3 squares cannot be used: squares (1,1), (2,3), and (3,2).

Note that the answer may be 2^{32} or greater.

Sample Input 3

Sample Output 3

F - Triple Attack

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

あなたはゲームをプレイしています。

N 人の敵が一列に並んでおり、前から i 番目の敵の体力は H_i です。

あなたは 0 で初期化された変数 T を使い、全ての敵の体力が 0 以下になるまで次の行動を繰り返します。

T を 1 増やす。その後、体力が 1 以上である最も前の敵を攻撃する。このとき、T が 3 の倍数ならばその敵の体力は 3 減り、そうでないなら 1 減る。

全ての敵の体力が 0 以下になったときの T の値を求めてください。

制約

1 \leq N \leq 2\times 10^5
1 \leq H_i \leq 10^9
入力は全て整数

入力

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

N
H_1 H_2 \ldots H_N

出力

答えを出力せよ。

入力例 1

3
6 2 2

出力例 1

行動は次のように行われます。

T=1 になる。1 番目の敵を攻撃し、その敵の体力は 6-1=5 となる。
T=2 になる。1 番目の敵を攻撃し、その敵の体力は 5-1=4 となる。
T=3 になる。1 番目の敵を攻撃し、その敵の体力は 4-3=1 となる。
T=4 になる。1 番目の敵を攻撃し、その敵の体力は 1-1=0 となる。
T=5 になる。2 番目の敵を攻撃し、その敵の体力は 2-1=1 となる。
T=6 になる。2 番目の敵を攻撃し、その敵の体力は 1-3=-2 となる。
T=7 になる。3 番目の敵を攻撃し、その敵の体力は 2-1=1 となる。
T=8 になる。3 番目の敵を攻撃し、その敵の体力は 1-1=0 となる。

入力例 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

出力例 2

82304529

入力例 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

3000000000

オーバーフローに注意してください。

Score : 300 points

Problem Statement

You are playing a game.

There are N enemies lined up in a row, and the i-th enemy from the front has a health of H_i.

You will repeat the following action until the healths of all enemies become 0 or less, using a variable T initialized to 0.

Increase T by 1. Then, attack the frontmost enemy with health 1 or more. If T is a multiple of 3, the enemy's health decreases by 3; otherwise, it decreases by 1.

Find the value of T when the healths of all enemies become 0 or less.

Constraints

1 \leq N \leq 2\times 10^5
1 \leq H_i \leq 10^9
All input values are integers.

Input

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

N
H_1 H_2 \ldots H_N

Output

Print the answer.

Sample Input 1

3
6 2 2

Sample Output 1

The actions are performed as follows:

T becomes 1. Attack the 1st enemy, and its health becomes 6-1=5.
T becomes 2. Attack the 1st enemy, and its health becomes 5-1=4.
T becomes 3. Attack the 1st enemy, and its health becomes 4-3=1.
T becomes 4. Attack the 1st enemy, and its health becomes 1-1=0.
T becomes 5. Attack the 2nd enemy, and its health becomes 2-1=1.
T becomes 6. Attack the 2nd enemy, and its health becomes 1-3=-2.
T becomes 7. Attack the 3rd enemy, and its health becomes 2-1=1.
T becomes 8. Attack the 3rd enemy, and its health becomes 1-1=0.

Sample Input 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 2

82304529

Sample Input 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Beware of integer overflow.

G - At Most 3 (Contestant ver.)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

整数 W が与えられます。
あなたは以下の条件をすべて満たすようにいくつかのおもりを用意することにしました。

おもりの個数は 1 個以上 300 個以下である。
おもりの重さは 10^6 以下の正整数である。
1 以上 W 以下のすべての正整数は 良い整数 である。ここで、以下の条件を満たす正整数 n を良い整数と呼ぶ。
- 用意したおもりのうち \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。

条件を満たすようなおもりの組を 1 つ出力してください。

制約

1 \leq W \leq 10^6
W は整数

入力

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

出力

N をおもりの個数、A_i を i 番目のおもりの重さとして、以下の形式で出力せよ。答えが複数存在する場合、どれを出力しても正解とみなされる。

N
A_1 A_2 \dots A_N

ただし、N および A_1,A_2,\dots,A_N は以下の条件を満たす必要がある。

1 \leq N \leq 300
1 \leq A_i \leq 10^6

入力例 1

出力例 1

3
1 2 3

上の出力は重さ 1 のおもり、重さ 2 のおもり、重さ 3 のおもりの 3 個のおもりを用意しています。
この出力は条件を満たしています。特に 3 番目の条件について、以下のようにおもりを選ぶことで 1 以上 W 以下の整数すべてが良い整数であることが確認できます。

1 番目のおもりのみを選ぶと、重さの和は 1 になる。
2 番目のおもりのみを選ぶと、重さの和は 2 になる。
3 番目のおもりのみを選ぶと、重さの和は 3 になる。
1 番目と 3 番目のおもりを選ぶと、重さの和は 4 になる。
2 番目と 3 番目のおもりを選ぶと、重さの和は 5 になる。
1 番目、2 番目と 3 番目のおもりを選ぶと、重さの和は 6 になる。

入力例 2

出力例 2

6
2 5 1 2 5 1

同じ重さのおもりを 2 個以上用意しても良いです。

Score : 400 points

Problem Statement

You are given an integer W.
You are going to prepare some weights so that all of the conditions below are satisfied.

The number of weights is between 1 and 300, inclusive.
Each weight has a mass of positive integer not exceeding 10^6.
Every integer between 1 and W, inclusive, is a good integer. Here, a positive integer n is said to be a good integer if the following condition is satisfied:
- We can choose at most 3 different weights from the prepared weights with a total mass of n.

Print a combination of weights that satisfies the conditions.

Constraints

1 \leq W \leq 10^6
W is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print in the following format, where N is the number of weights and A_i is the mass of the i-th weight. If multiple solutions exist, printing any of them is accepted.

N
A_1 A_2 \dots A_N

Here, N and A_1,A_2,\dots,A_N should satisfy the following conditions:

1 \leq N \leq 300
1 \leq A_i \leq 10^6

Sample Input 1

Sample Output 1

3
1 2 3

In the output above, 3 weights with masses 1, 2, and 3 are prepared.
This output satisfies the conditions. Especially, regarding the 3-rd condition, we can confirm that every integer between 1 and W, inclusive, is a good integer.

If we choose only the 1-st weight, it has a total mass of 1.
If we choose only the 2-nd weight, it has a total mass of 2.
If we choose only the 3-rd weight, it has a total mass of 3.
If we choose the 1-st and the 3-rd weights, they have a total mass of 4.
If we choose the 2-nd and the 3-rd weights, they have a total mass of 5.
If we choose the 1-st, the 2-nd, and the 3-rd weights, they have a total mass of 6.

Sample Input 2

Sample Output 2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.