Time Limit: 2 sec / Memory Limit: 1024 MiB
配点： 100 点
問題文
ビ太郎は N 枚のカードを持っており，i 枚目 (1 \leqq i \leqq N) のカードには整数 A_i が書かれている． これらの中から次の条件を満たすような 3 枚のカードを選びたい．
条件:
選んだカードに書かれている整数が 3 ずつ離れている．
厳密には，選んだカードに書かれている整数が，ある整数 x を用いて x, x+3, x+6 と表せる．
例えば，ビ太郎が 5 枚のカードを持っており，それぞれに 2, 4, 5, 7, 10 が書かれているとき，4, 7, 10 が書かれているカードを選ぶと，条件を満たす．
ビ太郎が持っているカードの情報が与えられたとき，条件を満たすように 3 枚のカードを選ぶことができるかどうか判定するプログラムを作成せよ．
制約
- 3 \leqq N \leqq 200\,000．
- 1 \leqq A_i \leqq 200\,000 (1 \leqq i \leqq N)．
- 入力される値はすべて整数である．
小課題
- (20 点) N = 3．
- (20 点) A_i \leqq 7 (1 \leqq i \leqq N)．
- (30 点) N \leqq 100．
- (30 点) 追加の制約はない．
入力
入力は以下の形式で与えられる．
N A_1 A_2 \cdots A_N
出力
条件を満たすように 3 枚のカードを選ぶことができる場合 Yes を，そうでない場合 No を出力せよ．
入力例 1
3 2 5 8
出力例 1
Yes
2, 5, 8 が書かれているカードを選ぶと，条件を満たす．したがって，Yes を出力する．
この入力例は小課題 1, 3, 4 の制約を満たす．
入力例 2
4 1 4 6 4
出力例 2
No
条件を満たすようにカードを選ぶことはできない．したがって，No を出力する．
この入力例は小課題 2, 3, 4 の制約を満たす．
入力例 3
8 9 8 11 1 1 6 10 4
出力例 3
No
条件を満たすようにカードを選ぶことはできない．したがって，No を出力する．
この入力例は小課題 3, 4 の制約を満たす．
入力例 4
20 2 15 4 30 6 8 11 27 14 3 16 26 19 2 23 21 18 13 28 6
出力例 4
Yes
15, 18, 21 が書かれているカードを選ぶと，条件を満たす．したがって，Yes を出力する．
この入力例は小課題 3, 4 の制約を満たす．
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点： 100 点
問題文
JOI 商店には N 個の商品があり，商品には 1 から N までの番号が付けられている．
それぞれの商品には，定価と種類が定められている．商品 i (1 \leqq i \leqq N) の定価は P_i 円である．商品の種類は 1 以上 M 以下の整数で表され，商品 i (1 \leqq i \leqq N) の種類は A_i である．
JOI 商店は，セールを行うことにした．セールは M 日間続き，j 日目 (1 \leqq j \leqq M) には種類 j の商品をすべて定価の半額で買うことができる．
セールの期間中に，Q 人の客が JOI 商店を訪れた．客には 1 から Q までの番号が付けられている．客 k (1 \leqq k \leqq Q) はセールの T_k 日目に JOI 商店を訪れ，商品 L_k, L_k+1, \dots, R_k を 1 つずつ買った．
セールの効果を調査するため，それぞれの客が商品を買うのにかかった金額を知りたい．
商品の情報と客の情報が与えられたとき，それぞれの客が商品を買うのにかかった金額を求めるプログラムを作成せよ．
制約
- 1 \leqq N \leqq 200\,000．
- 1 \leqq M\leqq 200\,000．
- 1 \leqq Q \leqq 200\,000．
- 2 \leqq P_i \leqq 10^9 (1 \leqq i \leqq N)．
- P_i は偶数である (1 \leqq i \leqq N)．
- 1 \leqq A_i \leqq M (1 \leqq i \leqq N)．
- 1 \leqq T_k \leqq M (1 \leqq k \leqq Q)．
- 1 \leqq L_k \leqq R_k \leqq N (1 \leqq k \leqq Q)．
- 入力される値はすべて整数である．
小課題
- (15 点) N \leqq 2\,000，M \leqq 2\,000，Q \leqq 2\,000．
- (20 点) M = 1．
- (12 点) M \leqq 10．
- (14 点) A_i \neq A_j (1 \leqq i < j \leqq N)．
- (22 点) P_i = 2 (1 \leqq i \leqq N)．
- (17 点) 追加の制約はない．
入力
入力は以下の形式で与えられる．
N M Q P_1 A_1 P_2 A_2 \vdots P_N A_N T_1 L_1 R_1 T_2 L_2 R_2 \vdots T_Q L_Q R_Q
出力
Q 行出力せよ．k 行目 (1 \leqq k \leqq Q) には，客 k が商品を買うのにかかった金額を，単位 (円) を省いて出力せよ．
入力例 1
5 1 3 10 1 40 1 30 1 20 1 50 1 1 2 4 1 3 5 1 1 5
出力例 1
45 50 75
客 1 が商品を買うのにかかった金額は 40 \div 2 + 30 \div 2 + 20 \div 2 = 45 円であるため，1 行目には 45 を出力する．
客 2 が商品を買うのにかかった金額は 30 \div 2 + 20 \div 2 + 50 \div 2 = 50 円であるため，2 行目には 50 を出力する．
客 3 が商品を買うのにかかった金額は 10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75 円であるため，3 行目には 75 を出力する．
この入力例は小課題 1,2,3,6 の制約を満たす．
入力例 2
5 3 3 10 1 40 3 30 2 20 1 50 3 1 2 4 3 3 5 2 1 5
出力例 2
80 75 135
客 1 が商品を買うのにかかった金額は 40 + 30 + 20 \div 2 = 80 円であるため，1 行目には 80 を出力する．
客 2 が商品を買うのにかかった金額は 30 + 20 + 50 \div 2 = 75 円であるため，2 行目には 75 を出力する．
客 3 が商品を買うのにかかった金額は 10 + 40 + 30 \div 2 + 20 + 50 = 135 円であるため，3 行目には 135 を出力する．
この入力例は小課題 1,3,6 の制約を満たす．
入力例 3
5 5 3 50 2 70 4 20 5 30 1 10 3 4 2 4 5 1 5 2 3 4
出力例 3
85 170 50
この入力例は小課題 1,3,4,6 の制約を満たす．
入力例 4
10 5 4 2 1 2 5 2 4 2 3 2 4 2 2 2 2 2 4 2 2 2 1 3 2 7 1 1 7 2 1 10 5 5 8
出力例 4
11 13 17 8
この入力例は小課題 1,3,5,6 の制約を満たす．
入力例 5
10 10 10 741703628 7 231838922 5 920286164 3 763741914 5 246151406 7 54109256 1 966457488 5 441379880 10 458514202 2 224373612 1 5 5 10 2 2 7 1 9 9 1 3 4 9 4 6 1 1 7 9 4 7 4 8 8 7 5 9 1 4 5
出力例 5
1907757100 3182585150 458514202 1684028078 1064002576 3897234150 2030460064 441379880 2043536529 1009893320
この入力例は小課題 1,3,6 の制約を満たす．
Time Limit: 1 sec / Memory Limit: 1024 MiB
配点： 100 点
問題文
N 個のライトが横一列に並んでおり，左から順に 1 から N までの番号が付けられている．それぞれのライトの色は赤，緑，青のいずれかである．ライトの色は文字列 S によって表され，ライト i (1 \leqq i \leqq N) の色は，S の i 文字目が R のとき赤，G のとき緑，B のとき青である．最初すべてのライトは点灯している．
JOI 君は点灯しているライトが 1 つ以上ある限り，以下の 3 種類の操作を好きな順番で好きな回数行うことができる．操作を 1 回も行わなくても構わない．
- A 円を払って点灯しているライトの中で最も左にあるものを消灯する．
- B 円を払って点灯しているライトの中で最も右にあるものを消灯する．
- C 円を払って点灯しているライトを 1 つ選び，好きな色へ点灯し直す．
JOI 君は，遠くからこのライトの列を見たときにきれいな白色に見えるようにしたい．そのためには，点灯しているライトを左から見たときの色の並びが RGBRGB...RGB のように RGB（赤緑青）の繰り返しになっている必要がある．ただし，1 つも点灯しているライトが存在しない場合も RGB の繰り返しであるとみなす． GBRGBR や RGBRG などの色の並びは条件を満たさないことに注意せよ．
ライトと操作に必要な金額の情報が与えられたとき，点灯しているライトの色の並びを RGB の繰り返しにするために必要な金額の最小値を求めるプログラムを作成せよ．
制約
- 1 \leqq N \leqq 200\,000．
- S は長さ N の文字列である．
- S の各文字は
R，G，Bのいずれかである． - 1 \leqq A \leqq 10^9．
- 1 \leqq B \leqq 10^9．
- 1 \leqq C \leqq 10^9．
- N, A, B, C は整数である．
小課題
- (4 点) N = 3．
- (22 点) N \leqq 300．
- (19 点) N \leqq 10\,000．
- (9 点) N は 3 の倍数，A = 10^9，B = 10^9，C = 1．
- (10 点) A = 10^9，B = 10^9，C = 1．
- (36 点) 追加の制約はない．
入力
入力は以下の形式で与えられる．
N S A B C
出力
点灯しているライトの色の並びを RGB の繰り返しにするために必要な金額の最小値を，単位 (円) を省いて 1 行で出力せよ．
入力例 1
6 GRBBRG 3 4 5
出力例 1
16
例えば以下のように 4 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．
- 3 円を払って点灯しているライトのうち最も左にあるライト 1 を消灯させる．それぞれのライトの状態は文字列
-RBBRGで表される． - 4 円を払って点灯しているライトのうち最も右にあるライト 6 を消灯させる．それぞれのライトの状態は文字列
-RBBR-で表される． - 4 円を払って点灯しているライトのうち最も右にあるライト 5 を消灯させる．それぞれのライトの状態は文字列
-RBB--で表される． - 5 円を払ってライト 3 を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列
-RGB--で表される．
16 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，16 を出力する．
この入力例は小課題 2,3,6 の制約を満たす．
入力例 2
3 BRG 1000000000 1000000000 1
出力例 2
3
例えば以下のように 3 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．
- 1 円を払ってライト 2 を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列
BGGで表される． - 1 円を払ってライト 3 を選び，青色へ点灯し直す．それぞれのライトの状態は文字列
BGBで表される． - 1 円を払ってライト 1 を選び，赤色へ点灯し直す．それぞれのライトの状態は文字列
RGBで表される．
3 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，3 を出力する．
この入力例は小課題 1,2,3,4,5,6 の制約を満たす．
入力例 3
3 GRB 9 11 14
出力例 3
27
例えば以下のように 3 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．
- 9 円を払って点灯しているライトのうち最も左にあるライト 1 を消灯させる．それぞれのライトの状態は文字列
-RBで表される． - 9 円を払って点灯しているライトのうち最も左にあるライト 2 を消灯させる．それぞれのライトの状態は文字列
--Bで表される． - 9 円を払って点灯しているライトのうち最も左にあるライト 3 を消灯させる．それぞれのライトの状態は文字列
---で表される．
27 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，27 を出力する．1 つも点灯しているライトが存在しない場合も条件を満たすものとすることに注意せよ．
この入力例は小課題 1,2,3,6 の制約を満たす．
入力例 4
9 RGBRGBRGB 1000000000 1000000000 1
出力例 4
0
既にライトの色の並びは RGB の繰り返しになっているため，0 を出力する．
この入力例は小課題 2,3,4,5,6 の制約を満たす．
入力例 5
20 BRGBRGBBGBBBGRRBBBRB 1000000000 1000000000 1
出力例 5
2000000008
この入力例は小課題 2,3,5,6 の制約を満たす．
入力例 6
23 BBGRGBBBBBBGRRGGGGBGGGG 786820955 792349124 710671229
出力例 6
10107224827
この入力例は小課題 2,3,6 の制約を満たす．
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点： 100 点
問題文
JOI 庭園は縦 N 行，横 N 列のマス目状に区切られた正方形の形をしている． 上から i 行目 (1 \leqq i \leqq N)，左から j 列目 (1 \leqq j \leqq N) のマスは区画 (i, j) と呼ばれている．
JOI 庭園は土壌にあまり恵まれていないため，各区画には特定の 1 種類の色の花を，最大 1 本しか植えることができない．
具体的には，区画 (i, j) には A_{i, j} = R のとき赤，A_{i, j} = Y のとき黄，A_{i, j} = B のとき青の色の花を最大 1 本しか植えることができない．
ここで，この庭園の管理者である K 理事長は，航空写真を撮った時の見栄えを良くするため，次の手順で花を植えようと思っている．
- 大きさを表す整数 r を決める．ただし 0 \leqq r \leqq \frac{N-1}{2} を満たさなければならない．
- 中心を表す区画 (x, y) を決める．ただし r+1 \leqq x \leqq N-r，r+1 \leqq y \leqq N-r を満たさなければならない．
- 色 c_0, c_1, c_2, \dots, c_r をそれぞれ赤・黄・青の中から選んで決める．
- それぞれの区画 (x', y') について，d = |x'-x| + |y'-y| に応じて以下の規則で花を植える．ただし，|t| は t の絶対値を表す．
- d \leqq r であるならば，区画 (x', y') には色 c_d の花を植える．
- d > r であるならば，区画 (x', y') には花を植えない．
庭園の大きさ，各区画に植えることができる花の色の情報が与えられたとき，K 理事長が植えることができる花の数の最大値を求めるプログラムを作成せよ．
制約
- 3 \leqq N \leqq 3\,500．
- A_{i, j} は
R，Y，Bのいずれかである (1 \leqq i \leqq N, 1 \leqq j \leqq N)． - N は整数である．
小課題
- (4 点) N = 3．
- (13 点) N \leqq 50．
- (17 点) N \leqq 800．
- (14 点) A_{i, j} \neq
Rを満たす (i, j) (1 \leqq i \leqq N, 1 \leqq j \leqq N) は 5 個以下である． - (16 点) どの (i, j) (1 \leqq i \leqq N-1, 1 \leqq j \leqq N-1) についても，A_{i, j}，A_{i, j+1}，A_{i+1, j}，A_{i+1, j+1} の中に
Rが 3 個以上存在する． - (36 点) 追加の制約はない．
入力
入力は以下の形式で与えられる．
N
A_{1,1}A_{1,2}\cdotsA_{1,N}
A_{2,1}A_{2,2}\cdotsA_{2,N}
\vdots
A_{N,1}A_{N,2}\cdotsA_{N,N}
出力
K 理事長が植えることができる花の数の最大値を 1 行で出力せよ．
入力例 1
3 RYR YBY BYY
出力例 1
5
r = 1，(x, y) = (2, 2) とし，c_0 として青，c_1 として黄を選ぶと，下図のように 5 本の花を植えることができる．ただし，背景色は各区画に植えることができる花の色を示している．
6 本以上の花を植える方法は存在しないため，5 を出力する．
この入力例は小課題 1, 2, 3, 6 の制約を満たす．
入力例 2
9 YYRYBBBYR BYYRRBYBB RBRRBRBBY RYRBRYRBR YYBRYYYRB RRYBRYRBR RBYRBRBRB BRYYRBBBR RBBBYBRRY
出力例 2
25
r = 3，(x, y) = (5, 6) とし，c_0 として黄，c_1 として黄，c_2 として赤，c_3 として青を選ぶと，下図のように 25 本の花を植えることができる．ただし，背景色は各区画に植えることができる花の色を示している．
26 本以上の花を植える方法は存在しないため，25 を出力する．
この入力例は小課題 2, 3, 6 の制約を満たす．
入力例 3
6 RBYRBY BYRBYR YRBYRB RBYRBY BYRBYR YRBYRB
出力例 3
1
この入力例は小課題 2, 3, 6 の制約を満たす．
入力例 4
20 RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRBRRRRRRRRRRRRYRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRYRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRYRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRBR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRR
出力例 4
85
この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす．
入力例 5
10 RRRRRRRRRR RYRRRRRRRR RRRRYRRRRR RBRRRRRRRR RRRRRRRRYR RBRRRRRRRR RRRRBRRRRR RBRRRRRRRR RRRRRRRRYR RRRRRRRRRR
出力例 5
25
この入力例は小課題 2, 3, 5, 6 の制約を満たす．
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点： 100 点
問題文
JOI 王国は N 個の都市からなる王国であり，これらの都市には 1 から N までの番号が付けられている． JOI 王国には，これらの都市を結ぶ一方通行の高速道路が M 本あり，1 から M までの番号が付けられている． 高速道路 i (1 \leqq i \leqq M) を通ると都市 A_i から都市 B_i に移動することができ，通行にかかる時間は L_i である．
それぞれの高速道路を通るたびに，通行料金が発生する． 高速道路 i の通行料金は最も安い時で C_i だが，JOI 王国の労働者は皆時間外労働を嫌うため，ある基準となる時刻 0 から離れれば離れるほど通行料金が増えてしまう． 具体的には，都市 A_i を時刻 t に出発して高速道路 i を通行した場合，通行料金は定数 K を用いて C_i + K\times |t| と表される． ただし，|t| は t の絶対値を表す．
都市 1 に住んでいるあなたは，友達の住む都市 N へ出かける計画を立てている． あなたは高速道路を通って都市 1 から都市 N まで移動したいので，まずはそれが可能かどうか確かめ，可能ならば通行料金の総和が最小でいくらになるかも求めたい． ただし，移動経路や各都市を出発するタイミングは自由に決めることができる． 特に，都市 1 を負の時刻に出発したり，高速道路を通行せずどこかの都市に留まっている時間があったりしてもよい．
高速道路の情報および定数 K が与えられたとき，高速道路を通って都市 1 から都市 N まで移動することが可能かどうか判定し， 可能な場合は通行料金の総和の最小値を求めるプログラムを作成せよ．
なお，この問題の制約の下では，高速道路を通って都市 1 から都市 N まで移動することが可能な場合，通行料金の総和の最小値は必ず整数になることが証明できる．
制約
- 2 \leqq N \leqq 4\,000．
- 1 \leqq M \leqq 8\,000．
- 0 \leqq K \leqq 100\,000．
- 1 \leqq A_i \leqq N (1 \leqq i \leqq M)．
- 1 \leqq B_i \leqq N (1 \leqq i \leqq M)．
- A_i \neq B_i (1 \leqq i \leqq M)．
- 1 \leqq L_i \leqq 1\,000\,000 (1 \leqq i \leqq M)．
- 0 \leqq C_i \leqq 10^9 (1 \leqq i \leqq M)．
- 入力される値はすべて整数である．
小課題
- (9 点) N \leqq 100，M \leqq 200，K = 0．
- (21 点) N \leqq 100，M \leqq 200，L_i \leqq 20 (1 \leqq i \leqq M)．
- (13 点) N \leqq 100，M = N - 1，A_i = i，B_i = i+1 (1 \leqq i \leqq M)．
- (23 点) N \leqq 100，M \leqq 200 であり，以下の制約を満たす．
- N は偶数，\lfloor \frac{B_i}{2} \rfloor - \lfloor \frac{A_i}{2} \rfloor = 1 (1 \leqq i \leqq M)． ここで，\lfloor x \rfloor は x 以下の最大の整数を表す．
- (16 点) N \leqq 100，M \leqq 200．
- (11 点) N \leqq 1\,500，M \leqq 3\,000．
- (7 点) 追加の制約はない．
入力
入力は以下の形式で与えられる．
N M K A_1 B_1 L_1 C_1 A_2 B_2 L_2 C_2 \vdots A_M B_M L_M C_M
出力
高速道路を通って都市 1 から都市 N まで移動することが不可能な場合は，-1 を出力せよ．
可能な場合は，通行料金の総和の最小値を表す整数を 1 行で出力せよ．
入力例 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
出力例 1
15
JOI 王国の都市と道路の様子を図にすると以下のようになる． 丸は都市を，矢印は道路を表し，各道路の横にはその道路の L_i と C_i の値がこの順に書かれている． なお，丸の中に書かれた数字はその都市の番号を表す．
以下のように移動すると通行料金の総和が 15 になる．
- 時刻 -1 : 都市 1 を出発し，都市 3 へ向かう．通行料金が 10+2\times \left|-1\right|=12 かかる．
- 時刻 0 : 都市 3 に到着し，すぐに都市 4 へ向かう．通行料金が 3+2\times |0|=3 かかる．
- 時刻 5 : 都市 4 に到着する．
通行料金の総和が 15 より小さくなるような移動方法は存在しないため，15 を出力する．
この入力例は小課題 2,5,6,7 の制約を満たす．
入力例 2
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
出力例 2
9
入力例 1 とは K の値だけが異なる．
以下のように移動すると通行料金の総和が 9 になる．
- 時刻 -3 : 都市 1 を出発し，都市 2 へ向かう．通行料金が 2+0\times \left|-3\right|=2 かかる．
- 時刻 0 : 都市 2 に到着し，すぐに都市 3 へ向かう．通行料金が 4+0\times |0|=4 かかる．
- 時刻 1 : 都市 3 に到着し，そのまま都市 3 に留まる．
- 時刻 3 : 都市 3 を出発し，都市 4 へ向かう．通行料金が 3+0\times |3|=3 かかる．
- 時刻 8 : 都市 4 に到着する．
通行料金の総和が 9 より小さくなるような移動方法は存在しないため，9 を出力する．
この入力例は小課題 1,2,5,6,7 の制約を満たす．
入力例 3
2 1 10 2 1 4 7
出力例 3
-1
高速道路を通って都市 1 から都市 2 まで移動することは不可能なので，-1 を出力する．
この入力例は小課題 2,5,6,7 の制約を満たす．
入力例 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
出力例 4
37
この入力例は小課題 2,3,5,6,7 の制約を満たす．
入力例 5
8 8 2 1 2 1 5 5 6 3 1 2 4 10 18 3 5 3 1 1 3 4 2 5 6 2 2 2 5 2 3 6 8 1 1
出力例 5
25
同じ (A_i,B_i) のペアを持つ複数の道路が存在することもある．
この入力例は小課題 2,4,5,6,7 の制約を満たす．
入力例 6
6 10 100000 4 2 212037 752027141 2 5 667097 1571491 2 1 769275 576006950 1 2 711969 526189398 5 3 733555 206320177 3 4 364807 802102091 1 4 467240 183184247 3 5 44994 15991843 5 3 613192 782356546 4 6 832593 639529758
出力例 6
47546714005
この入力例は小課題 5,6,7 の制約を満たす．