Time Limit: 2 sec / Memory Limit: 256 MB
問題文
りんごさんは一次元オセロで遊んでいます。一次元オセロとは、無限に長い 1 列に並んだマス目と、特殊なコマを使って遊ぶゲームです。一次元オセロで用いるコマは表が黒色で裏が白色のコマで、黒のコマを裏返すと白のコマに、白のコマを裏返すと黒のコマになります。一次元オセロは以下のように進行します。
- まず、白のコマ A_1 個、黒のコマ A_2 個、白のコマ A_3 個、...、白のコマ A_N 個をこの順に連続したマス目に置く。
- 黒のコマをいずれかの空きマスに置く。このとき、隣の 2 マスのうちちょうど 1 マスに白のコマがなければならない。
- 2. で置いた黒のコマに最も近い別の黒のコマ（そのようなコマは常に一意に定まる）との間にある白のコマを全て裏返して黒のコマにする。
- 2. と 3. の黒と白を入れ替えた操作を行う。
- 2. 〜 4. を繰り返す。
- 3. または 4. を終えた時点で、全てのコマが同じ色になった場合はその時点で終了となる。
たくさんのコマを裏返すのは大変なので、りんごさんはコマを裏返す回数を少なくしたいと思っています。ゲームが終了するまでにりんごさんが裏返すコマの個数の和の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
- 1 行目には、整数 N (3 ≦ N < 10^5, N は奇数) が与えられる。
- 2 行目には、コマの初期配置の情報を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目には A_i (1 ≦ A_i ≦ 10^8) が与えられる。
出力
ゲームが終了するまでにりんごさんが裏返すコマの個数の和の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
5 1 2 3 4 5
出力例1
20
下図のようにコマを置いていくと、全部で 1+4+5+10 = 20 回コマをひっくり返すことになります。
入力例2
9 100000000 20 15 11 14 20 15 11 15
出力例2
554
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
りんごさんは 1 辺の長さが 1 の立方体を積んで遊んでいます。りんごさんは地面に 1 辺の長さが 1 の正方形を横に並べて N 個描き、左から i 個目の正方形の上に立方体を A_i 個積みました。
りんごさんは立方体の表面にペンキを塗ることにしました。別の立方体や地面と接している面にはペンキを塗りません。しかし、りんごさんはペンキの量が足りるか不安になりました。そこで、K 個の立方体を取り除いてからペンキを塗ることにしました。このとき、いずれの正方形の上にも 1 個以上の立方体がなければなりません。
りんごさんは必要なペンキの量をできるだけ少なくしたいです。ペンキを塗る面積の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 ... A_N
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^5), K (1 ≦ K ≦ 10^{14}) が空白区切りで与えられる。これは、地面に描いた正方形の個数が N 個、取り除く立方体の個数が K 個であることを表す。
- 2 行目には、各正方形の上に積む立方体の個数を表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 A_i (1 ≦ A_i ≦ 10^9) は、左から i 個目の正方形の上に積む立方体の個数を表す。ただし、いずれの正方形の上にも 1 個以上の立方体を残して K 個の立方体を取り除くことができること、すなわち Σ A_i ≧ N+K が保証される。
出力
ペンキを塗る面積の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
7 6 2 3 2 1 2 3 4
出力例1
35
下図は、はじめに積んだ立方体を正面から見たときの様子を表しています。
下図のように 6 個の立方体を取り除くと、ペンキを塗る面積は 35 となります。
入力例2
10 919924177 114777581 900857217 199708389 41623648 586160911 824291566 209849198 803644124 355106148 180322764
出力例2
9307626516
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
りんごさんは長さ N の数列を持っています。数列は相異なる 1 ~ N の整数からなります。りんごさんはこの数列を K 箇所で切って K+1 個の連続した部分に分割し、それらを好きな順番で連結することにより新たな数列を作ろうとしています。りんごさんが作ることのできる数列のうち辞書順最小のものを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 ... A_N
- 1 行目には、2 つの整数 N (2 ≦ N ≦ 10^5), K (1 ≦ K ≦ N-1) が空白区切りで与えられる。これは、数列の長さが N、数列を切る場所が K 箇所であることを表す。
- 2 行目には、N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 A_i (1 ≦ A_i ≦ N) は、数列の i 番目の数を表す。ただし、A_i は全て相異なることが保証される。
出力
出力は N 行からなる。このうち i 行目には、りんごさんが作ることのできる数列のうち辞書順最小の数列の i 番目の数を表す 1 つの整数を出力せよ。出力の末尾にも改行を入れること。
入力例1
5 3 1 3 5 2 4
出力例1
1 2 3 5 4
1 | 3 5 | 2 | 4 と切って 1 | 2 | 3 5 | 4 と並べ替えると辞書順最小の数列になります。
入力例2
9 5 4 6 8 1 2 9 3 7 5
出力例2
1 2 3 4 6 7 5 8 9
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
りんごさんは無限に長い棒の上を歩く N 匹のアリを眺めています。今、i 匹目のアリは座標 X_i の場所にいて、速度 S_i で方向 D_i を向いて歩いています。D_i が R のときは座標が増加する向き、D_i が L のときは座標が減少する向きを表します。
りんごさんは K 匹のアリを棒から取り除くことができます。このとき、はじめにアリどうしが衝突するまでの時間の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N K X_1 S_1 D_1 X_2 S_2 D_2 : X_N S_N D_N
- 1 行目には、2 つの整数 N (2 ≦ N ≦ 10^5), K (1 ≦ K ≦ N-1) が空白区切りで与えられる。これは、アリが N 匹、りんごさんが取り除くことのできるアリが K 匹であることを表す。
- 2 行目からの N 行には、アリの情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、整数 X_i (0 ≦ X_i ≦ 10^9), S_i (1 ≦ S_i ≦ 10^6) と文字 D_i (D_i は
LまたはR) が与えられる。これは、i 匹目のアリがはじめ座標 X_i にいて、速度 S_i で方向 D_i を向いて歩くことを表す。ただし、X_i は全て相異なることが保証される。
出力
はじめにアリどうしが衝突するまでの時間の最大値を 1 行に出力せよ。出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。アリどうしが衝突しないようにすることができる場合は、代わりに Infinity と出力せよ。出力の末尾に改行を入れること。
入力例1
3 1 4 2 R 7 1 L 0 4 R
出力例1
2.000000000000000
2 匹目のアリを取り除いたとき、はじめにアリどうしが衝突するまでの時間が最も長くなります。
入力例2
7 2 1 3 L 2 3 R 3 2 L 4 2 L 5 4 R 6 5 L 9 1 R
出力例2
1.333333333333333
小数点以下は何桁出力してもかまいません。
入力例3
2 1 0 1000000 R 1000000000 1000000 R
出力例3
Infinity