問題

高校生のピ太郎は毎日徒歩で学校に通っている．

いつもは 6 時に起きるが，今日は深夜遅くまで起きていたせいで二度寝をしてしまった．急いで身支度を済ませたが，ピ太郎は普段通りに歩いていると授業に遅刻してしまうのではないかと心配している．

学校の授業は今からちょうど A+0.5 分後に始まる．また，家から学校までは普段通りに歩くと B 分かかる．

ピ太郎にこのままだと遅刻してしまうか教えてあげるプログラムを作成せよ．

制約

• A,B は整数である．
• 0 \leq A \leq 180．
• 0 < B \leq 180．

小課題

1. (100 点) 追加の制約はない．

入力例 1

20 10

出力例 1

1

この入力例では，ピ太郎は授業が始まる 10.5 分前に学校に到着する．

入力例 2

10 20

出力例 2

0

この入力例では，ピ太郎は授業が始まった 9.5 分後に学校に到着する．

入力例 3

10 10

出力例 3

1

授業は A + 0.5 分後に始まる事に気を付けよ．

問題

ピ太郎はボードゲームで遊んでいる．左から 1 ～ M の番号が振られた M 個の横に連続したマスに N 個の駒が置かれている．駒には 1 ～ N の番号がついていて，駒 i はマス x_i にある．

正整数 K が与えられる．ピ太郎は以下で示す操作 1 ～ K を 1 回ずつ行える．どの順番で操作をしてもよいし，行わない操作があってもよい．

操作 i (1 \leq i \leq K)

• 一度も動かされたことがない駒を 1 つ選び，i マス移動させる．
• つまり，選んだ駒がマス a にあるとき，その駒をマス a-i またはマス a+i に移動させる．
• 移動先が M 個のマスからはみ出してしまう場合は駒を動かすことができない．
• 移動先にすでに駒が置かれていても構わない．

ピ太郎は，どこかのマスにより多くの駒を集めようとしている．最適な操作をしたときの，あるマスに置かれた駒の個数の最大値を求めるプログラムを作成せよ．

制約

• 入力はすべて整数である．
• 1 \leq M \leq 2\,000
• 1 \leq N \leq 2\,000．
• 1 \leq K \leq 2\,000．
• 1 \leq x_i \leq M (1 \leq i \leq N)．

小課題

1. (12 点) x_i = i (1 \leq i \leq N)．
2. (13 点) x_i (1 \leq i \leq N) が取り得る値は 2 種類のみである．
3. (20 点) K \leq 2．
4. (55 点) 追加の制約はない．

入力例 1

5 3 1
1 2 3

出力例 1

2

操作 1 を行い，マス 1 にある駒 1 をマス 2 に移動させればよい．操作 1 は 1 回しか行えないため，これが最適となる．

入力例 2

4 3 3
1 4 4

出力例 2

3

1 つのマスに複数の駒が置かれていることもある．操作 3 を行い，マス 1 にある駒 1 をマス 4 に移動させればよい．

入力例 3

4 2 2
4 1

出力例 3

2

操作 3 は行えないため，マス 1 およびマス 4 には 2 個の駒を集めることができない．しかし，操作 1 と操作 2 を 1 回ずつ行うことで，マス 2 に 2 個の駒を集めることができる．

入力例 4

3 2 1
1 3

出力例 4

1

操作 2 は行えないし，操作 1 は 1 回しか行えない．

入力例 5

5 3 2
2 5 4

出力例 5

3

入力例 6

10 5 4
1 4 1 8 7

出力例 6

4

問題

ピ太郎は N 枚のカードセットを 2 組持っている．1 組目のカードセットには A と名前がついていて，先頭から順に a_1 から a_N の数が書かれている．2 組目のカードセットには B と名前がついていて，先頭から順に b_1 から b_N の数が書かれている．

ピ太郎はカードセット B を好きなように，いつでも何回でも並べ替えられる．

ピ太郎は次のようなゲームを N 回行う．

• i (1 \leq i \leq N) 回目のゲームでは．カードセット A の先頭 i 枚に書かれた数を順に並べた数列を C_i とする．
• カードセット B の各カードに書かれた数を順に並べた数列の中に数列 C_i が連続して登場する回数を最大化するようにカードセット B を並び替える．
• ただし，C_i 同士の登場位置は重なってはいけない．例えば数列 {1 2 1 2 1 2 1 2} は {(1 2 1 2) (1 2 1 2)} と考えると，数列 {1 2 1 2} が 2 回登場している．このとき，{(1 2 1 2) 1 2 1 2} ，{1 2 (1 2 1 2) 1 2} ，{1 2 1 2 (1 2 1 2)} の 3 回と数えることは出来ない．
• カードセット B の各カードに書かれた数を順に並べた数列の中に数列 C_i が連続して登場する回数をそのゲームのスコアとする．

