Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
AtCoder 町の、ある連続した 3 日間の天気の記録があります。天気の記録は長さ 3 の文字列 S で表され、i (1 \leq i \leq 3) 日目の天気は i 文字目が S
のとき晴れ、R
のとき雨でした。
天気が雨である日が連続していた最大の日数を求めてください。
制約
- |S| = 3
- S の各文字は
S
またはR
である
入力
入力は以下の形式で標準入力から与えられる。
S
出力
天気が雨である日が連続していた最大の日数を出力せよ。
入力例 1
RRS
出力例 1
2
3 日間のうち、1, 2 日目が雨で、最大では 2 日間雨である日が連続していたので 2 を出力してください。
入力例 2
SSS
出力例 2
0
3 日間のうち、3 日とも晴れでした。雨である日は無かったため、0 を出力してください。
入力例 3
RSR
出力例 3
1
3 日間のうち、1, 3 日目が雨でした。共に 1 日雨である日が連続していたので、1 を出力してください。
Score : 100 points
Problem Statement
We have weather records at AtCoder Town for some consecutive three days. A string of length 3, S, represents the records - if the i-th character is S
, it means it was sunny on the i-th day; if that character is R
, it means it was rainy on that day.
Find the maximum number of consecutive rainy days in this period.
Constraints
- |S| = 3
- Each character of S is
S
orR
.
Input
Input is given from Standard Input in the following format:
S
Output
Print the maximum number of consecutive rainy days in the period.
Sample Input 1
RRS
Sample Output 1
2
We had rain on the 1-st and 2-nd days in the period. Here, the maximum number of consecutive rainy days is 2, so we should print 2.
Sample Input 2
SSS
Sample Output 2
0
It was sunny throughout the period. We had no rainy days, so we should print 0.
Sample Input 3
RSR
Sample Output 3
1
We had rain on the 1-st and 3-rd days - two "streaks" of one rainy day, so we should print 1.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
1, \cdots, N の番号がついた N 本の棒があります。棒 i (1 \leq i \leq N) の長さは L_i です。
このうち、三角形を作ることのできるような長さの異なる 3 本の棒を選ぶ方法は何通りあるでしょうか。
つまり、3 つの整数 1 \leq i < j < k \leq N の組であって次の 2 つの条件の両方を満たすものの個数を求めてください。
- L_i, L_j, L_k がすべて異なる
- 3 辺の長さが L_i, L_j, L_k であるような三角形が存在する
制約
- 1 \leq N \leq 100
- 1 \leq L_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N L_1 L_2 \cdots L_N
出力
三角形を作ることのできるような、長さの異なる 3 本の棒を選ぶ方法の個数を出力せよ。
入力例 1
5 4 4 9 7 5
出力例 1
5
条件を満たすような (i, j, k) は、(1, 3, 4), (1, 4, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5) の 5 個があります。
入力例 2
6 4 5 4 3 3 5
出力例 2
8
長さ 3, 4, 5 の棒が 2 本ずつあります。1 つ目の条件を満たすためにはそれぞれから 1 本ずつ選ぶしかありません。
3 辺の長さが 3, 4, 5 の三角形は存在するので、条件を満たすような (i, j, k) は 2 ^ 3 = 8 個あります。
入力例 3
10 9 4 6 1 9 6 10 6 6 8
出力例 3
39
入力例 4
2 1 1
出力例 4
0
1 \leq i < j < k \leq N を満たす (i, j, k) が存在しないので、0 を出力してください。
Score : 200 points
Problem Statement
We have sticks numbered 1, \cdots, N. The length of Stick i (1 \leq i \leq N) is L_i.
In how many ways can we choose three of the sticks with different lengths that can form a triangle?
That is, find the number of triples of integers (i, j, k) (1 \leq i < j < k \leq N) that satisfy both of the following conditions:
- L_i, L_j, and L_k are all different.
- There exists a triangle whose sides have lengths L_i, L_j, and L_k.
Constraints
- 1 \leq N \leq 100
- 1 \leq L_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L_1 L_2 \cdots L_N
Output
Print the number of ways to choose three of the sticks with different lengths that can form a triangle.
Sample Input 1
5 4 4 9 7 5
Sample Output 1
5
The following five triples (i, j, k) satisfy the conditions: (1, 3, 4), (1, 4, 5), (2, 3, 4), (2, 4, 5), and (3, 4, 5).
Sample Input 2
6 4 5 4 3 3 5
Sample Output 2
8
We have two sticks for each of the lengths 3, 4, and 5. To satisfy the first condition, we have to choose one from each length.
There is a triangle whose sides have lengths 3, 4, and 5, so we have 2 ^ 3 = 8 triples (i, j, k) that satisfy the conditions.
Sample Input 3
10 9 4 6 1 9 6 10 6 6 8
Sample Output 3
39
Sample Input 4
2 1 1
Sample Output 4
0
No triple (i, j, k) satisfies 1 \leq i < j < k \leq N, so we should print 0.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数直線上で暮らす高橋君は、今座標 X にいます。これから高橋君はちょうど K 回、座標の正または負の方向に D 移動する行為を繰り返そうと考えています。
より正確には、1 回の移動では 座標 x から x + D または x - D に移動できます。
高橋君は、ちょうど K 回移動した後にいる座標の絶対値が最小となるように移動したいです。
K 回の移動後の座標の絶対値としてあり得る値の最小値を求めてください。
制約
- -10^{15} \leq X \leq 10^{15}
- 1 \leq K \leq 10^{15}
- 1 \leq D \leq 10^{15}
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
X K D
出力
K 回の移動後の座標の絶対値としてあり得る値の最小値を出力せよ。
入力例 1
6 2 4
出力例 1
2
高橋君は、今座標 6 にいます。次のように移動するのが最適です。
- 6 から (6 - 4 =) 2 に移動する。
- 2 から (2 - 4 =) -2 に移動する。
移動後の座標の絶対値は 2 で、これより小さくすることはできません。
入力例 2
7 4 3
出力例 2
1
高橋君は、今座標 7 にいます。例えば次のように移動するのが最適です。
- 7 から 4 に移動する。
- 4 から 7 に移動する。
- 7 から 4 に移動する。
- 4 から 1 に移動する。
移動後の座標の絶対値は 1 で、これより小さくすることはできません。
入力例 3
10 1 2
出力例 3
8
入力例 4
1000000000000000 1000000000000000 1000000000000000
出力例 4
1000000000000000
答えは非常に大きな値になる場合もあります。
Score : 300 points
Problem Statement
Takahashi, who lives on the number line, is now at coordinate X. He will make exactly K moves of distance D in the positive or negative direction.
More specifically, in one move, he can go from coordinate x to x + D or x - D.
He wants to make K moves so that the absolute value of the coordinate of the destination will be the smallest possible.
Find the minimum possible absolute value of the coordinate of the destination.
Constraints
- -10^{15} \leq X \leq 10^{15}
- 1 \leq K \leq 10^{15}
- 1 \leq D \leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X K D
Output
Print the minimum possible absolute value of the coordinate of the destination.
Sample Input 1
6 2 4
Sample Output 1
2
Takahashi is now at coordinate 6. It is optimal to make the following moves:
- Move from coordinate 6 to (6 - 4 =) 2.
- Move from coordinate 2 to (2 - 4 =) -2.
Here, the absolute value of the coordinate of the destination is 2, and we cannot make it smaller.
Sample Input 2
7 4 3
Sample Output 2
1
Takahashi is now at coordinate 7. It is optimal to make, for example, the following moves:
- Move from coordinate 7 to 4.
- Move from coordinate 4 to 7.
- Move from coordinate 7 to 4.
- Move from coordinate 4 to 1.
Here, the absolute value of the coordinate of the destination is 1, and we cannot make it smaller.
Sample Input 3
10 1 2
Sample Output 3
8
Sample Input 4
1000000000000000 1000000000000000 1000000000000000
Sample Output 4
1000000000000000
The answer can be enormous.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋君は 1, 2, \cdots, N の番号のついた N マスから成るマス目の上で、コマを使ってゲームを行おうとしています。マス i には整数 C_i が書かれています。また、1, 2 …, N の順列 P_1, P_2, \cdots, P_N が与えられています。
これから高橋君は好きなマスを 1 つ選んでコマを 1 つ置き、1 回以上 K 回以下の好きな回数だけ、次のような方法でコマを移動させます。
- 1 回の移動では、現在コマがマス i (1 \leq i \leq N) にあるなら、コマをマス P_i に移動させる。このとき、スコアに C_{P_i} が加算される。
高橋君のために、ゲーム終了時のスコアとしてあり得る値の最大値を求めてください。(ゲーム開始時のスコアは 0 です。)
制約
- 2 \leq N \leq 5000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq N
- P_i \neq i
- P_1, P_2, \cdots, P_N は全て異なる
- -10^9 \leq C_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K P_1 P_2 \cdots P_N C_1 C_2 \cdots C_N
出力
ゲーム終了時のスコアとしてあり得る値の最大値を出力せよ。
入力例 1
5 2 2 4 5 1 3 3 4 -10 -8 8
出力例 1
8
好きなマスから始めて 2 回以下コマを移動させる方法は以下の通りです。
- 初めマス 1 にコマを置く場合。1 回移動するとマス 2 に動き、スコアが 4 になる。2 回移動するとマス 4 に動き、スコアが 4 + (-8) = -4 になる。
- 初めマス 2 にコマを置く場合。1 回移動するとマス 4 に動き、スコアが -8 になる。2 回移動するとマス 1 に動き、スコアが -8 + 3 = -5 になる。
- 初めマス 3 にコマを置く場合。1 回移動するとマス 5 に動き、スコアが 8 になる。2 回移動するとマス 3 に動き、スコアが 8 + (-10) = -2 になる。
- 初めマス 4 にコマを置く場合。1 回移動するとマス 1 に動き、スコアが 3 になる。2 回移動するとマス 2 に動き、スコアが 3 + 4 = 7 になる。
- 初めマス 5 にコマを置く場合。1 回移動するとマス 3 に動き、スコアが -10 になる。2 回移動するとマス 5 に動き、スコアが -10 + 8 = -2 になる。
これらの最大値は 8 です。
入力例 2
2 3 2 1 10 -7
出力例 2
13
入力例 3
3 3 3 1 2 -1000 -2000 -3000
出力例 3
-1000
最低 1 回はコマを移動させる必要があります。
入力例 4
10 58 9 1 6 7 8 4 3 2 10 5 695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
出力例 4
29507023469
答えの絶対値は非常に大きくなる場合があります。
Score : 400 points
Problem Statement
Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.
Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):
- In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.
Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)
Constraints
- 2 \leq N \leq 5000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq N
- P_i \neq i
- P_1, P_2, \cdots, P_N are all different.
- -10^9 \leq C_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K P_1 P_2 \cdots P_N C_1 C_2 \cdots C_N
Output
Print the maximum possible score at the end of the game.
Sample Input 1
5 2 2 4 5 1 3 3 4 -10 -8 8
Sample Output 1
8
When we start at some square of our choice and make at most two moves, we have the following options:
- If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.
- If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.
- If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.
- If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.
- If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.
The maximum score achieved is 8.
Sample Input 2
2 3 2 1 10 -7
Sample Output 2
13
Sample Input 3
3 3 3 1 2 -1000 -2000 -3000
Sample Output 3
-1000
We have to make at least one move.
Sample Input 4
10 58 9 1 6 7 8 4 3 2 10 5 695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
Sample Output 4
29507023469
The absolute value of the answer may be enormous.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
R 行 C 列に並んだマス目に K 個のアイテムが置いてあります。1 \leq i \leq R 行目、 1 \leq j \leq C 列目のマスを (i, j) と表すとき、i 番目のアイテムはマス (r_i, c_i) に存在し、その価値は v_i です。
高橋君はマス (1, 1) からスタートしてゴールのマス (R, C) まで移動します。高橋君はマス (i, j) にいるとき、次には (存在すれば) マス (i + 1, j) またはマス (i, j + 1) に移動することができます。
高橋君は通ったマス (スタートとゴールも含む) のアイテムを拾うことができます。ただし、マス目の同じ行では 3 個までしかアイテムを拾うことができません。通ったマスにアイテムがある場合に、そのアイテムを拾わないことはできます。
高橋君が拾うことのできるアイテムの価値の合計としてありうる値の最大値を求めてください。
制約
- 1 \leq R, C \leq 3000
- 1 \leq K \leq \min(2 \times 10^5, R \times C)
- 1 \leq r_i \leq R
- 1 \leq c_i \leq C
- (r_i, c_i) \neq (r_j, c_j) (i \neq j)
- 1 \leq v_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
R C K r_1 c_1 v_1 r_2 c_2 v_2 : r_K c_K v_K
出力
高橋君が拾うことのできるアイテムの価値の合計としてありうる値の最大値を出力せよ。
入力例 1
2 2 3 1 1 3 2 1 4 1 2 5
出力例 1
8
移動の方法は以下の 2 通りあります。
- マス (1, 1) 、マス (1, 2)、マス (2, 2) の順に移動する。このとき拾うことのできるアイテムの価値の合計は 3 + 5 = 8 である。
- マス (1, 1) 、マス (2, 1)、マス (2, 2) の順に移動する。このとき拾うことのできるアイテムの価値の合計は 3 + 4 = 7 である。
よって、高橋君が拾うことのできるアイテムの価値の合計としてありうる値の最大値は 8 です。
入力例 2
2 5 5 1 1 3 2 4 20 1 2 1 1 3 4 1 4 2
出力例 2
29
1 行目にアイテムが 4 個あります。次のように移動してアイテムを拾う方法が最適です。
- マス (1, 1) 、マス (1, 2)、マス (1, 3)、マス (1, 4) 、マス (2, 4)、マス (2, 5) の順に移動する。このうちマス (1, 2) にあるアイテムのみ拾わないことにすると、アイテムの価値の合計は 3 + 4 + 2 + 20 = 29 である。
入力例 3
4 5 10 2 5 12 1 5 12 2 3 15 1 2 20 1 1 28 2 4 26 3 2 27 4 5 21 3 5 10 1 3 10
出力例 3
142
Score : 500 points
Problem Statement
There are K items placed on a grid of squares with R rows and C columns. Let (i, j) denote the square at the i-th row (1 \leq i \leq R) and the j-th column (1 \leq j \leq C). The i-th item is at (r_i, c_i) and has the value v_i.
Takahashi will begin at (1, 1), the start, and get to (R, C), the goal. When he is at (i, j), he can move to (i + 1, j) or (i, j + 1) (but cannot move to a non-existent square).
He can pick up items on the squares he visits, including the start and the goal, but at most three for each row. It is allowed to ignore the item on a square he visits.
Find the maximum possible sum of the values of items he picks up.
Constraints
- 1 \leq R, C \leq 3000
- 1 \leq K \leq \min(2 \times 10^5, R \times C)
- 1 \leq r_i \leq R
- 1 \leq c_i \leq C
- (r_i, c_i) \neq (r_j, c_j) (i \neq j)
- 1 \leq v_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
R C K r_1 c_1 v_1 r_2 c_2 v_2 : r_K c_K v_K
Output
Print the maximum possible sum of the values of items Takahashi picks up.
Sample Input 1
2 2 3 1 1 3 2 1 4 1 2 5
Sample Output 1
8
He has two ways to get to the goal:
- Visit (1, 1), (1, 2), and (2, 2), in this order. In this case, the total value of the items he can pick up is 3 + 5 = 8.
- Visit (1, 1), (2, 1), and (2, 2), in this order. In this case, the total value of the items he can pick up is 3 + 4 = 7.
Thus, the maximum possible sum of the values of items he picks up is 8.
Sample Input 2
2 5 5 1 1 3 2 4 20 1 2 1 1 3 4 1 4 2
Sample Output 2
29
We have four items in the 1-st row. The optimal choices are as follows:
- Visit (1, 1) (1, 2), (1, 3), (1, 4), (2, 4), and (2, 5), in this order, and pick up all items except the one on (1, 2). Then, the total value of the items he picks up will be 3 + 4 + 2 + 20 = 29.
Sample Input 3
4 5 10 2 5 12 1 5 12 2 3 15 1 2 20 1 1 28 2 4 26 3 2 27 4 5 21 3 5 10 1 3 10
Sample Output 3
142
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
英小文字から成る N 個の文字列 S_1, S_2, \cdots, S_N があります。
高橋君はまずこれらの文字列から重複を許して合計 1 個以上選んだ後、選んだ文字列を好きな順番で連結することで、回文であるような文字列を作ろうとしています。
文字列 S_i を 1 個使うにはコストが C_i かかり、同じ文字列であっても使った個数の分だけコストがかかります。
上述の方法で回文を作ることのできるように文字列を選ぶ方法のうち、コストの和としてありうる値の最小値を求めてください。
また、どのように選んでも回文を作ることが不可能である場合は -1 を出力してください。
制約
- 1 \leq N \leq 50
- 1 \leq |S_i| \leq 20
- S_i は英小文字から成る
- 1 \leq C_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N S_1 C_1 S_2 C_2 : S_N C_N
出力
回文を作ることのできるように文字列を選ぶ方法のうち、コストの和としてありうる値の最小値を出力せよ。不可能である場合は -1 を出力せよ。
入力例 1
3 ba 3 abc 4 cbaa 5
出力例 1
7
ba
, abc
, cbaa
があります。
例えば、ba
, abc
を 1 個ずつ使うとコストは 7 で、abc
, ba
の順で連結すると回文になります。
また、abc
, cbaa
を 1 個ずつ使うとコストは 9 で、cbaa
, abc
の順で連結すると回文になります。
コスト 7 未満で回文を作ることはできないので、7 を出力してください。
入力例 2
2 abcab 5 cba 3
出力例 2
11
abcab
を 1 個、cba
を 2 個選んで、abcab
, cba
, cba
の順で連結すると回文になり、コストは 11 です。
入力例 3
4 ab 5 cba 3 a 12 ab 10
出力例 3
8
a
を 1 個だけ選んで回文とすることもできますが、ab
と cba
を選んで連結する方がコストが小さいです。
入力例 4
2 abc 1 ab 2
出力例 4
-1
回文を作ることが不可能であるので、-1 を出力してください。
Score : 600 points
Problem Statement
We have N strings of lowercase English letters: S_1, S_2, \cdots, S_N.
Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.
The cost of using the string S_i once is C_i, and the cost of using it multiple times is C_i multiplied by that number of times.
Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.
If there is no choice of strings in which he can make a palindrome, print -1.
Constraints
- 1 \leq N \leq 50
- 1 \leq |S_i| \leq 20
- S_i consists of lowercase English letters.
- 1 \leq C_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N S_1 C_1 S_2 C_2 : S_N C_N
Output
Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or -1 if there is no such choice.
Sample Input 1
3 ba 3 abc 4 cbaa 5
Sample Output 1
7
We have ba
, abc
, and cbaa
.
For example, we can use ba
once and abc
once for a cost of 7, then concatenate them in the order abc
, ba
to make a palindrome.
Also, we can use abc
once and cbaa
once for a cost of 9, then concatenate them in the order cbaa
, abc
to make a palindrome.
We cannot make a palindrome for a cost less than 7, so we should print 7.
Sample Input 2
2 abcab 5 cba 3
Sample Output 2
11
We can choose abcab
once and cba
twice, then concatenate them in the order abcab
, cba
, cba
to make a palindrome for a cost of 11.
Sample Input 3
4 ab 5 cba 3 a 12 ab 10
Sample Output 3
8
We can choose a
once, which is already a palindrome, but it is cheaper to concatenate ab
and cba
.
Sample Input 4
2 abc 1 ab 2
Sample Output 4
-1
We cannot make a palindrome, so we should print -1.