第１６回日本情報オリンピック本選（過去問）

A - フェーン現象 (Foehn Phenomena)

Time Limit: 1 sec / Memory Limit: 256 MB

配点： 100 点

IOI 国では海から陸に向かって常に風が吹いている．風は地点 0 から地点 1，地点 2，\ldots という経路を通りながら地点 N まで吹く．地点 N には JOI 君の家が建てられている．地点 0 の標高は A_0 = 0 であり，地点 i (1 \leqq i \leqq N) の標高は A_i である．

風は地表面に沿って吹き，高度の変化に応じて風の温度が変化する．海に接している地点 0 での風の温度は 0 度であり，すべての i (0 \leqq i \leqq N - 1) に対して，地点 i から地点 i + 1 にかけての風の温度の変化はその時点における A_i と A_{i + 1} にのみ依存しており，以下のようになっている．

A_i < A_{i + 1} のとき，標高が 1 上がるごとに風の温度は S 度下がる．
A_i \geqq A_{i + 1} のとき，標高が 1 下がるごとに風の温度は T 度上がる．

IOI 国の領土では地殻変動が盛んである．あなたは，Q 日間の地殻変動のデータを入手した．j 日目 (1 \leqq j \leqq Q) には，L_j \leqq k \leqq R_j (1 \leqq L_j \leqq R_j \leqq N) を満たす地点の標高 A_k が X_j だけ変化する．X_j が非負のときは，標高が X_j だけ上がることを意味し，X_j が負のときは，標高が |X_j| だけ下がることを意味する．

あなたの仕事は，各地殻変動が起こった後の，JOI 君の家に吹く風の温度を求めることである．

課題

地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 j (1 \leqq j \leqq Q) に対し，j 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には， 4 個の整数 N, Q, S, T が空白を区切りとして書かれている．これらは，JOI 君の家が地点 N に建てられており，地殻変動の回数が Q であり，標高が 1 上がるごとに風の温度が S 度下がり，1 下がるごとに T 度上がることを表す．
続く N + 1 行のうちの i 行目 (1 \leqq i \leqq N + 1) には，地点 i - 1 での地殻変動が起こる前の標高を表す整数 A_{i - 1} が書かれている．
続く Q 行のうちの j 行目 (1 \leqq j \leqq Q) には，3 個の整数 L_j, R_j, X_j が空白を区切りとして書かれている．これらは，j 日目の地殻変動で地点 L_j から R_j までの標高が X_j だけ変化することを表す．

出力

出力は Q 行からなる．標準出力の j 行目 (1 \leqq j \leqq Q) には，j 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を出力せよ．

制限

すべての入力データは以下の条件を満たす．

1 \leqq N \leqq 200\,000．
1 \leqq Q \leqq 200\,000．
1 \leqq S \leqq 1\,000\,000．
1 \leqq T \leqq 1\,000\,000．
A_0 = 0．
-1\,000\,000 \leqq A_i \leqq 1\,000\,000 (1 \leqq i \leqq N)．
1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q)．
-1\,000\,000 \leqq X_j \leqq 1\,000\,000 (1 \leqq j \leqq Q)．

小課題

小課題 1 [30 点]

以下の条件を満たす．

N \leqq 2\,000．
Q \leqq 2\,000．

小課題 2 [10 点]

S = T を満たす．

小課題 3 [60 点]

追加の制限はない．

入力例 1

出力例 1

-5
-7
-13
-13
-18

最初，地点 0, 1, 2, 3 の標高はそれぞれ 0, 4, 1, 8 である．1 日目の地殻変動の後，標高はそれぞれ 0, 6, 3, 8となる．このとき，地点 0, 1, 2, 3 での風の温度はそれぞれ 0, -6, 0, -5 となる．

入力例 2

出力例 2

5
-35

この入力例は，小課題 2 の条件を満たす．

入力例 3

出力例 3

B - 準急電車 (Semiexpress)

Time Limit: 1 sec / Memory Limit: 256 MB

配点： 100 点

JOI 国の唯一の鉄道会社である JOI 鉄道には 1 本の線路に沿って N 個の駅があり，順に 1, 2, \ldots, N の番号が付いている．現在，運行されている電車の種別は，急行と普通の 2 種類である．

普通電車はすべての駅に停車し，各 i (1 \leqq i < N) について，駅 i と駅 i + 1 の間を A 分で走行する．

急行電車は M 個の駅 S_1, S_2, \ldots, S_M (1 = S_1 < S_2 < \cdots < S_M = N) に停車する．また，各 i (1 \leqq i < N) について，駅 i と駅 i + 1 の間を B 分で走行する．

