A - September

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

英小文字からなる 12 個の文字列 S_1,S_2,\ldots,S_{12} があります。

S_i の長さが i であるような整数 i (1 \leq i \leq 12) がいくつあるか求めてください。

制約

  • S_i は英小文字からなる長さ 1 以上 100 以下の文字列である。(1 \leq i \leq 12)

入力

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

S_1
S_2
\vdots
S_{12}

出力

S_i の長さが i であるような整数 i (1 \leq i \leq 12) がいくつあるか出力せよ。


入力例 1

january
february
march
april
may
june
july
august
september
october
november
december

出力例 1

1

S_i の長さが i であるような整数 i91 つのみです。よって、1 と出力します。


入力例 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

出力例 2

2

S_i の長さが i であるような整数 i4,82 つです。よって、2 と出力します。

Score : 100 points

Problem Statement

There are 12 strings S_1, S_2, \ldots, S_{12} consisting of lowercase English letters.

Find how many integers i (1 \leq i \leq 12) satisfy that the length of S_i is i.

Constraints

  • Each S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters. (1 \leq i \leq 12)

Input

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

S_1
S_2
\vdots
S_{12}

Output

Print the number of integers i (1 \leq i \leq 12) such that the length of S_i is i.


Sample Input 1

january
february
march
april
may
june
july
august
september
october
november
december

Sample Output 1

1

There is only one integer i such that the length of S_i is i: 9. Thus, print 1.


Sample Input 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

Sample Output 2

2

There are two integers i such that the length of S_i is i: 4 and 8. Thus, print 2.

B - 1D Keyboard

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

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

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

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

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

制約

  • SABCDEFGHIJKLMNOPQRSTUVWXYZ を並べ替えた文字列である。

入力

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

S

出力

答えを出力せよ。


入力例 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

25

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


入力例 2

MGJYIZDKSBHPVENFLQURTCWOAX

出力例 2

223

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:

S

Output

Print the answer.


Sample Input 1

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output 1

25

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

223
C - Max Ai+Bj

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250

問題文

長さ N の整数列 A,B が与えられます。1 以上 N 以下の整数 i,j を選んで、 A_i + B_j の値を最大化してください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9\,(i=1,2,\dots,N)
  • |B_j| \leq 10^9\,(j=1,2,\dots,N)
  • 入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

A_i + B_j の最大値を出力せよ。


入力例 1

2
-1 5
3 -7

出力例 1

8

(i,j)=(1,1),(1,2),(2,1),(2,2) に対する A_i+B_j の値はそれぞれ 2,-8,8,-2 であり、(i,j)=(2,1) が最大値 8 を達成します。


入力例 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

出力例 2

33

Score : 250 points

Problem Statement

You are given two integer sequences A and B, each of length N. Choose integers i, j (1 \leq i, j \leq N) to maximize the value of A_i + B_j.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • |A_i| \leq 10^9 (i=1,2,\dots,N)
  • |B_j| \leq 10^9 (j=1,2,\dots,N)
  • All input values are integers.

Input

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the maximum possible value of A_i + B_j.


Sample Input 1

2
-1 5
3 -7

Sample Output 1

8

For (i,j) = (1,1), (1,2), (2,1), (2,2), the values of A_i + B_j are 2, -8, 8, -2 respectively, and (i,j) = (2,1) achieves the maximum value 8.


Sample Input 2

6
15 12 3 -13 -1 -19
7 17 -13 -10 18 4

Sample Output 2

33
D - Hidden Weights

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

N 頂点 M 辺の有向グラフが与えられます。j 番目の有向辺は頂点 u_j から頂点 v_j に向かっており、重み w_j を持っています。

各頂点に -10^{18} 以上 10^{18} 以下の整数を書き込む方法であって、次の条件を満たすものを 1 つ見つけてください。

  • 頂点 i に書き込まれている値を x_i とする。すべての辺 j=1,2,\dots,M について、x_{v_j} - x_{u_j} = w_j が成り立つ。

与えられる入力について、条件を満たす書き込み方が少なくとも 1 つ存在することが保証されます。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}
  • 1 \leq u_j, v_j \leq N
  • u_j \neq v_j
  • i \neq j なら (u_i,v_i) \neq (u_j,v_j) かつ (u_i,v_i) \neq (v_j,u_j)
  • |w_j| \leq 10^9
  • 入力はすべて整数
  • 条件を満たす書き込み方が少なくとも 1 つ存在する

入力

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

N M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M

出力

