問題文

N 個の駅があり、M 本の線路で結ばれています。

線路 i は駅 A_i と駅 B_i を直接結んでおり、路線長は L_i mです。

a < c,a \neq b,b \neq c を満たす (a,b,c) の組で、駅 a と駅 b の間、駅 b と駅 c の間を直接結ぶ線路が存在し、かつ 2 つの路線長の和が 2540 mとなるものがいくつあるか求めてください。

同じ駅どうしを結ぶ路線や、線路の通らない駅が存在しないことは保証されますが、全ての駅が連結とは限りません。

制約

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i < B_i \leq N
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• 1000 \leq L_i \leq 2000
• 入力は全て整数
• 線路の通らない駅は存在しない

入力例 1

4 3
1 2 1420
2 3 1120
3 4 1420

出力例 1

2

(1,2,3),(2,3,4) が条件を満たします。

入力例 2

4 2
1 2 1920
3 4 1125

出力例 2

0

問題文

N 人のクラスがあり、色 1,2,...,M の中から 1 つの色を選んでテーマカラーを決めることとなりました。

それぞれの人が同確率でどれかの色 1 つに投票するとき、色 i(1 \leq i \leq M) に r_i 票集まる確率を p とします。

p \geq 10^{-x} を満たす最小の整数 x を求めてください。

ただし、p に 10^{-6} 以下の相対誤差が生じても x は変わらないことが保証されるものとします。

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq r_i \leq N
• r_1+r_2+...+r_M=N
• 入力は全て整数
• p に 10^{-6} 以下の相対誤差が生じても解は変わらない

入力例 1

3 2
1 2

出力例 1

1

p=0.375 より、p \geq 10^{-x} を満たす最小の整数は 1 となります。

入力例 2

120 5
18 36 31 12 23

出力例 2

8

問題文

ある電話会社では、通話料金のプランが N 種類あります。

プラン i を選んだ場合、ひと月あたり A_i 分以内の通話時間ならば B_i 円、それ以上の通話時間の場合は 超過時間 1 分あたり 1 円の通話料金がかかります。

例えば、通話時間が x(x ≥ A_i) 分の場合のプラン i での通話料金は B_i+(x-A_i) 円です。

また、全てのプラン i に対して、通話時間が A_i 分の場合には他のどのプランよりも通話料金が 1 円以上安くなることが保証されます。

人が M 人いて、人 i のひと月あたりの通話時間は T_i 分です。

全ての人に対して、とりうる通話料金の最安値を求めてください。

制約

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• 1 \leq T_i \leq 10^9
• 入力は全て整数
• 通話時間が A_i 分の場合にプラン i が他のどのプランよりも通話料金が 1 円以上安くなることが保証される

入力例 1

2
5 6
3 5
2
4
8

出力例 1

6
9

• 人 1 がプラン 1 を選んだ場合の通話料金は 6 円です。

• 人 1 がプラン 2 を選んだ場合の通話料金は 6 円です。 よって、人 1 の通話料金の最安値は 6 円です。

• 人 2 がプラン 1 を選んだ場合の通話料金は 9 円です。

• 人 2 がプラン 2 を選んだ場合の通話料金は 10 円です。 よって、人 2 の通話料金の最安値は 9 円です。

入力例 2

4
12 5
1 1
7 3
243 32
6
632
188
69
54
14
36

出力例 2

421
32
32
32
7
29

問題文

英大文字および英小文字によって構成される N 個の文字列 A_1,A_2,...,A_N があります。

文字列の 略称 を以下のように定義します。

• 文字列 S があるとき、1 \leq i < j < k \leq |S| を満たす任意の i,j,k に対し、S_i S_j S_k は S の略称となる。

3 文字からなる文字列のうち、A_1,A_2,...,A_N のうち最も多くの文字列の略称となるものを求めてください。

ただし、複数ある場合は、辞書順で最初のものを求めてください。

なお、辞書順において、文字の種類にかかわらず英大文字は英小文字より必ず先になるとします。

制約

• 1 \leq N \leq 30000
• 3 \leq |A_i|
• |A_1|+|A_2|+...+|A_N| \leq 90000
• A_i は英大文字および英小文字からなる

入力例 1

4
aKIHaBaRa
aKIBa
aSaKUSa
SHINKIBA

出力例 1

KIB

3 つの文字列の略称となるものは KIB,aKa ですが、これらのうち辞書順で最初の KIB を出力するとよいです。

辞書順において、英大文字は英小文字より必ず先になるので、K がa より先になることに注意してください。

入力例 2

3
abc
def
ghi

出力例 2

abc

問題文

高橋王国には 0 から N までの番号がついた N+1 箇所の町があります。

運動不足の高橋君は町 0 から町 N まで歩いて向かうことにしました。 高橋君は K 本の空のペットボトルを持っています。

高橋君は町 i(0 \leq i < N) にいるとき、以下の 2 種類の行動を行うことができます。

• A_i 円払い、1 本の空のペットボトルに水を注いでもらう。この行動は何度でも行うことができる。
• 水が入ったペットボトルを 1 本飲み干し、空のペットボトルにする。高橋君は町 i から町 i+1 へ移動する。

