AtCoder Daily Training HARD 2023/11/22 16:00start

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 - Almost Equal

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

英小文字からなる長さ M の文字列 N 個 S_1,S_2,\dots,S_N が与えられます。ここで、S_i は互いに異なります。

これらを並び替えた文字列の列 T_1,T_2,\dots,T_N であって、以下の条件を満たすものが存在するか判定してください。

1 \le i \le N-1 を満たす全ての整数 i に対して、T_i を 1 文字だけ別の英小文字に変えて T_{i+1} にすることが出来る。

制約

2 \le N \le 8
1 \le M \le 5
S_i は英小文字からなる長さ M の文字列である。(1 \le i \le N)
S_i は互いに異なる。

入力

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

N M
S_1
S_2
\vdots
S_N

出力

問題文の条件を満たす列が存在するならば Yes を、そうでないならば No を出力せよ。

入力例 1

4 4
bbed
abcd
abed
fbed

出力例 1

Yes

abcd , abed , bbed , fbed の順に並び替えると条件を満たします。

入力例 2

2 5
abcde
abced

出力例 2

No

どのように並び替えても条件を満たすことは出来ません。

入力例 3

8 4
fast
face
cast
race
fact
rice
nice
case

出力例 3

Yes

Score : 250 points

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

2 \le N \le 8
1 \le M \le 5
S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
S_i are pairwise distinct.

Input

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

N M
S_1
S_2
\vdots
S_N

Output

Print Yes if one can obtain a conforming sequence; print No otherwise.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

G - Takahashi's Solitaire

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は N 枚のカードを手札として持っています。 i = 1, 2, \ldots, N について、i 番目のカードには非負整数 A_i が書かれています。

高橋君は、まず手札から好きなカードを 1 枚選んで、テーブルの上に置きます。その後、高橋君は好きな回数（ 0 回でも良い）だけ、下記の操作を繰り返します。

最後にテーブルの上に置いたカードに書かれた整数を X とする。手札に整数 X または整数 (X+1)\bmod M が書かれたカードがあれば、そのうち好きなものを 1 枚選んで、テーブルの上に置く。ここで、(X+1)\bmod M は (X+1) を M で割ったあまりを表す。

最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値を出力してください。

制約

1 \leq N \leq 2 \times 10^5
2 \leq M \leq 10^9
0 \leq A_i \lt M
入力はすべて整数

入力

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

N M
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

9 7
3 0 2 5 5 3 0 6 3

出力例 1

高橋君が、まず 4 番目のカード（書かれた整数は 5 ）をテーブルの上に置き、その後、以下の手順で操作を行う場合を考えます。

5 番目のカード（書かれた整数は 5 ）をテーブルの上に置く。
8 番目のカード（書かれた整数は 6 ）をテーブルの上に置く。
2 番目のカード（書かれた整数は 0 ）をテーブルの上に置く。
7 番目のカード（書かれた整数は 0 ）をテーブルの上に置く。

このとき、最終的に手札に残ったカードは、1, 3, 6, 9 枚目のカードであり、それらに書かれた整数の総和は 3 + 2 + 3 +3 = 11 です。これが、最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値です。

入力例 2

1 10
4

出力例 2

入力例 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

出力例 3

Score : 400 points

Problem Statement

Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

1 \leq N \leq 2 \times 10^5
2 \leq M \leq 10^9
0 \leq A_i \lt M
All values in the input are integers.

Input

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

N M
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

Assume that he first puts the fourth card (5 is written) on the table and then performs the following.

