AtCoder Daily Training MEDIUM 2024/04/04 20:30start

C - Qualification Contest

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

配点 : 200 点

問題文

N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

1 \leq K \leq N \leq 100
K, N は整数
S_i は英小文字からなる長さ 10 以下の文字列
i \neq j ならば S_i \neq S_j

入力

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

N K
S_1
S_2
\vdots
S_N

出力

答えを改行区切りで出力せよ。

入力例 1

5 3
abc
aaaaa
xyz
a
def

出力例 1

aaaaa
abc
xyz

このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。

上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。

入力例 2

4 4
z
zyx
zzz
rbg

出力例 2

rbg
z
zyx
zzz

入力例 3

3 1
abc
arc
agc

出力例 3

abc

Score : 200 points

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

What is lexicographical order?

Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.

Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.

Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.

Constraints

1 \leq K \leq N \leq 100
K and N are integers.
S_i is a string of length 10 consisting of lowercase English letters.
S_i \neq S_j if i \neq j.

Input

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

N K
S_1
S_2
\vdots
S_N

Output

Print the nicknames, separated by newlines.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc

D - Rotate

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

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
入力は全て整数

入力

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

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 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

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}

入力例 1

出力例 1

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。

入力例 2

2
11
11

出力例 2

11
11

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
All input values are integers.

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}

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

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}

Sample Input 1

Sample Output 1

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

Sample Output 3

E - abc285_brutmhyhiizp

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

配点 : 300 点

問題文

別世界の AtCoder で開催されている AtCoder Big Contest では、 10^{16} 問の問題が一度に出題されます。
問題の ID は 1 問目から順に A, B, ..., Z, AA, AB, ..., ZZ, AAA, ... と付けられています。

つまり、 ID は以下の順番で付けられています。

長さ 1 の英大文字からなる文字列を辞書順に並べたもの
長さ 2 の英大文字からなる文字列を辞書順に並べたもの
長さ 3 の英大文字からなる文字列を辞書順に並べたもの
...

このコンテストに含まれる問題の ID である文字列 S が与えられるので、それが何問目か答えてください。

制約

S は AtCoder Big Contest に含まれる問題の ID として正しい

入力

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

出力

答えを整数として出力せよ。

入力例 1

AB

出力例 1

ID が AB である問題は、 AtCoder Big Contest の 28 問目です。

入力例 2

出力例 2

ID が C である問題は、 AtCoder Big Contest の 3 問目です。

入力例 3

BRUTMHYHIIZP

出力例 3

10000000000000000

ID が BRUTMHYHIIZP である問題は、 AtCoder Big Contest の 10^{16} 問目、すなわち最終問題です。

Score : 300 points

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

the strings of length 1 consisting of uppercase English letters, in lexicographical order;
the strings of length 2 consisting of uppercase English letters, in lexicographical order;
the strings of length 3 consisting of uppercase English letters, in lexicographical order;
...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

S is a valid ID of a problem given in AtCoder Big Contest.

Input

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

Output

Print the answer as an integer.

Sample Input 1

AB

Sample Output 1

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

Sample Output 2

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

F - Blue Spring

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

配点 : 300 点

問題文

高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。

ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。

N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq D\leq 2\times 10^5
1\leq P\leq 10^9
1\leq F_i\leq 10^9
入力はすべて整数

入力

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

N D P
F_1 F_2 \ldots F_N

出力

N 日間の旅行でかかる金額としてあり得る最小値を出力せよ。

入力例 1

5 2 10
7 1 6 3 6

出力例 1

1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。

入力例 2

3 1 10
1 2 3

出力例 2

3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。

入力例 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

3000000000

1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。

Score : 300 points

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

1\leq N\leq 2\times 10^5
1\leq D\leq 2\times 10^5
1\leq P\leq 10^9
1\leq F_i\leq 10^9
All input values are integers.

Input

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

N D P
F_1 F_2 \ldots F_N

Output

Print the minimum possible total cost for the N-day trip.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

G - Distinct Trio

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

配点 : 400 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
以下の 2 条件をともに満たすような整数の組 (i,j,k) の個数を求めてください。

1\leq i \lt j \lt k \leq N
A_i,A_j,A_k は相異なる

制約

3 \leq N \leq 2\times 10^5
1 \leq A_i \leq 2\times 10^5
入力に含まれる値は全て整数である

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

4
3 1 4 1

出力例 1

条件を満たす整数の組 (i,j,k) は (1,2,3),(1,3,4) の 2 つです。

入力例 2

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

出力例 2

入力例 3

15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

出力例 3

Score : 400 points

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\ldots,A_N).
Find the number of triples (i,j,k) that satisfy both of the following conditions.

1\leq i \lt j \lt k \leq N
A_i, A_j, and A_k are distinct.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

4
3 1 4 1

Sample Output 1

The two triples (i,j,k) satisfying the conditions are (1,2,3) and (1,3,4).

Sample Input 2

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

Sample Output 2

Sample Input 3

15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9