AtCoder Daily Training ALL 2026/07/23 16:00start

A - Full House

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

5 枚のカードがあり、それぞれのカードには整数 A,B,C,D,E が書かれています。

この 5 枚組は以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

同じ数が書かれたカード 3 枚と、別の同じ数が書かれたカード 2 枚からなる。

5 枚組がフルハウスであるか判定してください。

制約

1 \leq A,B,C,D,E\leq 13
A,B,C,D,E 全てが同じ値ではない
入力は全て整数

入力

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

A B C D E

出力

フルハウスである場合 Yes を、そうでないとき No を出力せよ。

入力例 1

1 2 1 2 1

出力例 1

Yes

1 が書かれたカード 3 枚と、2 が書かれたカード 2 枚からなるため、これはフルハウスです。

入力例 2

12 12 11 1 2

出力例 2

No

フルハウスの条件を満たしません。

Score : 100 points

Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

1 \leq A,B,C,D,E\leq 13
Not all of A, B, C, D, and E are the same.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

If the set is a Full house, print Yes; otherwise, print No.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

B - Lucky Direction

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

8 種類の方角（北、東、西、南、北東、北西、南東、南西）のいずれかを表す文字列 D が与えられます。方角とそれを表す文字列は以下のように対応しています。

北：N
東：E
西：W
南：S
北東：NE
北西：NW
南東：SE
南西：SW

D が表す方角の反対の方角を表す文字列を出力してください。

制約

D は N, E, W, S, NE, NW, SE, SW のいずれか

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

北の反対の方角である南を表す S を出力してください。

入力例 2

SE

出力例 2

NW

南東の反対の方角である北西を表す NW を出力してください。

Score : 100 points

Problem Statement

You are given a string D representing one of the eight directions (north, east, west, south, northeast, northwest, southeast, southwest). The correspondence between the directions and their representing strings is as follows.

North: N
East: E
West: W
South: S
Northeast: NE
Northwest: NW
Southeast: SE
Southwest: SW

Print the string representing the direction opposite to the direction denoted by D.

Constraints

D is one of N, E, W, S, NE, NW, SE, SW.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

Print S, which represents south, the direction opposite to north.

Sample Input 2

SE

Sample Output 2

NW

Print NW, which represents northwest, the direction opposite to southeast.

C - Hammer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。

座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。

高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。

制約

-1000 \leq X,Y,Z \leq 1000
X,Y,Z は相異なり、いずれも 0 でない
入力に含まれる値は全て整数である

入力

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

X Y Z

出力

高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。

入力例 1

10 -10 1

出力例 1

高橋君はまっすぐゴールに向かうことができます。

入力例 2

20 10 -10

出力例 2

ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。

入力例 3

100 1 1000

出力例 3

-1

Score : 200 points

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

-1000 \leq X,Y,Z \leq 1000
X, Y, and Z are distinct, and none of them is 0.
All values in the input are integers.

Input

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

X Y Z

Output

If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.

Sample Input 1

10 -10 1

Sample Output 1

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

D - 1D Keyboard

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

26 個のキーが数直線上に並んだキーボードがあります。

このキーボードの配列は ABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列 S で表されます。文字 S_x に対応するキーが座標 x (1 \leq x \leq 26) にあります。ここで、S_x は S の x 文字目を表します。

あなたはこのキーボードを使って ABCDEFGHIJKLMNOPQRSTUVWXYZ をこの順で右手人差し指で一度だけ入力します。ある文字を入力するためには、その文字に対応するキーの座標に指を移動させてキーを押す必要があります。

はじめ、指は A に対応するキーの座標にあります。A に対応するキーを押してから、Z に対応するキーを押すまでの指の移動距離の合計として考えられる最小値を求めてください。ただし、キーを押す動作は移動距離に含まれません。

制約

S は ABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列である。

入力

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

出力

答えを出力せよ。

入力例 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

A のキーを押してから Z のキーを押すまで指を 1 ずつ正の方向に移動させる必要があり、このときの移動距離の合計は 25 です。25 未満の総移動距離でキーを全て入力することはできないため、25 と出力します。