Put the fifth card (5 is written) on the table.
Put the eighth card (6 is written) on the table.
Put the second card (0 is written) on the table.
Put the seventh card (0 is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

Sample Input 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3

H - Our clients, please wait a moment

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

ある国には都市が N 個あります。
あなたは、都市 1 にある営業所から 0 個以上の都市を経由して都市 N にある訪問先へ移動しようとしています。
移動手段は社用車と電車の 2 種類があります。都市 i から都市 j へ移動するときの所要時間は以下の通りです。

社用車を使った場合 : D_{i,j} \times A 分
電車を使った場合 : D_{i,j} \times B + C 分

ただし、社用車から電車に乗り換えることはできますが、電車から社用車に乗り換えることはできません。
また、乗り換えは各都市のみで行え、乗り換えに時間はかかりません。

都市 1 から都市 N に移動するのにかかる時間は最短で何分ですか？

制約

2 \leq N \leq 1000
1 \leq A, B, C \leq 10^6
D_{i,j} \leq 10^6
D_{i,i} = 0
D_{i,j} = D_{j,i} > 0 (i \neq j)
入力される数値はすべて整数

入力

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

N A B C
D_{1,1} D_{1,2} \ldots D_{1,N}
D_{2,1} D_{2,2} \ldots D_{2,N}
\vdots
D_{N,1} D_{N,2} \ldots D_{N,N}

出力

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

入力例 1

出力例 1

以下のように移動することで合計 78 分で都市 1 から都市 4 に移動することができます。

都市 1 から都市 3 まで社用車で移動する。この移動には 2 \times 8 = 16 分かかる。
都市 3 から都市 2 まで社用車で移動する。この移動には 3 \times 8 = 24 分かかる。
都市 2 から都市 4 まで電車で移動する。この移動には 5 \times 5 + 13 = 38 分かかる。

78 分未満の時間で都市 1 から都市 4 に移動することはできません。

入力例 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

出力例 2

入力例 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

出力例 3

168604826785

Score : 450 points

Problem Statement

There are N cities in a certain country.
You will travel from your office in city 1 to a destination in city N, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city i to city j is as follows:

D_{i,j} \times A minutes by company car, and
D_{i,j} \times B + C minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city 1 to city N?

Constraints

2 \leq N \leq 1000
1 \leq A, B, C \leq 10^6
D_{i,j} \leq 10^6
D_{i,i} = 0
D_{i,j} = D_{j,i} > 0 (i \neq j)
All input values are integers.

Input

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

N A B C
D_{1,1} D_{1,2} \ldots D_{1,N}
D_{2,1} D_{2,2} \ldots D_{2,N}
\vdots
D_{N,1} D_{N,2} \ldots D_{N,N}

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

You can travel from city 1 to city 4 in a total of 78 minutes by moving as follows.

Travel by company car from city 1 to city 3. This takes 2 \times 8 = 16 minutes.
Travel by company car from city 3 to city 2. This takes 3 \times 8 = 24 minutes.
Travel by train from city 2 to city 4. This takes 5 \times 5 + 13 = 38 minutes.

It is impossible to travel from city 1 to city 4 in less than 78 minutes.

Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785

I - Find 4-cycle

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

S+T 頂点 M 辺の単純無向グラフ G があります。頂点には 1 から S+T の番号が、辺には 1 から M の番号が割り振られています。辺 i は頂点 u_i と頂点 v_i を結んでいます。
また、頂点集合 V_1 = \lbrace 1, 2,\dots, S\rbrace および V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace はともに独立集合です。

長さ 4 のサイクルを 4-cycle と呼びます。
G が 4-cycle を含む場合、4-cycle をどれか 1 つ選び、選んだサイクルに含まれる頂点を出力してください。頂点を出力する順番は自由です。
G が 4-cycle を含まない場合、 -1 を出力してください。

独立集合とは？

グラフ G の独立集合とは、G に含まれるいくつかの頂点からなる集合 V' であって、V' に含まれる任意の 2 つの頂点の間に辺がないものを言います。

制約

2 \leq S \leq 3 \times 10^5
2 \leq T \leq 3000
4 \leq M \leq \min(S \times T,3 \times 10^5)
1 \leq u_i \leq S
S + 1 \leq v_i \leq S + T
i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
入力される値はすべて整数

入力

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

S T M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

G が 4-cycle を含む場合は、任意の 4-cycle を 1 つ選び、選んだサイクルに含まれている相異なる 4 個の頂点の番号を出力せよ。(頂点の順番は問わない。)
G が 4-cycle を含まない場合は -1 を出力せよ。

入力例 1

出力例 1

1 2 4 5

頂点 1 と 4 、4 と 2、2 と 5、5 と 1 の間に辺があるので頂点 1,2,4,5 は 4-cycle をなします。よって 1, 2, 4, 5 を出力すればよいです。
頂点を出力する順番は自由で、出力例のほかにも例えば 2 5 1 4 のような出力も正答となります。

入力例 2

出力例 2

-1

G が 4-cycle を含まない入力もあります。

入力例 3

出力例 3

1 7 2 9

Score : 500 points

Problem Statement

We have a simple undirected graph G with (S+T) vertices and M edges. The vertices are numbered 1 through (S+T), and the edges are numbered 1 through M. Edge i connects Vertices u_i and v_i.
Here, vertex sets V_1 = \lbrace 1, 2,\dots, S\rbrace and V_2 = \lbrace S+1, S+2, \dots, S+T \rbrace are both independent sets.

A cycle of length 4 is called a 4-cycle.
If G contains a 4-cycle, choose any of them and print the vertices in the cycle. You may print the vertices in any order.
If G does not contain a 4-cycle, print -1.

What is an independent set?

An independent set of a graph G is a set V' of some of the vertices in G such that no two vertices of V' have an edge between them.

Constraints

2 \leq S \leq 3 \times 10^5
2 \leq T \leq 3000
4 \leq M \leq \min(S \times T,3 \times 10^5)
1 \leq u_i \leq S
S + 1 \leq v_i \leq S + T
If i \neq j, then (u_i, v_i) \neq (u_j, v_j).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

S T M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If G contains a 4-cycle, choose any of them, and print the indices of the four distinct vertices in the cycle. (The order of the vertices does not matter.)
If G does not contain a 4-cycle, print -1.

Sample Input 1

Sample Output 1

1 2 4 5

There are edges between Vertices 1 and 4, 4 and 2, 2 and 5, and 5 and 1, so Vertices 1, 2, 4, and 5 form a 4-cycle. Thus, 1, 2, 4, and 5 should be printed.
The vertices may be printed in any order. Besides the Sample Output, 2 5 1 4 is also considered correct, for example.

Sample Input 2

Sample Output 2

-1

Some inputs may give G without a 4-cycle.

Sample Input 3

Sample Output 3

1 7 2 9