JOI 鉄道は電車の種別として準急電車を新設することにした．準急電車は各 i (1 \leqq i < N) について，駅 i と駅 i + 1 の間を C 分で走行する．準急電車の停車駅は決まっていないが，以下の条件を満たすようにすることは決まっている．

準急電車はすべての急行停車駅に停車する．
準急電車はちょうど K 個の駅に停車する．

JOI 鉄道は，駅 1 から 1 種類以上の電車を使って移動するときの乗車時間の合計が T 分以内となるような，駅 1 以外の駅の個数が最大となるように準急電車の停車駅を決めることにした．ここで，乗車時間には停車時間は含めないものとする．

ただし，JOI 鉄道を用いて駅 1 から他の駅まで移動するときは，駅の番号が大きくなる方向の電車しか用いることができない．また，駅 i (2 \leqq i \leqq N - 1) に複数の種別の電車が停車するとき，その駅では停車するすべての電車に乗り換えることができる．

準急電車の停車駅をうまく決めたときの，駅 1 からの乗車時間の合計が T 分以内となるような，駅 1 以外の駅の個数の最大値を求めたい．

課題

JOI 鉄道の駅の個数，急行電車の停車駅，電車の速度の情報，乗車時間の条件が与えられたとき，乗車時間の条件を満たす駅の個数の最大値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には，3 個の整数 N, M, K が空白を区切りとして書かれている．これらは，JOI 鉄道に駅が N 個あり，急行電車は M 個の駅に停車し，準急電車は K 個の駅に停車することを表す．
2 行目には，3 個の整数 A, B, C が空白を区切りとして書かれている．これらは，普通電車，急行電車，準急電車が隣り合う駅の間を走行するのにかかる時間がそれぞれ A 分，B 分，C 分であることを表す．
3 行目には，整数 T が書かれている．これは，駅 1 からの乗車時間の合計が T 分以内となる駅の個数を最大化したいことを表す．
続く M 行のうちの i 行目 (1 \leqq i \leqq M) には，整数 S_i が書かれている．これは，急行電車が駅 S_i に停車することを表す．

出力

標準出力に，乗車時間の条件を満たす駅の個数の最大値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

2 \leqq N \leqq 1\,000\,000\,000．
2 \leqq M \leqq K \leqq 3\,000．
K \leqq N．
1 \leqq B < C < A \leqq 1\,000\,000\,000．
1 \leqq T \leqq 10^{18}．
1 = S_1 < S_2 < \cdots < S_M = N．

小課題

小課題 1 [18 点]

以下の条件を満たす．

N \leqq 300．
K - M = 2．
A \leqq 1\,000\,000．
T \leqq 1\,000\,000\,000．

小課題 2 [30 点]

N \leqq 300 を満たす．

小課題 3 [52 点]

追加の制限はない．

入力例 1

出力例 1

この入力例では，JOI 鉄道には 10 個の駅があり，急行電車は 3 個の駅 1, 6, 10 に停車する．準急電車を駅 1, 5, 6, 8, 10 に停車させると，駅 2, 3, \ldots, 10 のうち駅 9 を除く 8 個の駅に，駅 1 から 30 分以内の乗車時間で移動できる．

準急電車の停車駅を上記のように決めたときの，いくつかの i についての，駅 1 から駅 i まで移動する際の乗車時間と，そのときの移動方法を示す．

駅 1 から駅 3 へは，普通電車だけを用いて 20 分の乗車時間で移動できる．
駅 1 から駅 7 へは，駅 1 から駅 6 まで急行電車で移動し，駅 6 で普通電車に乗り換えることで 25 分の乗車時間で移動できる．
駅 1 から駅 8 へは，駅 1 から駅 6 まで急行電車で移動し，駅 6 で準急電車に乗り換えることで 25 分の乗車時間で移動できる．
駅 1 から駅 9 へは，駅 1 から駅 6 まで急行電車で移動し，駅 6 から駅 8 まで準急電車で移動し，駅 8 から駅 9 まで普通電車で移動することで 35 分の乗車時間で移動できる．

入力例 2

出力例 2

入力例 3

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

出力例 3

入力例 4

出力例 4

この入力例は，小課題 1 の条件を満たさない．

入力例 5

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

出力例 5

この入力例は，小課題 1 の条件を満たさない．

入力例 6

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

出力例 6

この入力例は，小課題 1 および小課題 2 の条件を満たさない．

C - JOIOI 王国 (Kingdom of JOIOI)