ピ太郎が各ゲームで獲得できるスコアを求めるプログラムを作成せよ．

制約

• 入力はすべて整数である．
• 2 \leq N \leq 100\,000．
• 1 \leq a_i, b_i \leq 100\,000 (1 \leq i \leq N)．

小課題

1. (16 点) N \leq 8．
2. (10 点) a_i = 1 (1 \leq i \leq N)．
3. (24 点) N \leq 1\,000．
4. (50 点) 追加の制約はない．

入力例 1

5
1 2 3 4 5
1 2 2 1 3

出力例 1

2
2
1
0
0

例えば {1 2 3 2 1} と並べ替えることで C_1 を 2 個，{3 1 2 1 2} と並べ替えることで C_2 を 2 個，{2 1 2 3 1} と並べ替えることで C_3 を 1 個登場させることができる．

この入出力例は小課題 1,3,4 を満たしている．

入力例 2

5
1 1 1 1 1
1 1 1 1 1

出力例 2

5
2
1
1
1

カードセット B から得られる数列として考えられるのは {1 1 1 1 1} だけである．

この入出力例は小課題 1,2,3,4 を満たしている．

問題

ピ太郎とあなたは楽しい楽しい楽しいゲームをしている．

ピ太郎は 10 進法で N 桁の正の整数を持っている．この数の先頭は 0 ではない．

ピ太郎はこれを上の桁から 1 桁ずつ読み上げていく．あなたはピ太郎が数字を言うたびに，ピ太郎がそれまで読み上げた数字を読み上げた順に上の桁から並べてできる整数を K とし，K が 3 の倍数であり 5 の倍数でないなら Fizz，5 の倍数であり 3 の倍数でないなら Buzz，15 の倍数なら FizzBuzz と発言する．K が 3 の倍数でも 5 の倍数でもないならあなたは何も言わない．例えばピ太郎が 12\,345\,670 という数を読み上げていくと，あなたは Fizz，Fizz，FizzBuzz，Fizz，Buzz と 5 回発言することになる．

あなたはゲームのプレイ記録を確認している．記録にはあなたがちょうど M 回だけ発言したことと，i (1 \leq i \leq M) 回目の発言が S_i であったことが書かれている．

この記録を満たす N 桁の正の整数としてありえるものの個数を 1\,000\,000\,007 で割った余りを求めるプログラムを作成せよ．

制約

• 1 \leq N \leq 1\,000．
• 0 \leq M \leq N．
• S_i は Fizz，Buzz，FizzBuzz のいずれかである (1 \leq i \leq M)．

小課題

1. (10 点) N \leq 6．
2. (2 点) N = M，S_i (1 \leq i \leq N) は FizzBuzz．
3. (14 点) N = M，S_i (1 \leq i \leq N) は Fizz．
4. (14 点) N = M，S_i (1 \leq i \leq N) は Buzz．
5. (20 点) N = M．
6. (40 点) 追加の制約はない．

入力例 1

3 2
Buzz
FizzBuzz

出力例 1

7

105，255，405，525，585，705，855 が与えられた記録を満たしている．

入力例 2

2 2
Buzz
FizzBuzz

出力例 2

0

入力例 3

1 0

出力例 3

5

入力例 4

10 5
Fizz
FizzBuzz
Fizz
Buzz
FizzBuzz

出力例 4

3232774

入力例 5

2 1
FizzBuzz

出力例 5

3

例えば 01 や 07 といった数は 2 桁とはみなされないので注意せよ．

問題

時は 22 世紀，新たに大手前高校の校長となったピ太郎の尽力により，大手前プロコンは世界中から注目されるイベントとなっていた．

大手前プロコン 21XX の開会式では，N 人の生徒が一列に並んで行進する．生徒が進む道は数直線としてあらわされる．生徒たちは全員，数直線上の正の方向を向いて行進する．時刻 0 に，前から i 番目 (1 \leq i \leq N) の生徒は，座標 −i に立っている．座標 0 には，旗手のピ太郎校長が立っている．