高橋君が町 N に到着するまでに必要な資金の最小値を求めてください。

制約

• 1 \leq K \leq N \leq 10^{5}
• 1 \leq A_i \leq 10^{9}
• 与えられる入力は全て整数

入力例 1

6 3
2 7 1 8 2 8

出力例 1

9

• 町 0 で 2 本のペットボトルに水を注いでもらう
• 町 1 へ移動する
• 町 2 へ移動する
• 町 2 で 3 本のペットボトルに水を注いでもらう
• 町 3 へ移動する
• 町 4 へ移動する
• 町 4 で 1 本のペットボトルに水を注いでもらう
• 町 5 へ移動する
• 町 6 へ移動する
• このように行動したとき 9 円で町 6 へ到着することが可能であり、これが最適です

入力例 2

13 4
4 3 9 1 3 8 2 6 11 9 2 15 40

出力例 2

26

問題文

高橋君の冬休みは N 日あります。 高橋君は N 日間の食事の予定を考えています。

i 日目の予定は T_i が 0 ならばラーメン屋に行く予定であり、 T_i が 1 ならばレストランに行く予定です。食事の美味しさは A_i です。

高橋君には グルメ度 があり、はじめグルメ度は 0 です。 高橋君がラーメン屋でご飯を食べた場合、グルメ度は 1 減少 します。 高橋君がレストランでご飯を食べた場合、グルメ度は 1 増加 します。

高橋君はグルメ度を 0 以上 K 以下に保ちたいです。 高橋君は 0 個以上の食事の予定をキャンセルし、自炊をすることができます。自炊をした場合、グルメ度は変化せず、食事の美味しさは 0 です。

高橋君が冬休みで得られる美味しさの総和の最大値を求めてください。

制約

• 1 \leq K \leq N \leq 10^{5}
• 1 \leq A_i \leq 10^9
• T_i は 0 あるいは 1
• 与えられる入力は全て整数

入力例 1

8 2
1 3
1 7
0 2
1 8
1 4
0 6
0 2
0 4

出力例 1

31

• 1 日目：自炊をする。グルメ度は 0 のままです
• 2 日目：レストランに行く。グルメ度は 1 になります
• 3 日目：ラーメン屋に行く。グルメ度は 0 になります
• 4 日目：レストランに行く。グルメ度は 1 になります
• 5 日目：レストランに行く。グルメ度は 2 になります
• 6 日目：ラーメン屋に行く。グルメ度は 1 になります
• 7 日目：自炊をする。グルメ度は 1 のままです
• 8 日目：ラーメン屋に行く。グルメ度は 0 になります
• 得られる食事の美味しさの総和は 7+2+8+4+6+4 = 31 となり、これが最大です。

入力例 2

15 3
0 3
1 4
1 5
0 2
0 9
0 11
1 6
1 2
1 6
0 4
1 7
0 4
1 8
1 4
1 9

出力例 2

73

入力例 3

5 3
1 1000000000
0 1000000000
1 1000000000
0 1000000000
1 1000000000

出力例 3

5000000000

• 答えが大きくなりうることに注意してください

問題文

高橋君は N 羽のひよこを M 個の鳥かごに振り分けて入れることにしました。 ひよこには 1 から N の番号がついており、ひよこ i の大きさは A_i です。

鳥かごは狭いため、どのひよこも同じ鳥かごにいるひよこの大きさの和(そのひよこ自身も含む)だけストレスを受けます。

ひよこが受けるストレスの総和の最小値を求めてください。

制約

• 1 \leq M \leq N \leq 2{,}000
• 1 \leq A_i \leq 10^9
• 与えられる入力は全て整数

入力例 1

5 3
3 6 2 15 9

出力例 1

55

• (1,2),(3,5),(4) と鳥かごに入れたとき、受けるストレスは 9+9+11+15+11 = 55 となり、これが最小です

入力例 2

13 4
4 3 9 1 3 8 2 6 11 9 2 15 40

出力例 2

304

入力例 3

4 2
1000000000 1000000000 1000000000 1000000000

出力例 3

8000000000

• 答えが大きくなりうることに注意してください

問題文

AtCoder共和国は 1 から N までの番号がついた町と 1 から N-1 の番号がついた N-1 本の道からできています。それぞれの町は道をたどって到達可能です。

道 i は町 A_i と B_i を双方向につなぐ道で、移動に D_i だけ時間がかかります。

AtCoder共和国で 1 から M までの番号がついた M 個のオンサイトコンテストが開催されることになりました。

コンテスト i は町 C_i で開催され、開始時刻は S_i で終了時刻は E_i です。また、コンテストの優勝賞金は X_i 円です。

賞金稼ぎの高橋君は、賞金をできる限りたくさんもらいたいです。高橋君はとても強いので参加したコンテスト全てで優勝可能です。

高橋君がコンテスト i に参加するためには、S_i \leq t < E_i を満たすいずれの時刻 t においても町 C_i にいて他のコンテストに参加していない必要があります。 詳しくはサンプル 1 も参照してください。