Time Limit: 4 sec / Memory Limit: 256 MB

配点： 100 点

JOIOI 王国は H 行 W 列のマスに区切られた長方形の形をしている．JOIOI 王国では，行政の効率化のため，国全体を 2 つの地域 JOI と IOI に分けることにした．

地域の分け方が複雑になりすぎるのを防ぐため，以下の条件を満たすように分割を行うことにした：

各地域は，1 つ以上のマスを含む．
それぞれのマスは，2 つの地域のうちのちょうど 1 つに属する．
地域 JOI に属するどの 2 つのマスの間も，その地域に属さないマスに入らずに辺で接しているマスへの移動を繰り返すことにより移動できる．地域 IOI についても同様である．
各行，各列について，その行または列に属するマス全体を取り出したとき，それぞれの地域のマスはひとつながりになっている．ただし，その行あるいは列のすべてのマスが同じ地域に属していてもよい．

各マスには標高と呼ばれる整数が定まっている．地域への分割を行った後は，各地域内での移動が活発になると想定される．地域内での標高の差があまりに大きいと移動が大変であるため，同じ地域内での標高差ができるだけ小さくなるように分割を行いたい．すなわち，地域 JOI の中での標高の最大値と最小値の差と，地域 IOI の中での標高の最大値と最小値の差のうち，大きい方の値を最小化したい．

課題

JOIOI 王国の各マスの標高が与えられたとき，条件を満たすように地域の分割をした際の，地域 JOI の中での標高の最大値と最小値の差と，地域 IOI の中での標高の最大値と最小値の差のうち，大きい方の値の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には，2 個の整数 H, W が空白を区切りとして書かれている．これらは，JOIOI 国が H 行 W 列のマスに区切られた長方形の形をしていることを表す．
続く H 行のうちの i 行目 (1 \leqq i \leqq H) には，W 個の整数 A_{i, 1}, A_{i, 2}, \ldots, A_{i, W} が空白を区切りとして書かれている．これは，JOIOI 王国の上から i 行目，左から j 列目 (1 \leqq j \leqq W) の標高が A_{i, j} であることを表す．

出力

標準出力に，条件を満たすように地域の分割をした際の，地域 JOI の中での標高の最大値と最小値の差と，地域 IOI の中での標高の最大値と最小値の差のうち，大きい方の値の最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

2 \leqq H \leqq 2\,000．
2 \leqq W \leqq 2\,000．
1 \leqq A_{i, j} \leqq 1\,000\,000\,000 (1 \leqq i \leqq H，1 \leqq j \leqq W)．

小課題 1 [15 点]

以下の条件を満たす．

H \leqq 10．
W \leqq 10．

小課題 2 [45 点]

以下の条件を満たす．

H \leqq 200．
W \leqq 200．

小課題 3 [40 点]

追加の制限はない．

入力例 1

出力例 1

この入力例では，例えば下の図のように地域を分割すればよい．ここで，J は地域 JOI，I は地域 IOI を表す．

J J J I
J J J I
J J I I
J I I I

ここで，例えば次のような分割は，左から 3 列目において地域 IOI がひとつながりになっていないため，条件を満たす分割ではない．

J J I I
J J J I
J J J I
J I I I

入力例 2

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16

出力例 2

D - サッカー (Soccer)

Time Limit: 3 sec / Memory Limit: 256 MB

配点： 100 点

あなたは JOI リーグの名門サッカークラブに所属するマネージャーである．

クラブには N 人の選手が所属しており，選手には 1 から N までの番号が付けられている．選手たちは優勝を目指してグラウンドで日々練習をしている．グラウンドは縦 H メートル，横 W メートルの長方形の形状をしている．グラウンドの縦方向は南北方向に平行であり，横方向は東西方向に平行である．グラウンドの北西隅から南に i メートル，東に j メートル進んだ地点を地点 (i, j) と呼ぶことにする．

練習が終わったあと，練習に使用したボールを片付けなければならない．片付け開始時点では，選手 i (1 \leqq i \leqq N) は地点 (S_i, T_i) におり，ボールは選手 1 のみが 1 つ所持している状態である．あなたは選手 N とともに地点 (S_N, T_N) におり，あなたがボールを回収すること，すなわちボールを地点 (S_N, T_N) に移動させることで片付けは完了する．片付けの過程であなたは移動できない．

あなたは選手たちに行動を指示することができる．選手たちは何か行動すると，その行動に応じて疲労度を蓄積してしまう．

以下の行動のうち，ボールを所持している選手は行動 (i), (ii), (iii) を，それ以外の選手は行動 (ii), (iv) を実行できる．

