AtCoder Daily Training EASY 2024/06/12 18:00start

A - Probably English

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

配点 : 100 点

問題文

英小文字からなる N 個の文字列 W_1,W_2,\dots,W_N が与えられます。
これらのうち一つ以上が and, not, that, the, you のいずれかと一致するなら Yes 、そうでないなら No と出力してください。

制約

N は 1 以上 100 以下の整数
1 \le |W_i| \le 50 ( |W_i| は文字列 W_i の長さ )
W_i は英小文字からなる

入力

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

N
W_1 W_2 \dots W_N

出力

答えを出力せよ。

入力例 1

10
in that case you should print yes and not no

出力例 1

Yes

例えば W_4= you なので、 Yes と出力します。

入力例 2

10
in diesem fall sollten sie no und nicht yes ausgeben

出力例 2

No

文字列 W_i はいずれも、 and, not, that, the, you のいずれとも一致しません。

Score : 100 points

Problem Statement

You are given N strings W_1,W_2,\dots,W_N consisting of lowercase English letters.
If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.

Constraints

N is an integer between 1 and 100, inclusive.
1 \le |W_i| \le 50 (|W_i| is the length of W_i.)
W_i consists of lowercase English letters.

Input

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

N
W_1 W_2 \dots W_N

Output

Print the answer.

Sample Input 1

10
in that case you should print yes and not no

Sample Output 1

Yes

We have, for instance, W_4= you, so you should print Yes.

Sample Input 2

10
in diesem fall sollten sie no und nicht yes ausgeben

Sample Output 2

No

None of the strings W_i equals any of and, not, that, the, and you.

B - Majority

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

配点 : 100 点

問題文

ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。

i \, (i = 1, 2, \dots, N) 番目の人の意見は文字列 S_i で表され、S_i = For のとき賛成しており、S_i = Against のとき反対しています。

過半数の人がこの提案に賛成しているかどうかを判定してください。

制約

N は 1 以上 99 以下の奇数
全ての i = 1, 2, \dots, N に対し、S_i = For または S_i = Against

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 人のうち過半数が提案に賛成しているならば Yes、そうでなければ No と出力せよ。

入力例 1

3
For
Against
For

出力例 1

Yes

提案に賛成している人数は 2 人であり、これは半数を超えているので Yes と出力します。

入力例 2

5
Against
Against
For
Against
For

出力例 2

No

提案に賛成している人数は 2 人であり、これは半数以下なので No と出力します。

入力例 3

1
For

出力例 3

Yes

Score : 100 points

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

N is an odd number between 1 and 99, inclusive.
S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print Yes if the majority of the N people agree with the proposal; print No otherwise.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

C - Coloring Matrix

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

配点 : 200 点

問題文

各要素が 0 あるいは 1 である N 行 N 列の行列 A, B が与えられます。
A の i 行目 j 列目の要素を A_{i,j}、B の i 行目 j 列目の要素を B_{i,j} で表します。
A を適切に回転することで、 A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできるか判定してください。
ただし、A を回転するとは、以下の操作を好きな回数（0 回でもよい）繰り返すことをいいます。

1 \leq i, j \leq N を満たすすべての整数の組 (i, j) について同時に A_{i,j} を A_{N + 1 - j,i} で置き換える

制約

1 \leq N \leq 100
A, B の各要素は 0 か 1 のいずれか
入力はすべて整数

入力

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

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

出力

A を適切に回転することで、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているようにできる場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

出力例 1

Yes

はじめ、A は

0 1 1
1 0 0
0 1 0

です。
1 回操作を行うと、A は

0 1 0
1 0 1 
0 0 1

となります。
もう 1 度操作を行うと、A は

0 1 0
0 0 1
1 1 0

となります。
このとき、A_{i,j} = 1 であるすべての整数の組 (i, j) について B_{i,j} = 1 が成り立っているので、Yes を出力します。

入力例 2

出力例 2

Yes

入力例 3

出力例 3

No

Score : 200 points

Problem Statement

You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:

for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.

Constraints

1 \leq N \leq 100
Each element of A and B is 0 or 1.
All values in the input are integers.

Input

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

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

Output

If it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

Initially, A is :

0 1 1
1 0 0
0 1 0

After performing the operation once, A is :

0 1 0
1 0 1 
0 0 1

After performing the operation once again, A is :

0 1 0
0 0 1
1 1 0

Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.

Sample Input 2

Sample Output 2

Yes

Sample Input 3

Sample Output 3

No

D - Mongeness

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

配点 : 200 点

問題文

縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。上から i 行目、左から j 列目のマスに書かれている整数は A_{i, j} です。

マス目が下記の条件を満たすかどうかを判定してください。

1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たすすべての整数の組 (i_1, i_2, j_1, j_2) について、A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立つ。

制約

2 \leq H, W \leq 50
1 \leq A_{i, j} \leq 10^9
入力はすべて整数

入力

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

H W
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}

出力

マス目が問題文中の条件を満たす場合は Yes と出力し、条件を満たさない場合は No と出力せよ。

入力例 1

出力例 1

Yes

1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たす整数の組 (i_1, i_2, j_1, j_2) は 9 個存在し、それらすべてについて A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立ちます。例えば、

(i_1, i_2, j_1, j_2) = (1, 2, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 2, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 2, 2, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 3, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 3, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}

が成り立ちます。残りの (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3) についても同様に確認できます。
よって、Yes を出力します。

入力例 2

2 4
4 3 2 1
5 6 7 8

出力例 2

No

問題文中の条件を満たさないので、No を出力します。
例えば、(i_1, i_2, j_1, j_2) = (1, 2, 1, 4) について、A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} です。

Score : 200 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

2 \leq H, W \leq 50
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
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

If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

E - Make Takahashi Happy

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

配点 : 300 点

問題文

H 行 W 列のマス目があります。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす 2 つの整数 i, j について、上から i 行目、左から j 列目のマス（以下、(i, j) と表す）には、整数 A_{i, j} が書かれています。

いま、高橋君は (1, 1) にいます。これから高橋君は「いまいるマスから右または下に隣接するマスに移動する」ことを繰り返して、(H, W) まで移動します。ただし、その過程でマス目の外部に移動することは出来ません。

その結果、高橋君が通ったマス（始点 (1, 1) と終点 (H, W) を含む）に書かれた整数がすべて異なるとき、高橋君は嬉しくなります。高橋君の移動経路として考えられるもののうち、高橋君が嬉しくなるものの個数を出力してください。

制約

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

入力

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

H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君の移動経路として考えられるものは下記の 6 通りです。

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 2, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。

よって、高橋君が嬉しくなる移動経路は、上で 3, 5, 6 番目に述べた 3 個です。

入力例 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

出力例 2

この例では、高橋君は考えられるどの経路を通っても嬉しくなります。

Score : 300 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

2 \leq H, W \leq 10
1 \leq A_{i, j} \leq 10^9
All values in the input are integers.

Input

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

H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}

Output

Print the answer.

Sample Input 1

Sample Output 1

There are six possible paths:

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Sample Output 2

In this example, every possible path makes him happy.