Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正の整数 L に対して、 レベル L のダンゴ文字列とは、以下の条件を満たす文字列です。
oと-からなる長さ L+1 の文字列である。- 先頭の文字と末尾の文字のうちちょうど一方が
-であり、そのほかの L 文字はすべてoである。
例えば、ooo- はレベル 3 のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません（より正確には、どのような正の整数 L に対してもレベル L のダンゴ文字列ではありません）。
2 種類の文字 o - からなる、長さ N の文字列 S が与えられます。
次の条件を満たすような正整数 X のうち、最大のものを求めてください。
- S の連続する部分文字列であって、レベル X のダンゴ文字列であるものが存在する。
ただし、そのような整数が存在しない場合、-1 と出力してください。
制約
- 1\leq N\leq 2\times10^5
- S は
o-からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S にレベル X のダンゴ文字列が含まれるような最大の X の値を 1 行で出力せよ。
そのような値が存在しない場合、-1 を出力せよ。
入力例 1
10 o-oooo---o
出力例 1
4
たとえば、S の 3 文字目から 7 文字目までに対応する部分文字列 oooo- は、レベル 4 のダンゴ文字列です。
S の部分文字列であってレベル 5 以上のダンゴ文字列であるようなものは存在しないため、4 と出力してください。
入力例 2
1 -
出力例 2
-1
S の連続する部分文字列は空文字列と - の 2 種類だけです。
これらはダンゴ文字列ではないため、-1 と出力してください。
入力例 3
30 -o-o-oooo-oo-o-ooooooo--oooo-o
出力例 3
7
Score : 300 points
Problem Statement
For a positive integer L, a level-L dango string is a string that satisfies the following conditions.
- It is a string of length L+1 consisting of
oand-. - Exactly one of the first character and the last character is
-, and the other L characters areo.
For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).
You are given a string S of length N consisting of the two characters o and -.
Find the greatest positive integer X that satisfies the following condition.
- There is a contiguous substring of S that is a level-X dango string.
If there is no such integer, print -1.
Constraints
- 1\leq N\leq 2\times10^5
- S is a string of length N consisting of
oand-.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the greatest positive integer X such that S contains a level-X dango string, or -1 if there is no such integer.
Sample Input 1
10 o-oooo---o
Sample Output 1
4
For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string.
No substring of S is a level-5 dango string or above, so you should print 4.
Sample Input 2
1 -
Sample Output 2
-1
Only the empty string and - are the substrings of S.
They are not dango strings, so you should print -1.
Sample Input 3
30 -o-o-oooo-oo-o-ooooooo--oooo-o
Sample Output 3
7
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の商品があります。i = 1, 2, \ldots, N について、i 番目の商品の値段は A_i 円です。
高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも（ 0 枚でもよい）使用することができます。
値段が a 円の商品に対して k 枚のクーポンを使用すると、その商品を \max\lbrace a - kX, 0\rbrace 円で買うことができます。
高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K X A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 4 7 8 3 10 5 13
出力例 1
12
1 番目の商品に対してクーポン 1 枚、3 番目の商品に対してクーポン 1 枚、5 番目の商品に対してクーポン 2 枚を使用すると、
- 1 番目の商品を \max\lbrace A_1-X, 0 \rbrace = 1 円で買うことができ、
- 2 番目の商品を \max\lbrace A_2, 0 \rbrace = 3 円で買うことができ、
- 3 番目の商品を \max\lbrace A_3-X, 0 \rbrace = 3 円で買うことができ、
- 4 番目の商品を \max\lbrace A_4, 0 \rbrace = 5 円で買うことができ、
- 5 番目の商品を \max\lbrace A_5-2X, 0 \rbrace = 0 円で買うことができます。
よって、すべての商品を 1 + 3 + 3 + 5 + 0 = 12 円で買うことができ、これが最小です。
入力例 2
5 100 7 8 3 10 5 13
出力例 2
0
入力例 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
出力例 3
112
Score : 300 points
Problem Statement
There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).
Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.
Print the minimum amount of money Takahashi needs to buy all the items.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K X A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 4 7 8 3 10 5 13
Sample Output 1
12
By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:
- buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
- buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
- buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
- buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
- buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,
for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.
Sample Input 2
5 100 7 8 3 10 5 13
Sample Output 2
0
Sample Input 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
Sample Output 3
112
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
H \times W 枚のクッキーが H 行 W 列に並んでいます。
上から i 行目・左から j 列目のクッキーの色は英小文字 c_{i,j} で表されます。
これから、以下の手続きを行います。
1. 各行に対して次の操作を行う : その行に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。
2. 各列に対して次の操作を行う : その列に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。
3. 印のついたクッキーがあればそれらをすべて取り除いて 1. に戻り、なければ手続きを終了する。
手続きを終了した時点で残っているクッキーの枚数を求めてください。
制約
- 2 \leq H, W \leq 2000
- c_{i,j} は英小文字である
入力
入力は以下の形式で標準入力から与えられる。
H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}
出力
答えを出力せよ。
入力例 1
4 3 aaa aaa abc abd
出力例 1
2
以下で示す順で手続きを行います。
- 1. により、1, 2 行目のクッキーに印をつける。
- 2. により、1 列目のクッキーに印をつける。
- 3. により、印を付けたクッキーを取り除く。
この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。
... ... .bc .bd
- 1. により、何もしない。
- 2. により、2 列目のクッキーに印をつける。
- 3. により、印を付けたクッキーを取り除く。
この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。
... ... ..c ..d
- 1. により、何もしない。
- 2. により、何もしない。
- 3. により、印がついているクッキーが存在しないので手続きを終了する。
最終的に残っているクッキーの枚数は 2 枚です。
入力例 2
2 5 aaaaa abcde
出力例 2
4
入力例 3
3 3 ooo ooo ooo
出力例 3
0
Score : 400 points
Problem Statement
There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.
We will perform the following procedure.
1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.
2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.
3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.
Find the number of cookies remaining at the end of the procedure.
Constraints
- 2 \leq H, W \leq 2000
- c_{i,j} is a lowercase English letter.
Input
The input is given from Standard Input in the following format:
H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}
Output
Print the answer.
Sample Input 1
4 3 aaa aaa abc abd
Sample Output 1
2
The procedure is performed as follows.
- 1. Mark the cookies in the first and second rows.
- 2. Mark the cookies in the first column.
- 3. Remove the marked cookies.
At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.
... ... .bc .bd
- 1. Do nothing.
- 2. Mark the cookies in the second column.
- 3. Remove the marked cookies.
At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.
... ... ..c ..d
- 1. Do nothing.
- 2. Do nothing.
- 3. No cookies are marked, so terminate the procedure.
The final number of cookies remaining is 2.
Sample Input 2
2 5 aaaaa abcde
Sample Output 2
4
Sample Input 3
3 3 ooo ooo ooo
Sample Output 3
0
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
ある国には N 個の都市と M 個の発電所があります。これらを総称して地点と呼びます。
地点には 1,2,\dots,N+M の番号がつけられており、そのうち都市は地点 1,2,\dots,N で発電所は地点 N+1,N+2,\dots,N+M です。
この国には電線が E 本あり、電線 i ( 1 \le i \le E ) は地点 U_i と地点 V_i を双方向に結びます。
また、ある都市に 電気が通っている とは、ある都市から電線をいくつか辿って少なくともひとつの発電所に辿り着くことができる状態を言います。
今、 Q 個のイベントが起こります。そのうち i ( 1 \le i \le Q ) 番目のイベントでは電線 X_i が切れ、その電線を辿ることができなくなります。一度切れた電線は、その後のイベントにおいても切れたままです。
全てのイベントについて、そのイベントが終わった直後に電気が通っている都市の数を求めてください。
制約
- 入力は全て整数
- 1 \le N,M
- N+M \le 2 \times 10^5
- 1 \le Q \le E \le 5 \times 10^5
- 1 \le U_i < V_i \le N+M
- i \neq j ならば、 U_i \neq U_j または V_i \neq V_j
- 1 \le X_i \le E
- X_i は相異なる
入力
入力は以下の形式で標準入力から与えられる。
N M E U_1 V_1 U_2 V_2 \vdots U_E V_E Q X_1 X_2 \vdots X_Q
出力
Q 行出力せよ。
そのうち i ( 1 \le i \le Q ) 行目には i 番目のイベントが終わった直後に電気が通っている都市の数を出力せよ。
入力例 1
5 5 10 2 3 4 10 5 10 6 9 2 9 4 8 1 7 3 6 8 10 1 8 6 3 5 8 10 2 7
出力例 1
4 4 2 2 2 1
はじめ、全ての都市に電気が通っています。
- 1 番目のイベントによって地点 5 と地点 10 を結ぶ電線 3 が切れます。
- これにより、都市 5 に電気が通らなくなり、電気が通っている都市の数は 4 となります。
- 2 番目のイベントによって地点 2 と地点 9 を結ぶ電線 5 が切れます。
- 3 番目のイベントによって地点 3 と地点 6 を結ぶ電線 8 が切れます。
- これにより、都市 2,3 に電気が通らなくなり、電気が通っている都市の数は 2 となります。
- 4 番目のイベントによって地点 1 と地点 8 を結ぶ電線 10 が切れます。
- 5 番目のイベントによって地点 4 と地点 10 を結ぶ電線 2 が切れます。
- 6 番目のイベントによって地点 1 と地点 7 を結ぶ電線 7 が切れます。
- これにより、都市 1 に電気が通らなくなり、電気が通っている都市の数は 1 となります。
Score : 500 points
Problem Statement
A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.
This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.
Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.
Find the number of electrified cities right after each events.
Constraints
- All values in input are integers.
- 1 \le N,M
- N+M \le 2 \times 10^5
- 1 \le Q \le E \le 5 \times 10^5
- 1 \le U_i < V_i \le N+M
- If i \neq j, then U_i \neq U_j or V_i \neq V_j.
- 1 \le X_i \le E
- X_i are distinct.
Input
Input is given from Standard Input in the following format:
N M E U_1 V_1 U_2 V_2 \vdots U_E V_E Q X_1 X_2 \vdots X_Q
Output
Print Q lines.
The i-th line should contain the number of electrified cities right after the i-th event.
Sample Input 1
5 5 10 2 3 4 10 5 10 6 9 2 9 4 8 1 7 3 6 8 10 1 8 6 3 5 8 10 2 7
Sample Output 1
4 4 2 2 2 1
Initially, all cities are electrified.
- The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
- Now City 5 is no longer electrified, while 4 cities remain electrified.
- The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
- The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
- Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
- The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
- The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
- The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
- Now City 1 is no longer electrified, while 1 city remains electrified.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
縦の長さが A、横の長さが B の長方形の内部に描ける正三角形の一辺の長さの最大値を求めてください。
制約
- 1 \leq A,B \leq 1000
- A,B は整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解として扱われる。
入力例 1
1 1
出力例 1
1.03527618041008295791
下図のように描くのが最適で、一辺の長さが \sqrt{6} - \sqrt{2} になります。
なお、この出力例の値は \sqrt{6}- \sqrt{2} と厳密には一致しませんが、誤差が 10^{-9} 以下なので正解として扱われます。
Score : 500 points
Problem Statement
Find the maximum side length of a regular triangle that can be drawn within a rectangle whose side lengths are A and B.
Constraints
- 1 \leq A,B \leq 1000
- A and B are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Your output is considered correct if the absolute or relative error from the true answer is at most 10^{-9}.
Sample Input 1
1 1
Sample Output 1
1.03527618041008295791
The following figure shows an optimal drawing, with the side length of \sqrt{6} - \sqrt{2}.
Note that the sample output does not strictly match \sqrt{6}- \sqrt{2}, but the error is within 10^{-9}, so it is considered correct.