入力例 2

MGJYIZDKSBHPVENFLQURTCWOAX

出力例 2

Score : 200 points

Problem Statement

There is a keyboard with 26 keys arranged on a number line.

The arrangement of this keyboard is represented by a string S, which is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ. The key corresponding to the character S_x is located at coordinate x (1 \leq x \leq 26). Here, S_x denotes the x-th character of S.

You will use this keyboard to input ABCDEFGHIJKLMNOPQRSTUVWXYZ in this order, typing each letter exactly once with your right index finger. To input a character, you need to move your finger to the coordinate of the key corresponding to that character and press the key.

Initially, your finger is at the coordinate of the key corresponding to A. Find the minimal possible total traveled distance of your finger from pressing the key for A to pressing the key for Z. Here, pressing a key does not contribute to the distance.

Constraints

S is a permutation of ABCDEFGHIJKLMNOPQRSTUVWXYZ.

Input

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

Output

Print the answer.

Sample Input 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output 1

From pressing the key for A to pressing the key for Z, you need to move your finger 1 unit at a time in the positive direction, resulting in a total traveled distance of 25. It is impossible to press all keys with a total traveled distance less than 25, so print 25.

Sample Input 2

MGJYIZDKSBHPVENFLQURTCWOAX

Sample Output 2

E - Uniqueness

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N の番号がついた N 人の人がいます。人 i は数 A_i を持っています。

「自分と同じ数を持っている人が自分以外の N-1 人の中に存在しない」という条件を満たす人のうち、持っている数が最大である人の番号を求めてください。

条件を満たす人が存在しない場合、代わりにそのことを報告してください。

制約

1 \leq N \leq 3\times 10^5
1 \leq A_i \leq 10^9
入力は全て整数である

入力

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

N
A_1 A_2 \ldots A_N

出力

「自分と同じ数を持っている人が自分以外の N-1 人の中に存在しない」という条件を満たす人が存在しない場合、-1 と出力せよ。

条件を満たす人が存在する場合、そのうち、持っている数が最大である人の番号を出力せよ。

入力例 1

9
2 9 9 7 9 2 4 5 8

出力例 1

「自分と同じ数を持っている人が自分以外の N-1 人の中に存在しない」という条件を満たすのは人 4,7,8,9 の 4 人です。
これらの人が持っている数はそれぞれ 7,4,5,8 であり、最大の数を持っているのは人 9 です。
よって答えは 9 となります。

入力例 2

4
1000000000 1000000000 998244353 998244353

出力例 2

-1

条件を満たす人が存在しない場合、-1 を出力してください。

Score : 300 points

Problem Statement

There are N people, labeled 1 to N. Person i has an integer A_i.

Among the people who satisfy the condition "None of the other N-1 people has the same integer as themselves," find the one with the greatest integer, and print that person's label.

If no person satisfies the condition, report that fact instead.

Constraints

1 \leq N \leq 3\times 10^5
1 \leq A_i \leq 10^9
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

If no person satisfies the condition "None of the other N-1 people has the same integer as themselves," print -1.

Otherwise, among those who satisfy it, print the label of the person whose integer is the largest.

Sample Input 1

9
2 9 9 7 9 2 4 5 8

Sample Output 1

Those who satisfy the condition are the persons labeled 4, 7, 8, and 9.
Their integers are 7, 4, 5, and 8, respectively, and the person with the largest integer is the person labeled 9.
Thus, the answer is 9.

Sample Input 2

4
1000000000 1000000000 998244353 998244353

Sample Output 2

-1

If no person satisfies the condition, print -1.

F - ~

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

整数列 A = (A_1, A_2, \ldots, A_{|A|}) に対し、A が チルダ型 とは以下の 4 つの条件をすべて満たすことであると定義します。

A の長さ |A| は 4 以上である
A_1 < A_2 である
A_{i - 1} < A_i > A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である　
A_{i - 1} > A_i < A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である

数列 (1, 2, \ldots, N) を並べ替えて得られる数列 P = (P_1, P_2, \ldots, P_N) が与えられます。P の連続部分列であってチルダ型である数列の個数を求めてください。

