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

A - Exponential or Quadratic

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

2^n \gt n^2 ですか？

制約

n は 1 以上 10^9 以下の整数

入力

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

出力

2^n \gt n^2 なら Yes を、そうでないなら No を出力せよ。

入力例 1

出力例 1

Yes

2^5=32,\ 5^2=25 より 2^n \gt n^2 であるため、Yes を出力します。

入力例 2

出力例 2

No

n=2 の場合 2^n=n^2=2^2 となり、故に 2^n \gt n^2 ではありません。よって No を出力します。

入力例 3

623947744

出力例 3

Yes

Score : 100 points

Problem Statement

Does 2^n \gt n^2 hold?

Constraints

n is an integer between 1 and 10^9 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

If 2^n \gt n^2, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

B - Intersection

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

X=L_1 から X=R_1 までをすべて赤色で塗る。
X=L_2 から X=R_2 までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
入力はすべて整数

入力

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

L_1 R_1 L_2 R_2

出力

両方の色で塗られている部分の長さを整数で出力せよ。

入力例 1

0 3 1 5

出力例 1

X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。

よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。

入力例 2

0 1 4 5

出力例 2

両方の色で塗られている部分はありません。

入力例 3

0 3 3 7

出力例 3

赤色と青色で塗られている部分が接している場合でも、両方の色で塗られている部分の長さは 0 となります。

Score : 100 points

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

First, he painted the part from X=L_1 to X=R_1 red.
Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L_1 R_1 L_2 R_2

Output

Print the length of the part of the line painted both red and blue, as an integer.

Sample Input 1

0 3 1 5

Sample Output 1

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

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