頂点 i に書き込む整数を x_i として、x_1,x_2,\dots,x_N をこの順に空白区切りで 1 行で出力せよ。答えが複数ある場合、どれを出力しても良い。


入力例 1

3 3
1 2 2
3 2 3
1 3 -1

出力例 1

3 5 2

x=(3,5,2) とすることで、x_2-x_1=w_1=2,x_2-x_3=w_2=3,x_3-x_1=w_3=-1 となり、条件を満たします。

他にも、たとえば x=(-1,1,-2) としても正解となります。


入力例 2

4 2
2 1 5
3 4 -3

出力例 2

5 0 6 3

他にも、たとえば x=(0,-5,4,1)x=(5,0,4,1) としても正解となります。


入力例 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

出力例 3

200401298 182231955 -106709603 69445364 278499365

Score : 400 points

Problem Statement

You are given a directed graph with N vertices and M edges. The j-th directed edge goes from vertex u_j to vertex v_j and has a weight of w_j.

Find one way to write an integer between -10^{18} and 10^{18}, inclusive, to each vertex such that the following condition is satisfied.

  • Let x_i be the value written on vertex i. For all edges j=1,2,\dots,M, it holds that x_{v_j} - x_{u_j} = w_j.

It is guaranteed that at least one such assignment exists for the given input.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}
  • 1 \leq u_j, v_j \leq N
  • u_j \neq v_j
  • If i \neq j, then (u_i, v_i) \neq (u_j, v_j) and (u_i, v_i) \neq (v_j, u_j)
  • |w_j| \leq 10^9
  • All input values are integers.
  • There exists at least one assignment satisfying the conditions.

Input

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

N M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M

Output

Let x_i be the integer written on vertex i. Print x_1, x_2, \dots, x_N in this order, separated by spaces, on a single line. If there are multiple solutions, you may print any of them.


Sample Input 1

3 3
1 2 2
3 2 3
1 3 -1

Sample Output 1

3 5 2

By setting x = (3, 5, 2), we have x_2 - x_1 = w_1 = 2, x_2 - x_3 = w_2 = 3, x_3 - x_1 = w_3 = -1, satisfying the conditions.

For example, x = (-1, 1, -2) is also a valid answer.


Sample Input 2

4 2
2 1 5
3 4 -3

Sample Output 2

5 0 6 3

For example, x = (0, -5, 4, 1) and x = (5, 0, 4, 1) are also valid answers.


Sample Input 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

Sample Output 3

200401298 182231955 -106709603 69445364 278499365
E - How to Win the Election

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : 500

問題文

1,2,\ldots,N の番号のついた N 人の候補者で選挙が行われています。K 票の投票があり、現在一部の開票作業が行なわれました。

これまでの開票作業では、i 番目の候補者に A_i 票が入りました。

全ての票が開票された後、i 番目 (1 \leq i \leq N) の候補者はその候補者より多く票を獲得した候補者が M 人未満であるとき、かつその時に限り当選します。複数の候補者が当選することもあります。

各候補者が当選を確定させるためには残りの票のうち最小で何票追加で票が必要か求めてください。

より厳密には、i = 1,2,\ldots,N に対して次の問題を解いてください。

次の条件を満たす K - \displaystyle{\sum_{i=1}^{N}} A_i 以下の非負整数 X が存在するか判定し、存在するならその最小値を求めてください。

  • これ以降の開票作業で i 番目の候補者へ X 票入るなら、i 番目の候補者は必ず当選する。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{12}
  • 0 \leq A_i \leq 10^{12}
  • \displaystyle{\sum_{i=1}^{N} A_i} \leq K
  • 入力はすべて整数

入力

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

N M K
A_1 A_2 \ldots A_N

出力

候補者 i が当選を確定させるために必要な票数を C_i としたとき、C_1,C_2,\ldots,C_N を空白区切りで出力せよ。

ただし、候補者 i がすでに当選を確定させている場合は C_i=0、候補者 i が当選を確定させることができない場合は C_i=-1 とします。


入力例 1

5 2 16
3 1 4 1 5

出力例 1

2 -1 1 -1 0

すでに 14 票の開票が終了しており、残りの票数は 2 票です。
答えるべき C(2, -1, 1, -1, 0) です。たとえば:

  • 候補者 1 は追加で 2 票得ることで当選を確定することができます。追加で 1 票獲得することでは当選を確定することができないので、C_1 = 2 です。
  • 候補者 2 はどのようにしても(例えば、残り 2 票をすべて獲得しても)当選することが不可能なので、 C_2 = -1 です。