(i) 東西南北 4 方向のうち 1 方向および正整数 p を指定する．その方向にボールを蹴り，ボールをちょうど p メートルだけ移動させる．蹴った選手はこの行動では移動せず，ボールを所持していない状態になる．疲労度は A \times p + B だけ増加する．
(ii) 東西南北 4 方向のうち 1 方向を指定する．その方向に 1 メートル移動する．もしも移動する選手がボールを所持している場合，ボールと一緒に移動する．ボールの有無にかかわらず疲労度は C だけ増加する．
(iii) ボールをその場に置き，ボールを所持していない状態になる．疲労度は増加しない．
(iv) ボールを所持する．疲労度は増加しない．この操作はボールと同一地点にいる選手のみが，他に誰もボールを所持していない場合に限り実行可能である．

選手やボールがグラウンドの外に出たり，複数の選手が同一地点に存在したりしてもかまわないことに注意せよ．

練習後の選手にあまり多く疲労度を蓄積させないために，あなたは片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を求めることにした．

課題

グラウンドの大きさおよび選手たちの位置が与えられたとき，片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には 2 個の整数 H, W が空白を区切りとして書かれている．これらはグラウンドが縦に H メートル，横に W メートルの長方形の形状をしていることを表している．
2 行目には疲労度の増加に関する 3 個の整数 A, B, C が空白を区切りとして書かれている．
3 行目には整数 N が書かれている．これは選手が N 人いることを表している．
続く N 行のうち i 行目 (1 \leqq i \leqq N) には 2 つの整数 S_i, T_i が空白を区切りとして書かれている．これらは片付け開始時点で選手 i が地点 (S_i, T_i) にいることを表している．

出力

標準出力に，片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

1 \leqq H \leqq 500．
1 \leqq W \leqq 500．
0 \leqq A \leqq 1\,000\,000\,000．
0 \leqq B \leqq 1\,000\,000\,000．
0 \leqq C \leqq 1\,000\,000\,000．
2 \leqq N \leqq 100\,000．
0 \leqq S i \leqq H (1 \leqq i \leqq N)．
0 \leqq Ti \leqq W (1 \leqq i \leqq N)．
(S_1, T_1) \neq (S_N, T_N)．

小課題

小課題 1 [5 点]

N = 2 を満たす．

小課題 2 [30 点]

以下の条件を満たす．

N \leqq 1\,000．
A = 0．

小課題 3 [65 点]

追加の制限はない．

入力例 1

出力例 1

入力例 1 は，小課題 1 および小課題 2 の条件を満たしていない．この入力例では，グラウンドは下図の状態となっている．図において，白い丸は選手を，黒い丸はボールを表している．あなたは (6, 5) にいる．

グラウンドの初期状態

この場合，以下のように行動すればよい．

選手 1 が所持しているボールを東に 3 メートル蹴る．疲労度は 1 \times 3 + 3 = 6 だけ上昇し，ボールは (1, 4) に移動する．
選手 2 が南に 1 メートル移動し，ボールを所持する．疲労度は 6 だけ上昇する．
選手 2 が東に 1 メートル移動する．疲労度は 6 だけ上昇する．
選手 2 が所持しているボールを南に 5 メートル蹴る．疲労度は 1 \times 5 + 3 = 8 だけ上昇し，ボールは (6, 5) に移動する．

この場合，疲労度の合計値は 6 + 6 + 6 + 8 = 26 となり，これが最小値となる．

最適解における行動の様子

入力例 2

出力例 2

入力例 2 は，小課題 1 および小課題 2 の条件を満たしている．入力例 2 において，ボールを蹴る必要はない．

入力例 3

出力例 3

入力例 3 は，小課題 1 および小課題 2 の条件を満たしている．

入力例 4

出力例 4

入力例 4 は，小課題 1 の条件を満たしておらず，小課題 2 の条件を満たしている．同じ地点に複数の選手がいる場合が含まれることに注意せよ．

E - 縄 (Rope)

Time Limit: 2.5 sec / Memory Limit: 256 MB

配点： 100 点

赤ちゃんの JOI くんは縄で遊んでいる．縄の長さは N であり，左右にまっすぐ伸びている．縄は太さ 1，長さ 1 の紐 (ひも) が N 個つながってできている．縄には M 種類の色が使われており，左から i 番目の紐の色は C_i (1 \leqq C_i \leqq M) である．

JOI くんは縄をより合わせて短くしていく．具体的には，以下の操作を縄の長さが 2 となるまで繰り返す．

