AtCoder Daily Training MEDIUM 2024/03/05 17:30start

C - AtCoder Quiz

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder では現在、 ABC , ARC , AGC , AHC の 4 つのコンテストが定期的に開催されています。

AtCoder で現在定期的に開催されているコンテストは S_1 , S_2 , S_3 とあと 1 つは何ですか?

制約

S_1 , S_2 , S_3 はそれぞれ、 ABC , ARC , AGC , AHC のいずれかである。
S_1 , S_2 , S_3 は相異なる。

入力

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

S_1
S_2
S_3

出力

答えを出力せよ。

入力例 1

ARC
AGC
AHC

出力例 1

ABC

ARC , AGC , AHC の 3つが入力として与えられているので、残りの 1 つはABC です。

入力例 2

AGC
ABC
ARC

出力例 2

AHC

Score : 200 points

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
S_1, S_2, and S_3 are pairwise different.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3

Output

Print the answer.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

D - Longest Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

文字列 S が与えられます。 S の連続する部分文字列のうち、回文であるものの長さの最大値を求めてください。
ただし、S の連続する部分文字列であって回文であるものは常に存在します。

制約

S は長さ 2 以上 100 以下の英大文字からなる文字列

入力

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

出力

答えを出力せよ。

入力例 1

TOYOTA

出力例 1

TOYOTA の連続する部分文字列 TOYOT は長さ 5 の回文です。
TOYOTA の唯一の長さ 6 の連続する部分文字列 TOYOTA は回文でないので、5 を出力します。

入力例 2

ABCDEFG

出力例 2

すべての長さ 1 の連続する部分文字列は回文です。

入力例 3

AAAAAAAAAA

出力例 3

Score : 200 points

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Input

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

Output

Print the answer.

Sample Input 1

TOYOTA

Sample Output 1

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

E - Previous Permutation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。ただし、(P_1, \dots, P_N) \neq (1, \dots, N) です。

(1 \dots, N) の順列を全て辞書順で小さい順に並べたとき、P が K 番目であるとします。辞書順で小さい方から K-1 番目の順列を求めてください。

順列とは？

(1, \dots, N) の順列とは、(1, \dots, N) を並べ替えて得られる数列のことをいいます。

辞書順とは？

長さ N の数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) に対し、A が B より辞書順で真に小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことをいいます。

(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
A_i < B_i

制約

2 \leq N \leq 100
1 \leq P_i \leq N \, (1 \leq i \leq N)
P_i \neq P_j \, (i \neq j)
(P_1, \dots, P_N) \neq (1, \dots, N)
入力される値は全て整数

入力

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

N
P_1 \ldots P_N

出力

求める順列を Q = (Q_1, \dots, Q_N) として、Q_1, \dots, Q_N をこの順に空白区切りで一行に出力せよ。

入力例 1

3
3 1 2

出力例 1

2 3 1

(1, 2, 3) の順列を辞書順で小さい順に並べると次のようになります。

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

よって P = (3, 1, 2) は小さい方から 5 番目であり、求める順列、すなわち小さい方から 5 - 1 = 4 番目の順列は (2, 3, 1) です。

入力例 2

10
9 8 6 5 10 3 1 2 4 7

出力例 2

9 8 6 5 10 2 7 4 3 1

Score : 300 points

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

What are permutations?

A permutation of (1, \dots, N) is an arrangement of (1, \dots, N) into a sequence.

What is lexicographical order?

For sequences of length N, A = (A_1, \dots, A_N) and B = (B_1, \dots, B_N), A is said to be strictly lexicographically smaller than B if and only if there is an integer 1 \leq i \leq N that satisfies both of the following.

(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
A_i < B_i.

Constraints

2 \leq N \leq 100
1 \leq P_i \leq N \, (1 \leq i \leq N)
P_i \neq P_j \, (i \neq j)
(P_1, \dots, P_N) \neq (1, \dots, N)
All values in the input are integers.

Input

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

N
P_1 \ldots P_N

Output

Let Q = (Q_1, \dots, Q_N) be the sought permutation. Print Q_1, \dots, Q_N in a single line in this order, separated by spaces.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

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

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

F - Socks 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

高橋君は N 組の靴下を持っており、i 番目の組は色 i の靴下 2 枚からなります。ある日タンスの中を整理した高橋君は、色 A_1,A_2,\dots,A_K の靴下を 1 枚ずつなくしてしまったことに気づいたので、残っている 2N-K 枚の靴下を使って、靴下 2 枚ずつからなる \lfloor\frac{2N-K}{2}\rfloor 個の組を新たに作り直すことにしました。色 i の靴下と色 j の靴下からなる組の奇妙さは |i-j| として定義され、高橋君は奇妙さの総和をできるだけ小さくしたいです。

残っている靴下をうまく組み合わせて \lfloor\frac{2N-K}{2}\rfloor 個の組を作ったとき、奇妙さの総和が最小でいくつになるか求めてください。なお、2N-K が奇数のとき、どの組にも含まれない靴下が 1 枚存在することに注意してください。

制約

1\leq K\leq N \leq 2\times 10^5
1\leq A_1 < A_2 < \dots < A_K \leq N
入力は全て整数

入力

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

N K
A_1 A_2 \dots A_K

出力

奇妙さの総和の最小値を整数として出力せよ。

入力例 1

4 2
1 3

出力例 1

以下、色 i の靴下と色 j の靴下からなる組を (i,j) と表記します。

色 1,2,3,4 の靴下がそれぞれ 1,2,1,2 枚ずつあります。 (1,2),(2,3),(4,4) の 3 組を作ると、奇妙さの総和は |1-2|+|2-3|+|4-4|=2 となり、これが最小です。

入力例 2

5 1
2

出力例 2

(1,1),(3,3),(4,4),(5,5) の 4 組を作り、色 2 の靴下を 1 枚余らせる（どの組にも入れない）のが最適です。

入力例 3

8 5
1 2 4 7 8

出力例 3

Score : 350 points

Problem Statement

Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.

Constraints

1\leq K\leq N \leq 2\times 10^5
1\leq A_1 < A_2 < \dots < A_K \leq N
All input values are integers.

Input

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

N K
A_1 A_2 \dots A_K

Output

Print the minimum total weirdness as an integer.

Sample Input 1

4 2
1 3

Sample Output 1

Below, let (i,j) denote a pair of a sock of color i and a sock of color j.

There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

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.