Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
高橋くんはプログラミングコンテストに出ていますが， YES か NO で答える問題でTLEしてしまいました。
提出の詳細を見ると，テストケースは全てで N ケースあり，そのうち M ケースでTLEしていました。
そこで高橋くんは, M ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し， 残りの N-M ケースではそれぞれ実行に 100 ms かかって必ず正解するプログラムへ書き換えました。
そして，以下の操作を行います。
- このプログラムを提出する。
- 全てのケースの実行が終わるまで待機する。
- もし M ケースのうちどれかで不正解だった場合，もう一度プログラムを提出する。
- これを，一度で全てのケースに正解するまで繰り返す。
この操作が終了するまでの，プログラムの実行時間の総和の期待値を X msとした時，X を出力してください。
なお，X は整数で出力してください。
制約
- 入力は全て整数
- 1 \leq N \leq 100
- 1 \leq M \leq {\rm min}(N, 5)
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
実行時間の総和の期待値 X を整数で出力してください。 なお，X はこの問題の制約下で，10^9 以下の整数となることが証明できます。
入力例 1
1 1
出力例 1
3800
この入力だとケースは 1 ケースだけであり，1900 ms かかって 1/2 の確率で正解するプログラムを投げ続けます。
つまり 1 回で正解する確率は 1/2, 2 回で正解する確率は 1/4, 3 回で正解する確率は 1/8 です。
よって答えは 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800 です。
入力例 2
10 2
出力例 2
18400
2 ケースで 1900 ms かかり，10-2=8 ケースで 100 ms かかるプログラムを投げ続けます。 全てのケースで正解する確率は 1/2 \times 1/2 = 1/4 です。
入力例 3
100 5
出力例 3
608000
Score : 300 points
Problem Statement
Takahashi is now competing in a programming contest, but he received TLE in a problem where the answer is YES or NO.
When he checked the detailed status of the submission, there were N test cases in the problem, and the code received TLE in M of those cases.
Then, he rewrote the code to correctly solve each of those M cases with 1/2 probability in 1900 milliseconds, and correctly solve each of the other N-M cases without fail in 100 milliseconds.
Now, he goes through the following process:
- Submit the code.
- Wait until the code finishes execution on all the cases.
- If the code fails to correctly solve some of the M cases, submit it again.
- Repeat until the code correctly solve all the cases in one submission.
Let the expected value of the total execution time of the code be X milliseconds. Print X (as an integer).
Constraints
- All input values are integers.
- 1 \leq N \leq 100
- 1 \leq M \leq {\rm min}(N, 5)
Input
Input is given from Standard Input in the following format:
N M
Output
Print X, the expected value of the total execution time of the code, as an integer. It can be proved that, under the constraints in this problem, X is an integer not exceeding 10^9.
Sample Input 1
1 1
Sample Output 1
3800
In this input, there is only one case. Takahashi will repeatedly submit the code that correctly solves this case with 1/2 probability in 1900 milliseconds.
The code will succeed in one attempt with 1/2 probability, in two attempts with 1/4 probability, and in three attempts with 1/8 probability, and so on.
Thus, the answer is 1900 \times 1/2 + (2 \times 1900) \times 1/4 + (3 \times 1900) \times 1/8 + ... = 3800.
Sample Input 2
10 2
Sample Output 2
18400
The code will take 1900 milliseconds in each of the 2 cases, and 100 milliseconds in each of the 10-2=8 cases. The probability of the code correctly solving all the cases is 1/2 \times 1/2 = 1/4.
Sample Input 3
100 5
Sample Output 3
608000
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
N 枚のカードからなる山札があります。カードにはそれぞれ数が書かれており， 上から i 枚目には a_i が書かれています。
この山札を使い，X さんと Y さんが 2 人でゲームをします。 X, Y さんは最初，Z, W が書かれたカードを持っています。 そして X さんから交互に以下を行います。
- 山札から何枚かカードを引く。そして今持っているカードを捨て，最後に引いたカードを代わりに持つ。ただし，必ず 1 枚は引かなくてはならない。
山札がなくなるとゲームは終了で，2 人の持っているカードに書かれた数の差の絶対値がこのゲームのスコアになります。
X さんはスコアを最大化するように，Y さんはスコアを最小化するようにゲームをプレイした時， スコアはいくつになるでしょうか？
制約
- 入力は全て整数
- 1 \leq N \leq 2000
- 1 \leq Z, W, a_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N Z W a_1 a_2 ... a_N
出力
求めたスコアを出力してください。
入力例 1
3 100 100 10 1000 100
出力例 1
900
X さんが最初に 2 枚カードを引くと，次に Y さんが最後のカードを引き，スコアは |1000 - 100| = 900 になります。
入力例 2
3 100 1000 10 100 100
出力例 2
900
X さんが最初に全てのカードを引くと，スコアは |100 - 1000| = 900 になります。
入力例 3
5 1 1 1 1 1 1 1
出力例 3
0
入力例 4
1 1 1 1000000000
出力例 4
999999999
Score : 500 points
Problem Statement
We have a deck consisting of N cards. Each card has an integer written on it. The integer on the i-th card from the top is a_i.
Two people X and Y will play a game using this deck. Initially, X has a card with Z written on it in his hand, and Y has a card with W written on it in his hand. Then, starting from X, they will alternately perform the following action:
- Draw some number of cards from the top of the deck. Then, discard the card in his hand and keep the last drawn card instead. Here, at least one card must be drawn.
The game ends when there is no more card in the deck. The score of the game is the absolute difference of the integers written on the cards in the two players' hand.
X will play the game so that the score will be maximized, and Y will play the game so that the score will be minimized. What will be the score of the game?
Constraints
- All input values are integers.
- 1 \leq N \leq 2000
- 1 \leq Z, W, a_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N Z W a_1 a_2 ... a_N
Output
Print the score.
Sample Input 1
3 100 100 10 1000 100
Sample Output 1
900
If X draws two cards first, Y will draw the last card, and the score will be |1000 - 100| = 900.
Sample Input 2
3 100 1000 10 100 100
Sample Output 2
900
If X draws all the cards first, the score will be |1000 - 100| = 900.
Sample Input 3
5 1 1 1 1 1 1 1
Sample Output 3
0
Sample Input 4
1 1 1 1000000000
Sample Output 4
999999999
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
宝石が N 個あり，それぞれ 1, 2, ..., N と数が書かれています。
あなたは，以下の操作を好きなだけ行うことが出来ます(一度も行わなくてもよいです)。
- 正整数 x を選ぶ。x の倍数が書かれた宝石を全て叩き割る。
そして，i が書かれていた宝石が割られずに残っていた場合，a_i 円貰います。 ただし，この a_i は負の場合もあり，その場合はお金を払わなくてはいけません。
うまく操作を行った時，あなたは最大で何円お金を貰えるでしょうか？
制約
- 入力は全て整数
- 1 \leq N \leq 100
- |a_i| \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
出力
貰えるお金の最大値を出力してください。
入力例 1
6 1 2 -6 4 5 3
出力例 1
12
宝石 3, 6 を叩き割るのが最適です。
入力例 2
6 100 -100 -100 -100 100 -100
出力例 2
200
入力例 3
5 -1 -2 -3 -4 -5
出力例 3
0
全ての宝石を叩き割るのが最適です。
入力例 4
2 -1000 100000
出力例 4
99000
Score : 700 points
Problem Statement
We have N gemstones labeled 1 through N.
You can perform the following operation any number of times (possibly zero).
- Select a positive integer x, and smash all the gems labeled with multiples of x.
Then, for each i, if the gem labeled i remains without getting smashed, you will receive a_i yen (the currency of Japan). However, a_i may be negative, in which case you will be charged money.
By optimally performing the operation, how much yen can you earn?
Constraints
- All input values are integers.
- 1 \leq N \leq 100
- |a_i| \leq 10^9
Input
Input is given from Standard Input in the following format:
N a_1 a_2 ... a_N
Output
Print the maximum amount of money that can be earned.
Sample Input 1
6 1 2 -6 4 5 3
Sample Output 1
12
It is optimal to smash Gem 3 and 6.
Sample Input 2
6 100 -100 -100 -100 100 -100
Sample Output 2
200
Sample Input 3
5 -1 -2 -3 -4 -5
Sample Output 3
0
It is optimal to smash all the gems.
Sample Input 4
2 -1000 100000
Sample Output 4
99000
Time Limit: 3 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
全ての要素が 0 の数列 a = \{a_1, ..., a_N\} と，0 と 1 からなる数列 b = \{b_1, ..., b_N\} が与えられます。 どちらも長さは N です。
あなたは Q 種類の操作を行うことが可能です。i 種類目の操作は以下のような動作です。
- a_{l_i}, a_{l_i + 1}, ..., a_{r_i} を全て 1 に書き換える
Q 種類の操作のうちいくつかを行い，a と b のハミング距離， つまり a_i \neq b_i なる i の数を最小化してください。
制約
- 1 \leq N \leq 200,000
- b は 0, 1 からなる
- 1 \leq Q \leq 200,000
- 1 \leq l_i \leq r_i \leq N
- i \neq j ならば l_i \neq l_j または r_i \neq r_j
入力
入力は以下の形式で標準入力から与えられる。
N b_1 b_2 ... b_N Q l_1 r_1 l_2 r_2 : l_Q r_Q
出力
ハミング距離の最小値を出力してください。
入力例 1
3 1 0 1 1 1 3
出力例 1
1
操作を行うと a = \{1, 1, 1\} になり，ハミング距離は 1 となります。
入力例 2
3 1 0 1 2 1 1 3 3
出力例 2
0
両方の操作を行うと a = \{1, 0, 1\} になり，ハミング距離は 0 となります。
入力例 3
3 1 0 1 2 1 1 2 3
出力例 3
1
入力例 4
5 0 1 0 1 0 1 1 5
出力例 4
2
何も操作を行わないのが最適な時もあります。
入力例 5
9 0 1 0 1 1 1 0 1 0 3 1 4 5 8 6 7
出力例 5
3
入力例 6
15 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 9 4 10 13 14 1 7 4 14 9 11 2 6 7 8 3 12 7 13
出力例 6
5
入力例 7
10 0 0 0 1 0 0 1 1 1 0 7 1 4 2 5 1 3 6 7 9 9 1 5 7 9
出力例 7
1
Score : 1000 points
Problem Statement
You are given a sequence a = \{a_1, ..., a_N\} with all zeros, and a sequence b = \{b_1, ..., b_N\} consisting of 0 and 1. The length of both is N.
You can perform Q kinds of operations. The i-th operation is as follows:
- Replace each of a_{l_i}, a_{l_i + 1}, ..., a_{r_i} with 1.
Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.
Constraints
- 1 \leq N \leq 200,000
- b consists of 0 and 1.
- 1 \leq Q \leq 200,000
- 1 \leq l_i \leq r_i \leq N
- If i \neq j, either l_i \neq l_j or r_i \neq r_j.
Input
Input is given from Standard Input in the following format:
N b_1 b_2 ... b_N Q l_1 r_1 l_2 r_2 : l_Q r_Q
Output
Print the minimum possible hamming distance.
Sample Input 1
3 1 0 1 1 1 3
Sample Output 1
1
If you choose to perform the operation, a will become \{1, 1, 1\}, for a hamming distance of 1.
Sample Input 2
3 1 0 1 2 1 1 3 3
Sample Output 2
0
If both operations are performed, a will become \{1, 0, 1\}, for a hamming distance of 0.
Sample Input 3
3 1 0 1 2 1 1 2 3
Sample Output 3
1
Sample Input 4
5 0 1 0 1 0 1 1 5
Sample Output 4
2
It may be optimal to perform no operation.
Sample Input 5
9 0 1 0 1 1 1 0 1 0 3 1 4 5 8 6 7
Sample Output 5
3
Sample Input 6
15 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 9 4 10 13 14 1 7 4 14 9 11 2 6 7 8 3 12 7 13
Sample Output 6
5
Sample Input 7
10 0 0 0 1 0 0 1 1 1 0 7 1 4 2 5 1 3 6 7 9 9 1 5 7 9
Sample Output 7
1