縄の長さを L とする．ある整数 j (1 \leqq j < L) を取り，左から長さ j の位置が新たに左の端点となるよう，縄をより合わせていく．すなわち，
- j \leqq L/2 のとき，各 i (1 \leqq i \leqq j) について，左から i 番目の紐と，左から 2j - i + 1 番目の紐をより合わせる．このとき元々右の端点だった位置は引き続き右の端点となり，縄の長さは L - j となる．
- j > L/2 のとき，各 i (2j - L + 1 \leqq i \leqq j) について，左から i 番目の紐と，左から 2j - i + 1 番目の紐をより合わせる．このとき元々左の端点だった位置は右の端点となり，縄の長さは j となる．
このとき，より合わされる各紐の組について，色を揃えなければならない．紐はより合わせる直前に，任意の色に塗り替えることができるが，塗り替えた場合その太さと同じだけのコストがかかる．色を揃えたのち，紐はより合わされ，できた紐の太さはより合わされた 2 つの紐の太さの和となる．

JOI くんは，縄の長さが 2 となるまでに行う操作のコストの総和を最小化したいと思っている．JOI くんはすべての色について，最終的な縄がその色を含むように操作を行った場合のコストの総和の最小値を求めたいと思っている．

あなたの仕事は JOI くんに代わってこの問題を解くことである．

課題

はじめの縄を構成する紐の色が与えられたとき，それぞれの色について，縄がその色を含み，かつ長さを 2 とするのに必要なコストの最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

1 行目には 2 個の整数 N, M が空白を区切りとして書かれている．これらは縄を構成する紐が N 個あり，それらの色が M 種類あることを表す．
2 行目には N 個の整数 C_1, C_2, \ldots,C_N が空白を区切りとして書かれている．これらは左から i 番目の紐の色が C_i であることを表す．

出力

標準出力に M 行で出力せよ．M 行のうちの c (1 \leqq c \leqq M) 行目には，最終的な縄の長さが 2 となり，その縄に色 c を含むようにより合わせるためのコストの総和の最小値を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

2 \leqq N \leqq 1\,000\,000．
1 \leqq M \leqq N．
1 \leqq C_i \leqq M (1 \leqq i \leqq N)．
1 \leqq c \leqq M を満たすすべての整数 c について，C_i = c となる i が存在する.

小課題

小課題 1 [15 点]

以下の条件を満たす．

N \leqq 15．
M \leqq 10．

小課題 2 [30 点]

以下の条件を満たす．

N \leqq 100\,000．
M \leqq 10．

小課題 3 [10 点]

以下の条件を満たす．

N \leqq 100\,000．
M \leqq 500．

小課題 4 [25 点]

M \leqq 5\,000 を満たす．

小課題 5 [20 点]

追加の制限はない．

入力例 1

5 3
1 2 3 3 2

出力例 1

2
1
1

以下のような操作で，色 1 を含むようコスト 2 で長さ 2 により合わせることができる．

左から 2 番目の紐を色 1 に塗り替え，左から長さ 1 の位置が端点となるようより合わせる．左から順に縄の色は 1, 3, 3, 2 となり，太さは 2, 1, 1, 1 となる．
左から 4 番目の紐の色を 1 に塗り替え，左から長さ 2 の位置が端点となるようより合わせる．左から順に縄の色は 3, 1 となり，太さは 2, 3 となる．

また，以下のような操作で，色 2, 3 を含むようコスト 1 で長さ 2 により合わせることができる．

左から長さ 3 の位置が端点となるようより合わせる．左から順に縄の色は 3, 2, 1 となり，太さは 2, 2, 1 となる．
左から 3 番目の紐の色を 2 に塗り替え，左から長さ 2 の位置が端点となるようより合わせる．左から順に縄の色は 2, 3 となり，太さは 3, 2 となる．

入力例 2

7 3
1 2 2 1 3 3 3

出力例 2

2
2
2

以下のような操作で，色 1 を含むようコスト 2 で長さ 2 により合わせることができる．

左から長さ 2 の位置が端点となるようより合わせる．
左から 1 番目の紐の色を 1 に塗り替え，左から長さ 1 の位置が端点となるようより合わせる．塗り替える紐の太さが 2 なので，コストが 2 かかることに注意せよ．
左から長さ 3 の位置が端点となるようより合わせる．
左から長さ 1 の位置が端点となるようより合わせる．

入力例 3

10 3
2 2 1 1 3 3 2 1 1 2

出力例 3

3
3
4

1 回のより合わせの前に，複数箇所の紐を塗り替えてもよい．