制約

4 \leq N \leq 3 \times 10^5
P = (P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) を並べ替えて得られる数列
入力される値はすべて整数

入力

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

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

6
1 3 6 4 2 5

出力例 1

数列 (1, 3, 6, 4, 2, 5) の連続部分列のうちチルダ型であるものは (3, 6, 4, 2, 5), (1, 3, 6, 4, 2, 5) の 2 つのみです。

入力例 2

6
1 2 3 4 5 6

出力例 2

入力例 3

12
11 3 8 9 5 2 10 4 1 6 12 7

出力例 3

Score : 350 points

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

The length |A| is at least 4.
A_1 < A_2.
There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

4 \leq N \leq 3 \times 10^5
P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
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

Output the answer.

Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

Sample Input 3

12
11 3 8 9 5 2 10 4 1 6 12 7

Sample Output 3

G - Toggle Maze

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマス目を (i,j) と表します。各マスの状態は文字 A_{i,j} で表され、意味は以下の通りです。

. ：空きマス。
# ：障害物マス。
S ：スタートマス。
G ：ゴールマス。
o ：開いたドアのマス。
x ：閉じたドアのマス。
? ：スイッチマス。

高橋君は、 1 回の操作で今いるマスから上下左右に隣り合う、障害物マスでも閉じたドアでもないマスへ移動することができます。

また、スイッチマスに移動する度に全ての開いたドアのマスは閉じたドアのマスに、閉じたドアのマスは開いたドアのマスに変わります。

高橋君がはじめスタートマスにいる状態からゴールマスにいる状態にするよう操作できるか判定し、可能な場合は必要な操作回数の最小値を求めてください。

制約

1\le H,W \le 500
H,W は整数
A_{i,j} は ., #, S, G, o, x, ? のいずれか
S と G は A_{i,j} にそれぞれちょうど 1 つずつ存在する

入力

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

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}

出力

高橋君がはじめスタートマスにいる状態からゴールマスにいる状態するよう操作できる場合は必要な操作回数の最小値を、できない場合は -1 を出力せよ。

入力例 1

2 4
S.xG
#?o.

出力例 1

(1,1) から順に (1,2),(2,2),(1,2),(1,3),(1,4) と移動するよう操作することで 5 回の操作でゴールマスにいる状態にすることができます。

入力例 2

1 5
So?oG

出力例 2

-1

どのように操作してもゴールマスにいる状態にすることはできません。したがって、 -1 を出力してください。

入力例 3

5 5
Sx?x?
o#o#x
?o?o?
x#x#o
?x?oG

出力例 3

Score : 400 points

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. The state of each cell is represented by a character A_{i,j}, with the following meanings:

. : Empty cell.
# : Obstacle cell.
S : Start cell.
G : Goal cell.
o : Open door cell.
x : Closed door cell.
? : Switch cell.

Takahashi can move from his current cell to an adjacent cell (up, down, left, right) that is neither an obstacle cell nor a closed door cell in one operation.

Also, every time he moves to a switch cell, all open door cells become closed door cells, and all closed door cells become open door cells.

Determine whether he can move from the initial state of being at the start cell to being at the goal cell, and if possible, find the minimum number of operations required.

Constraints

1\le H,W \le 500
H and W are integers.
Each A_{i,j} is one of ., #, S, G, o, x, ?.
S and G each appear exactly once in A_{i,j}.

Input

The 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 Takahashi can move from the initial state of being at the start cell to being at the goal cell, output the minimum number of operations required; otherwise, output -1.

Sample Input 1

2 4
S.xG
#?o.

Sample Output 1

By moving from (1,1) to (1,2),(2,2),(1,2),(1,3),(1,4) in that order, he can reach the goal cell in five operations.

Sample Input 2

1 5
So?oG

Sample Output 2

-1

No matter how he operates, he cannot reach the goal cell. Therefore, output -1.

Sample Input 3

5 5
Sx?x?
o#o#x
?o?o?
x#x#o
?x?oG

Sample Output 3