ピ太郎校長は，単位時刻あたり 1 だけ道の上を正の方向に進む．

すべての生徒には呑気さという値が定まっている．前から i 番目の生徒の呑気さは D_i である．各生徒は単位時間かけて同時に以下の行動を取る．

• 時刻 0 に前から i 番目にいた生徒は，時刻 0 に自分の目の前にいた参加者 (生徒またはピ太郎校長) との距離がちょうど D_i なら，距離 1 だけ 道の上を正の方向に進む．そうでないなら，動かない．

あなたは，開会式を見に来たきたむー教頭である．あなたは写真を撮らなければならなかったが，開会式の間中ずっと熟睡していた．仕方がないので，あなたは会場の写真を撮り，その写真に参加者の絵を描いて誤魔化すことにした．

誤魔化したことを明るみに出さないために，また絵を描く手間を見積もるために，あなたは以下の Q 個の値を知っておきたい．

• 時刻 T_j における，L_j 以上 R_j 以下の座標に立っている参加者の人数 (1 \leq j \leq Q)

各生徒の呑気さと，Q 個の質問の情報が与えられるので，それぞれの質問ごとに，条件を満たす参加者の人数を求めるプログラムを作成せよ．

制約

• 入力はすべて整数である．
• 1 \leq N \leq 500\,000．
• 1 \leq Q \leq 500\,000．
• 1 \leq D_i \leq 1\,000\,000\,000 (1 \leq i \leq N)．
• 1 \leq T_j \leq 1\,000\,000\,000 (1 \leq j \leq Q)．
• 1 \leq L_j \leq R_j \leq 1\,000\,000\,000 (1 \leq j \leq Q)．

小課題

1. (15 点) N, Q, D_i, T_j, L_j, R_j \leq 1\,000 (1 \leq i \leq N, 1 \leq j \leq Q)．
2. (16 点) T_i = T_j (1 \leq i,j \leq Q)．
3. (69 点) 追加の制約はない．

入力例 1

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

出力例 1

0
1
1
2
1
1

時刻 0 には，校長，選手 1，2，3 の順に，それぞれ座標 0,-1,-2,-3 にいる．

時刻 1 にはそれぞれ，座標 1,-1,-2,-3 にいる．

時刻 2 にはそれぞれ，座標 2,0,-2,-3 にいる．これは時刻 1 から時刻 2 にかけて，それぞれ次のような行動を取ったからである．

• 校長は場所 2 に移動する
• 選手 1 は前の参加者との差が 2 になったから場所 0 に移動する
• 選手 2 は前の参加者との差が 5 未満だから動かない
• 選手 3 は前の参加者との差が 3 未満だから動かない

時刻 3 にはそれぞれ，座標 3,1,-2,-3にいる．

入力例 2

4 2
1
1
1
1
2 1 4
1 3 6

出力例 2

2
0

入力例 3

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

出力例 3

0
2
0
4
1
4

問題

天秤の左側の皿に N 枚のコインが縦に積まれており，上から順にコイン 1, コイン 2 , \cdots, コイン N と呼ぶことにする．これらのコインは酸化などによって毎日質量が変化する．i 日目のコイン j の質量は M_{i,j} である．

あなたは D 日間にわたって毎日以下の遊びをする．

• 天秤の左側の皿に積まれているコインを上から好きな枚数だけ右側の皿に移動する．1 枚も移動させなくても構わない．
• 天秤を釣り合わせるのに必要な分銅の質量を G とする．G は左右の皿に積まれているコインの合計質量の差の絶対値である．
• あなたはコスト G を払う．

D 日間にわたって払う必要のある合計コストの最小値を求めるプログラムを作成せよ．

制約

• 1 \leq N \leq 2\,000．
• 1 \leq D \leq 2\,000．
• 1 \leq M_{i,j} \leq 1\,000\,000\,000 (1 \leq i \leq D, 1 \leq j \leq N)．

小課題

1. (8 点) N = 2．
2. (8 点) N = 3．
3. (14 点) N \leq 10，D \leq 10．
4. (24 点) N \leq 200，D \leq 200．
5. (46 点) 追加の制約はない．

入力例 1

3 4
10 8 3
5 7 8
9 6 1
2 8 9

出力例 1

14

以下のように操作を行うと，払う合計コストは 14 となり，このときが最小である． また，この入力例は小課題 2, 3, 4, 5 の制約を満たす．