高橋君が時刻 0 の時点で好きな位置にいることができるときの、高橋君が得られる賞金の総和の最大値を求めてください。

制約

• 1 \leq N,M \leq 7 \times 10^{4}
• 1 \leq A_i < B_i \leq N
• 1 \leq D_i,X_i \leq 10^{9}
• 1 \leq S_i < E_i \leq 10^{9}
• 1 \leq C_i \leq N
• 与えられる入力は全て整数
• 全ての町は道を辿って到達可能

入力例 1

5 4
1 2 2
2 3 3
2 4 1
4 5 5
1 5 1 5
2 5 3 7
8 15 4 5
12 16 5 9

出力例 1

10

• 時刻 0 に町 1 にいる
• 時刻 1 まで留まる
• 時刻 1 に町 1 で開催されるコンテスト 1 に参加する
• 時刻 5 に町 2 に向かって移動する
• 時刻 7 に町 4 に向かって移動する
• 時刻 8 に町 4 で開催されるコンテスト 3 に参加する
• 得られる賞金の総和は 10 となり、これが最大です

入力例 2

11 10
5 9 1
2 9 5
4 8 4
2 6 1
3 7 3
5 8 2
2 11 5
3 11 1
1 4 3
9 10 3
1 7 11 10
2 8 9 12
8 15 3 11
2 3 2 4
3 6 4 6
7 9 5 9
4 8 1 7
11 18 6 9
10 14 6 4
5 11 7 11

出力例 2

21

入力例 3

2 6
1 2 1000000000
1 2 1 1000000000
3 4 1 1000000000
5 6 1 1000000000
7 8 1 1000000000
899999999 900000000 1 1000000000
999999999 1000000000 2 1000000000

出力例 3

5000000000

• 答えは非常に大きくなりうることに注意してください

問題文

高橋君は夏休みの宿題を片付けることにしました。

宿題は 1 から N までの番号がついた N 個の問題からなります。 問題 i は解くのに 2^{A_i} 秒かかり、B_i 点だけ得点が得られます。

高橋君は得られた得点の総和が K 以上になるように問題を解く必要があります。これを達成するために必要な時間の最小値を求めてください。

制約

• 1 \leq N \leq 10^{5}
• 0 \leq A_i \leq 30
• 1 \leq B_i \leq 10^{9}
• 1 \leq K \leq Σ{B_i}
• 与えられる入力は全て整数

入力例 1

6 24
1 5
0 4
1 9
2 10
2 11
3 15

出力例 1

7

• 問題 2,3,5 を解くと、7 秒間で 24 点が得られ、これが最適です。

入力例 2

13 105
0 1
3 8
5 28
0 1
0 2
4 17
5 26
5 33
3 8
4 19
3 7
2 4
4 17

出力例 2

98

入力例 3

5 5000000000
30 1000000000
30 1000000000
30 1000000000
30 1000000000
30 1000000000

出力例 3

5368709120

• 答えが大きくなりうることに注意してください

問題文

長さ N の数列 S_{0} と T が与えられます。 ここで、N はある自然数 r に対して 2^{r} と表せることが保証されます。

あなたは 0 回以上 500 回以内、操作を行うことができます。あなたの目的は操作回数を k として S_{k} と T を一致させることです。

i 回目の操作は以下のようにして行われます。

• 0 \leq x < i, 0\leq y < i を満たす整数 x,y、-(N-1) \leq f \leq N-1 を満たす整数 f を指定する
• その後、x,y のみからなる長さ N の文字列 s を指定する
• x,y,f,s を用いて長さ N の数列 S_{i} を作る
  • S_{i,j} は s_{j} が x ならば、S_{x,j} となる
  • S_{i,j} は s_j が y ならば、S_{y,j-f} となる。ただし、1 \leq j-f \leq N を満たさなくてはならない

目的が達成可能かどうか判定し、可能ならば、操作の一例を出力してください。不可能ならば代わりに -1 を出力してください。

操作についてはサンプル 1 も参照してください。

制約

• 2 \leq N \leq 8192
• 1 \leq S_{0,j},T_{j} \leq N
• N はある自然数 r に対して 2^{r} と表せる
• 与えられる入力は全て整数

入力例 1

4
1 2 3 4
2 4 3 4

出力例 1

2
0 0 1 xxyx
0 1 -2 yyxx

• 1 回目の操作では x=0,y=0,f=1,s=xxyx を指定して操作を行います
• S_{1,1},S_{1,2},S_{1,4} はそれぞれ S_{0,1},S_{0,2},S_{0,4} に、S_{1,3} は S_{0,2} となります。よって S_{1}=(1,2,2,4) となります
• 2 回目の操作では x=0,y=1,f=-2,s=yyxx を指定して操作を行います
• S_{2,3},S_{2,4} はそれぞれ S_{0,3},S_{0,4} となり、S_{2,1},S_{2,2} はそれぞれ S_{1,3},S_{1,4} となります。よって S_{2}=(2,4,3,4) となります
• S_{2} と T が一致したため正解です

入力例 2

4
3 1 2 3
1 2 3 4

出力例 2

-1

• 目的が達成不可能な場合は -1 を出力してください