H - Count 123

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

以下の条件をすべて満たす長さ X_1+X_2+X_3 の数列 A = (a_1, \cdots, a_{X_1 + X_2 + X_3}) としてあり得るものの個数を 998244353 で割ったあまりを求めてください。

A は 1 を X_1 個、2 を X_2 個、3 を X_3 個含む。
隣接する要素の差の絶対値は 1 以下である。つまり、1 \leq i \leq X_1+X_2+X_3-1 を満たす任意の整数 i について、|a_{i+1} - a_i| \leq 1 が成り立つ。

制約

1 \leq X_1, X_2, X_3 \leq 10^6
入力される値はすべて整数

入力

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

X_1 X_2 X_3

出力

答えを出力せよ。

入力例 1

2 2 1

出力例 1

条件を満たす数列は以下の 9 通りです。

(1, 1, 2, 2, 3)
(1, 1, 2, 3, 2)
(1, 2, 1, 2, 3)
(1, 2, 3, 2, 1)
(2, 1, 1, 2, 3)
(2, 3, 2, 1, 1)
(3, 2, 1, 1, 2)
(3, 2, 1, 2, 1)
(3, 2, 2, 1, 1)

入力例 2

5 3 4

出力例 2

入力例 3

998244 998353 998107

出力例 3

701926019

Score : 450 points

Problem Statement

Find the number, modulo 998244353, of sequences A = (a_1, \cdots, a_{X_1 + X_2 + X_3}) of length X_1+X_2+X_3 that satisfy all of the following conditions.

A contains exactly X_1 copies of 1, exactly X_2 copies of 2, and exactly X_3 copies of 3.
The absolute difference between adjacent elements is at most 1. That is, for every integer i satisfying 1 \leq i \leq X_1+X_2+X_3-1, we have |a_{i+1} - a_i| \leq 1.

Constraints

1 \leq X_1, X_2, X_3 \leq 10^6
All input values are integers.

Input

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

X_1 X_2 X_3

Output

Output the answer.

Sample Input 1

2 2 1

Sample Output 1

The sequences satisfying the conditions are the following nine:

(1, 1, 2, 2, 3)
(1, 1, 2, 3, 2)
(1, 2, 1, 2, 3)
(1, 2, 3, 2, 1)
(2, 1, 1, 2, 3)
(2, 3, 2, 1, 1)
(3, 2, 1, 1, 2)
(3, 2, 1, 2, 1)
(3, 2, 2, 1, 1)

Sample Input 2

5 3 4

Sample Output 2

Sample Input 3

998244 998353 998107

Sample Output 3

701926019

I - Almost Sorted 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : {500} 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) および正整数 D が与えられます。

A を並び替えることで得られる整数列 B=(B_1, B_2, \ldots, B_N) であって、次の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

すべての i\ (1\leq i\leq N-1) に対して B_{i+1}\geq B_i-D が成り立つ。

制約

2\leq N\leq 2\times 10^5
1\leq D\leq 10^6
1\leq A_i\leq 10^6
入力は全て整数

入力

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

N D
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

4 1
5 2 1 2

出力例 1

条件を満たす整数列は (1,2,2,5),(2,1,2,5),(2,2,1,5) の 3 つです。

入力例 2

5 10
20 40 60 80 100

出力例 2

入力例 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

出力例 3

858152905

Score : 500 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and a positive integer D.

Find the number, modulo 998244353, of integer sequences B=(B_1, B_2, \ldots, B_N) that can be obtained by rearranging A and satisfy the following condition:

B_{i+1}\geq B_i-D holds for all i\ (1\leq i\leq N-1).

Constraints

2\leq N\leq 2\times 10^5
1\leq D\leq 10^6
1\leq A_i\leq 10^6
All input values are integers.

Input

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

N D
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

4 1
5 2 1 2

Sample Output 1

The integer sequences satisfying the condition are (1,2,2,5),(2,1,2,5),(2,2,1,5), which are three sequences.

Sample Input 2

5 10
20 40 60 80 100

Sample Output 2

Sample Input 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

Sample Output 3

858152905