• 1 日目にはコインを 1 枚移動する．払うコストは |10 - (8+3)| = 1 である．
• 2 日目にはコインを 1 枚も移動しない．払うコストは |5 - (7+8)| = 10 である．
• 3 日目にはコインを 1 枚も移動しない．払うコストは |9 - (6+1)| = 2 である．
• 4 日目にはコインを 1 枚移動する．払うコストは |(2+8) - 9| = 1 である．

入力例 2

10 8
50 8 226 426 123 30 114 304 230 994
402 230 316 555 193 95 547 66 171 1000
399 30 24 177 97 325 315 1 361 993
606 973 94 32 391 116 64 782 784 631
759 1000 130 503 81 538 260 41 71 118
1000 148 223 149 113 1 110 366 56 113
1000 245 104 383 171 27 244 34 204 121
55 1000 32 151 59 44 270 386 36 104

出力例 2

6733

この入力例は小課題 3, 4, 5 の制約を満たす．

入力例 3

1 10
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

出力例 3

10000000000

この入力例は小課題 3, 4, 5 の制約を満たす． 出力が 32 ビット整数型に収まらない場合があることに注意せよ．

問題

ピーターランドは碁盤の目のような構造になっており，N \times N 個の区画からなる．西から i (1 \leq i \leq N) 番目，北から j (1 \leq j \leq N) 番目の区画を (i, j) と表す．また，ある区画に対して，東西南北いずれかに隣接している区画をその区画の隣の区画と呼ぶ．

高校生のピ太郎はピーターランドに住むごく普通のピーターラビットである．いや，であったというのが正しいであろうか．度重なる遅刻を改善しようと試みた結果，ピ太郎はワープすることができるようになってしまったのである．ピ太郎は通常，ある区画から隣の区画へ徒歩で移動するのに 1 ビョウかかる．しかし，このワープ能力を用いるとピ太郎は隣の区画へ 0 ビョウで移動することができる．

ただし，ピ太郎は太陽のエネルギーを使ってワープするので，どこでも，どの方向にでもワープができるわけではない．ピ太郎がワープできる日当たりの良い範囲に関する M 個の情報が与えられる．k 個目の情報 (1 \leq k \leq M) では整数 T_k, A_k, B_k, C_k, D_k が与えられ，次のことを意味する．

• T_k = 1 のとき，A_k \leq i \leq B_k ，C_k \leq j \leq D_k - 1 について，ピ太郎は (i, j) と (i, j + 1) を双方向に好きなだけワープできる．
• T_k = 2 のとき，A_k \leq i \leq B_k - 1 ，C_k \leq j \leq D_k について，ピ太郎は (i, j) と (i + 1, j) を双方向に好きなだけワープできる．

ピ太郎はまた深夜遅くまで起きていたせいで学校に遅刻しそうである．ピ太郎の家は (P, Q) に，ピ太郎の学校は (R, S) にある．ピ太郎が家から学校に行くのにかかる時間の最小値を求めたい．

制約

• 入力はすべて整数である．
• 1 \leq N \leq 1\,000\,000\,000．
• 0 \leq M \leq 1\,000．
• 1 \leq P, Q, R, S \leq N．
• T_k は 1 または 2 (1 \leq k \leq M)．
• T_k = 1 のとき，
  • 1 \leq A_k \leq B_k \leq N (1 \leq k \leq M)．
  • 1 \leq C_k < D_k \leq N (1 \leq k \leq M)．
• T_k = 2 のとき，
  • 1 \leq A_k < B_k \leq N (1 \leq k \leq M)．
  • 1 \leq C_k \leq D_k \leq N (1 \leq k \leq M)．

小課題

1. (4 点) M = 0．
2. (12 点) T_k = 1，A_k = B_k = 1，C_k = D_k - 1，P = 1，R = 1 (1 \leq k \leq M)．
3. (13 点) T_k = 1，A_k = B_k = 1，P = 1，R = 1 (1 \leq k \leq M)．
4. (18 点) N \leq 300，M \leq 300．
5. (53 点) 追加の制約はない．

入力例 1

8 9
2 1 3 7
2 3 8 8 8
2 1 3 1 2
2 2 5 3 4
2 5 7 7 7
1 6 8 3 7
1 1 4 7 8
1 1 1 2 4
2 3 6 4 5
2 6 7 1 1

出力例 1

3