入力例 2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

出力例 2

79 89 111 117 117 74 112 116 80 107 117 106

Score : 500 points

Problem Statement

An election is being held with N candidates numbered 1, 2, \ldots, N. There are K votes, some of which have been counted so far.

Up until now, candidate i has received A_i votes.

After all ballots are counted, candidate i (1 \leq i \leq N) will be elected if and only if the number of candidates who have received more votes than them is less than M. There may be multiple candidates elected.

For each candidate, find the minimum number of additional votes they need from the remaining ballots to guarantee their victory regardless of how the other candidates receive votes.

Formally, solve the following problem for each i = 1,2,\ldots,N.

Determine if there is a non-negative integer X not exceeding K - \displaystyle{\sum_{i=1}^{N}} A_i satisfying the following condition. If it exists, find the minimum possible such integer.

  • If candidate i receives X additional votes, then candidate i will always be elected.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{12}
  • 0 \leq A_i \leq 10^{12}
  • \displaystyle{\sum_{i=1}^{N} A_i} \leq K
  • All input values are integers.

Input

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

N M K
A_1 A_2 \ldots A_N

Output

Let C_i be the minimum number of additional votes candidate i needs from the remaining ballots to guarantee their victory regardless of how other candidates receive votes. Print C_1, C_2, \ldots, C_N separated by spaces.

If candidate i has already secured their victory, then let C_i = 0. If candidate i cannot secure their victory under any circumstances, then let C_i = -1.


Sample Input 1

5 2 16
3 1 4 1 5

Sample Output 1

2 -1 1 -1 0

14 votes have been counted so far, and 2 votes are left.
The C to output is (2, -1, 1, -1, 0). For example:

  • Candidate 1 can secure their victory by obtaining 2 more votes, while not by obtaining 1 more vote. Thus, C_1 = 2.
  • Candidate 2 can never (even if they obtain 2 more votes) secure their victory, so C_2 = -1.

Sample Input 2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

Sample Output 2

79 89 111 117 117 74 112 116 80 107 117 106
F - Knapsack with Diminishing Values

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 550

問題文

N 種類の品物があり、 i 種類目の品物の重みは w_i、価値は v_i です。どの種類の品物も 10^{10} 個ずつあります。

高橋君はこれから、品物をいくつか選んで、容量 W のバッグに入れます。高橋君は、選ぶ品物の価値を大きくしつつ、同じ種類の品物ばかりにならないようにしたいです。そこで高橋君は、i 種類目の品物を k_i 個選んだときの うれしさk_i v_i - k_i^2 と定義したとき、選んだ品物の重さの総和を W 以下にしつつ、各種類のうれしさの総和が最大になるように品物を選びます。高橋君が達成できる、うれしさの総和の最大値を求めてください。

制約

  • 1 \leq N \leq 3000
  • 1 \leq W \leq 3000
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^9
  • 入力はすべて整数

入力

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

N W
w_1 v_1
w_2 v_2
\vdots
w_N v_N

出力

答えを出力せよ。


入力例 1

2 10
3 4
3 2

出力例 1

5

1 種類目の品物を 2 個、2 種類目の品物を 1 個選ぶと、うれしさの総和を 5 にすることができ、これが最適です。 1 種類目の品物についてのうれしさは 2 \times 4 - 2^2 = 42 種類目の品物についてのうれしさは 1 \times 2 - 1^2 = 1 です。 また、重さの総和は 9 であり、容量 10 のバッグに入ります。


入力例 2

3 6
1 4
2 3
2 7

出力例 2

14

入力例 3

1 10
1 7

出力例 3

12

Score : 550 points

Problem Statement

There are N types of items. The i-th type of item has a weight of w_i and a value of v_i. Each type has 10^{10} items available.

Takahashi is going to choose some items and put them into a bag with capacity W. He wants to maximize the value of the selected items while avoiding choosing too many items of the same type. Hence, he defines the happiness of choosing k_i items of type i as k_i v_i - k_i^2. He wants to choose items to maximize the total happiness over all types while keeping the total weight at most W. Calculate the maximum total happiness he can achieve.

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq W \leq 3000
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^9
  • All input values are integers.

Input

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

N W
w_1 v_1
w_2 v_2
\vdots
w_N v_N

Output

Print the answer.


Sample Input 1

2 10
3 4
3 2

Sample Output 1

5

By choosing 2 items of type 1 and 1 item of type 2, the total happiness can be 5, which is optimal.

