AtCoder Daily Training EASY 2026/03/06 18:00start

A - Subsegment Reverse

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N,L,R が与えられます。
長さ N の数列 A=(1,2,\dots,N) に対し、 L 項目から R 項目までを逆順に並べ替えるという操作を一度行いました。
操作後の数列を出力してください。

制約

入力は全て整数
1 \le L \le R \le N \le 100

入力

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

N L R

出力

操作後の数列を A'=(A'_1,A'_2,\dots,A'_N) として、以下の形式で出力せよ。

A'_1 A'_2 \dots A'_N

入力例 1

5 2 3

出力例 1

1 3 2 4 5

最初、 A=(1,2,3,4,5) です。
2 項目から 3 項目までを逆順に並べ替えた後の数列は (1,3,2,4,5) なので、これを出力してください。

入力例 2

7 1 1

出力例 2

1 2 3 4 5 6 7

L=R である場合もあります。

入力例 3

10 1 10

出力例 3

10 9 8 7 6 5 4 3 2 1

L=1 や R=N である場合もあります。

Score : 100 points

Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

All input values are integers.
1 \leq L \leq R \leq N \leq 100

Input

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

N L R

Output

Let A' = (A'_1, A'_2, \dots, A'_N) be the sequence after the operation. Print it in the following format:

A'_1 A'_2 \dots A'_N

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

B - Overall Winner

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんと青木くんが N 回の試合を行いました。これらの試合の結果を表す長さ N の文字列 S が与えられます。 i 回目の試合の勝者は、S の i 文字目が T ならば高橋くん、A ならば青木くんです。

高橋くんと青木くんのうち、勝った試合の数が多い方を総合勝者とします。ただし、勝った試合の数が同じである場合は、先にその勝ち数に達した者を総合勝者とします。高橋くんと青木くんのどちらが総合勝者であるか求めてください。

制約

1\leq N \leq 100
N は整数
S は T および A からなる長さ N の文字列

入力

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

N
S

出力

総合勝者が高橋くんならば T を、青木くんならば A を出力せよ。

入力例 1

5
TTAAT

出力例 1

高橋くんは 3 回の試合に勝ち、青木くんは 2 回の試合に勝ちました。よって、勝った試合の数が多い高橋くんが総合勝者です。

入力例 2

6
ATTATA

出力例 2

高橋くんと青木くんのどちらも 3 回の試合に勝ちました。また、高橋くんは 5 回目の試合で 3 勝目に達し、青木くんは 6 回目の試合で 3 勝目に達しました。よって、先に 3 勝目に達した高橋くんが総合勝者です。

入力例 3

1
A

出力例 3

Score : 100 points

Problem Statement

Takahashi and Aoki played N games. You are given a string S of length N, representing the results of these games. Takahashi won the i-th game if the i-th character of S is T, and Aoki won that game if it is A.

The overall winner between Takahashi and Aoki is the one who won more games than the other. If they had the same number of wins, the overall winner is the one who reached that number of wins first. Find the overall winner: Takahashi or Aoki.

Constraints

1\leq N \leq 100
N is an integer.
S is a string of length N consisting of T and A.

Input

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

N
S

Output

If the overall winner is Takahashi, print T; if it is Aoki, print A.

Sample Input 1

5
TTAAT

Sample Output 1

Takahashi won three games, and Aoki won two. Thus, the overall winner is Takahashi, who won more games.

Sample Input 2

6
ATTATA

Sample Output 2

Both Takahashi and Aoki won three games. Takahashi reached three wins in the fifth game, and Aoki in the sixth game. Thus, the overall winner is Takahashi, who reached three wins first.

Sample Input 3

1
A

Sample Output 3

C - chess960

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は chess960 と呼ばれるゲームで遊んでいます。高橋君はランダムに決めた初期配置が chess960 の条件を満たすか確認するプログラムを書くことにしました。

長さ 8 の文字列 S が与えられます。S には K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれます。 S が以下の条件を全て満たしているか判定してください。

S において左から x,y\ (x < y) 文字目が B であるとする。このとき x と y の偶奇が異なる。
K は 2 つの R の間にある。より形式的には、S において左から x,y\ (x < y) 文字目が R であり、 z 文字目が K であるとする。このとき、 x< z < y が成り立つ。

制約

S は長さ 8 の文字列であり、K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれる。

入力

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

出力

S が条件を満たす場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

RNBQKBNR

出力例 1

Yes

B は左から 3 番目、6 番目にあり、3 と 6 は偶奇が異なります。また、K は 2 つの R の間にあります。よって条件を満たします。

入力例 2

KRRBBNNQ

出力例 2

No

K は 2 つの R の間にありません。

入力例 3

BRKRBQNN

出力例 3

No

Score : 200 points

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.
K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Input

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

Output

Print Yes if S satisfies the conditions; print No otherwise.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

D - Number Box

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

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

N 行 N 列のマス目があり、上から i 行目、左から j 列目のマスには数字 A_{i,j} が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

(1,i) の上のマスは (N,i) であり、(N,i) の下のマスは (1,i) である。(1\le i\le N)
(i,1) の左のマスは (i,N) であり、(i,N) の右のマスは (i,1) である。(1\le i\le N)

高橋君は、上下左右および斜めの 8 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に 1 マス移動することを N-1 回繰り返します。

高橋君は N 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

1 \le N \le 10
1 \le A_{i,j} \le 9
入力はすべて整数。

入力

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

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}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君が上から 2 行目、左から 4 列目のマスから出発し、右下に進むことで、通ったマスに書かれた数字を並べ 9786 を作ることができます。 9786 より大きい値を作ることはできないため、9786 が解です。

入力例 2

出力例 2

1111111111

32bit整数型に答えが収まるとは限らないことに注意してください。

Score : 200 points

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

(N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
(i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

1 \le N \le 10
1 \le A_{i,j} \le 9
All values in input are integers.

Input

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}

Output

Print the answer.

Sample Input 1

Sample Output 1

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

E - 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.