(2, 1) から (3, 7) まで最短時間で移動したい．この時，図のような経路で移動すると，(2, 1) - (2, 2) の移動と (1, 4) - (2, 4) の移動と (5, 7) - (4, 7) の移動以外はすべてワープで済むので，3 ビョウで家から学校まで移動することができる．また，これより短い時間で家から学校へ行くことはできないので，3 を出力する．

この入出力例は小課題 4, 5 を満たしている．

入力例 2

10 6
1 1 1 9
1 1 1 1 2
1 1 1 7 10
1 1 1 3 5
1 1 1 4 6
1 1 1 1 2
1 1 1 8 10

出力例 2

2

この入出力例は小課題 3, 4, 5 を満たしている．

入力例 3

12 0
1 3 1 11

出力例 3

8

この入出力例は小課題 1, 2, 3, 4, 5 を満たしている．

問題

N 個の飴があり，i 番目の飴の美味しさは A_i である．

f(l,r) (1 \leq l \leq r \leq N) を，l 番目から r 番目の飴において下記の条件の下で，食べた飴の美味しさの総和の最大値と定義する．

条件：2 個連続して食べない．すなわち，l \leq i < r を満たす全ての i において，i 番目の飴と i+1 番目の飴を両方食べることはできない．

それぞれの飴の美味しさが与えられたとき，1 \leq l \leq r \leq N を満たすすべての組 (l,r) についての f(l,r) の総和を 998\,244\,353 で割った余りを求めるプログラムを作成せよ．

制約

• 1 \leq N \leq 200\,000．
• 1 \leq A_i \leq 1\,000\,000\,000 (1 \leq i \leq N)．

小課題

1. (10 点) N \leq 300．
2. (20 点) A_i \leq 300 (1 \leq i \leq N)．
3. (70 点) 追加の制約はない．

入力例 1

3
1 2 3

出力例 1

15

l=2,r=3 の場合，2 番目と 3 番目の飴を両方とも食べることができず，3 番目の飴だけを食べるのが最適になるので，f(l,r)=3 になる． l=1,r=3 の場合，1 番目と 3 番目の飴を食べるのが最適になるので，f(l,r)=1+3=4 になる．

出力する値は f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+4+2+3+3=15 になる．

入力例 2

4
1 100 100 1

出力例 2

805

入力例 3

1
1000000000

出力例 3

1755647

998\,244\,353 で割った余りを出力せよ．

入力例 4

10
850534838 749655434 745817507 991867417 645519349 373697182 427765279 182404140 260664174 366393413

出力例 4

554337161

問題

ピーターランドには N 個の都市があり，1 から N までの番号が付いている．2 個の都市を双方向に結ぶ道がちょうど N 本あり，i 番目 (1 \leq i \leq N) の道は都市 A_i と都市 B_i を結んでいる．どの都市からどの都市へも，いくつかの道を使って移動できる．

2 個の都市の間の距離を，一方から他方へ移動するために通る必要がある道の本数の最小値と定める．N 個の都市から2 個の都市を選ぶ方法は \frac{N (N - 1)}{2} 通りあるが，それらについての距離の 2 乗の総和を 998\,244\,353 で割った余りを求めよ．

制約

• 2 \leq N \leq 500\,000．
• 1 \leq A_i \leq N (1 \leq i \leq N)．
• 1 \leq B_i \leq N (1 \leq i \leq N)．
• A_i \neq B_i (1 \leq i \leq N)．
• どの都市からどの都市へも，いくつかの道を使って移動できる．

小課題

1. (5 点) N \leq 400．
2. (5 点) N \leq 4\,000．
3. (30 点) (A_1, B_1) = (A_2, B_2) = (1, 2)，A_i \neq 1 (3 \leq i \leq N)，B_i \neq 1 (3 \leq i \leq N)．
4. (60 点) 追加の制約はない．

入力例 1

4
1 2
2 3
3 1
1 4

出力例 1

12

• 都市 1 と都市 2 の距離は 1
• 都市 1 と都市 3 の距離は 1
• 都市 1 と都市 4 の距離は 1
• 都市 2 と都市 3 の距離は 1
• 都市 2 と都市 4 の距離は 2
• 都市 3 と都市 4 の距離は 2

であるから，距離の 2 乗の総和は 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 2^2 = 12 である．

入力例 2

6
1 2
1 2
6 3
4 3
3 2
5 2

出力例 2

65

入力例 3

10
7 4
9 7
5 8
8 4
3 7
1 9
10 9
4 1
2 5
6 4

出力例 3

384