Here, the happiness for type 1 is 2 \times 4 - 2^2 = 4, and the happiness for type 2 is 1 \times 2 - 1^2 = 1.

The total weight is 9, which is within the capacity 10.


Sample Input 2

3 6
1 4
2 3
2 7

Sample Output 2

14

Sample Input 3

1 10
1 7

Sample Output 3

12
G - No Cross Matching

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

2 次元平面上に P_1,P_2,\ldots,P_N, Q_1,Q_2,\ldots,Q_N2N 個の点があります。 P_i の座標は (A_i,B_i)Q_i の座標は (C_i,D_i) です。 同一直線上に異なる 3 点が存在することはありません。

(1,2,\ldots,N) の順列であるような数列 R=(R_1,R_2,\ldots,R_N) であって以下の条件を満たすような R が存在するか判定し、存在する場合は 1 つ求めてください。

  • 1 以上 N 以下のすべての整数 i について 線分 iP_iQ_{R_i} を端点とする線分としたとき、どの線分 i と線分 j (1 \leq i < j \leq N) も互いに交差しない。

制約

  • 1 \leq N \leq 300
  • 0 \leq A_i,B_i,C_i,D_i \leq 5000 (1 \leq i \leq N)
  • (A_i,B_i) \neq (A_j,B_j) (1 \leq i < j \leq N)
  • (C_i,D_i) \neq (C_j,D_j) (1 \leq i < j \leq N)
  • (A_i,B_i) \neq (C_j,D_j) (1 \leq i,j \leq N)
  • 同一直線上に異なる 3 点が存在することはない
  • 入力はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots 
A_N B_N
C_1 D_1
C_2 D_2
\vdots
C_N D_N

出力

条件を満たす R が存在しない場合は -1 と出力せよ。

存在する場合は R_1,R_2,\ldots,R_N を空白区切りで出力せよ。答えが複数存在する場合はどれを出力してもかまわない。


入力例 1

3
0 0
2 4
4 2
0 2
2 0
4 4

出力例 1

2 1 3

以下の図のように点が並んでいます。 R=(2,1,3) とすることで 3 本の線分は互いに交差しません。また、 R(1,2,3),(1,3,2),(2,3,1),(3,1,2) のいずれにしても正しい答えとなります。


入力例 2

8
59 85
60 57
72 12
3 27
16 58
41 94
77 64
97 20
32 37
7 2
57 94
35 70
38 60
97 100
5 76
38 8

出力例 2

3 5 8 2 7 4 6 1

Score : 600 points

Problem Statement

There are 2N points P_1,P_2,\ldots,P_N, Q_1,Q_2,\ldots,Q_N on a two-dimensional plane. The coordinates of P_i are (A_i, B_i), and the coordinates of Q_i are (C_i, D_i). No three different points lie on the same straight line.

Determine whether there exists a permutation R = (R_1, R_2, \ldots, R_N) of (1, 2, \ldots, N) that satisfies the following condition. If such an R exists, find one.

  • For each integer i from 1 through N, let segment i be the line segment connecting P_i and Q_{R_i}. Then, segment i and segment j (1 \leq i < j \leq N) never intersect.

Constraints

  • 1 \leq N \leq 300
  • 0 \leq A_i, B_i, C_i, D_i \leq 5000 (1 \leq i \leq N)
  • (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq N)
  • (C_i, D_i) \neq (C_j, D_j) (1 \leq i < j \leq N)
  • (A_i, B_i) \neq (C_j, D_j) (1 \leq i, j \leq N)
  • No three different points lie on the same straight line.
  • All input values are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots 
A_N B_N
C_1 D_1
C_2 D_2
\vdots
C_N D_N

Output

If there is no R satisfying the condition, print -1.

If such an R exists, print R_1, R_2, \ldots, R_N separated by spaces. If there are multiple solutions, you may print any of them.


Sample Input 1

3
0 0
2 4
4 2
0 2
2 0
4 4

Sample Output 1

2 1 3

The points are arranged as shown in the following figure.

By setting R = (2, 1, 3), the three line segments do not cross each other. Also, any of R = (1, 2, 3), (1, 3, 2), (2, 3, 1), and (3, 1, 2) is a valid answer.


Sample Input 2

8
59 85
60 57
72 12
3 27
16 58
41 94
77 64
97 20
32 37
7 2
57 94
35 70
38 60
97 100
5 76
38 8

Sample Output 2

3 5 8 2 7 4 6 1