問題文

この春から社会人になったゴジラさんは、 M 万円の奨学金を N ヶ月間に分割して返済しようとしています。

毎月の返済額は、以下のルールによって決まっています。

• i ヶ月目( 1 \leq i \leq N-1 )： M/N の小数点以下を切り捨てた金額(万円)。
• N ヶ月目：未返済の金額全て。

ゴジラさんは N ヶ月目に奨学金を何万円返済しますか。

制約

• 入力はすべて整数である。
• 2 \leq N \leq M \leq 100

入力例 1

7 3

出力例 1

3

1 ヶ月目と 2 ヶ月目にそれぞれ 2 万円を返済するので、3 ヶ月目には 3 万円を返済します。

入力例 2

100 20

出力例 2

5

問題文

夜のテレビ番組「こんばんはゴジラです」では、次のようなパネルめくりゲームを実施しています。

ゲームの参加者であるあなたは、初めに 0 円を持っています。

各パネルには記号と非負整数が 1 つずつ書かれており、 i 番目のパネルに書かれた記号と非負整数はそれぞれ c_i, a_i です。

あなたが i 番目のパネルを開けたとき、以下のルールに従ってあなたの所持金が変化します。

• c_i= + のとき：所持金が a_i 円増える。
• c_i= - のとき：所持金が a_i 円減る。
• c_i= * のとき：所持金が a_i 倍になる。

あなたは、 N 枚のパネルのうち 0 枚以上のパネルを、1 枚ずつ好きな順番で開けることができ、途中でいつでもゲームを終了することができます。また、ゲーム途中及び終了時に所持金が負の値になってもかまいません。

あらかじめどのパネルに何が書かれてあるかを知っているあなたは、ゲーム終了時の自分の所持金を最大化しようとしました。ゲーム終了時の所持金の最大値 M を答えてください。

制約

• 1 \leq N \leq 1000
• 0 \leq a_i \leq 1000
• c_i は+, -, * のいずれかである。
• ゲーム終了時の所持金の最大値 M は 10^9 を超えない。

入力例 1

4
+ 100
- 80
* 3
+ 300

出力例 1

1200

「 +100 」,「 +300 」,「 *3 」のパネルを順に開けた後ゲームを終了することによって、 1200 円を得ることができます。

入力例 2

3
- 314
- 159
- 265

出力例 2

0

1 枚もパネルを開かずにゲームを終了することもできます。

入力例 3

4
* 8
+ 7
* 0
* 5

出力例 2

280

問題文

バンズ文字列とは、以下によって定義される、文字 ( および ) からなる文字列のことです。

1. 空文字列はバンズ文字列である。
2. A がバンズ文字列であるとき、( と A と ) を順に連結した文字列はバンズ文字列である。
3. A, B がバンズ文字列であるとき、A と B を連結した文字列はバンズ文字列である。
4. これら以外の文字列はバンズ文字列ではない。

上のようにしてバンズ文字列を生成するにあたって、 2. によって同時に追加された ( と ) をペアにして、これを対応バンズと呼ぶことにします。
バンズ文字列では、任意の文字がある対応バンズに属し、どの文字も複数の対応バンズに属さないことがわかります。

また、バーガー文字列とは、以下によって定義される、文字 ( , ) および | からなる文字列のことです。

• 文字 | をすべて取り除くと、バンズ文字列になる。
• 文字 | は2つ以上連続しない。

長さ N のバンズ文字列 S が与えられます。 あなたは S に文字 | を K 個挿入し、バーガー文字列を作ることにしました。
バーガー文字列に含まれるある対応バンズの美味しさとは、その2文字 ( と ) の間にある | の個数のことです。
バーガー文字列の美味しさとは、それに含まれるすべての対応バンズの美味しさの和のことです。

あなたが作ることのできるバーガー文字列の美味しさの最大値を求めてください。

制約

• 1 \leq K < N \leq 10^5
• K, N は整数である。
• |S|=N
• S はバンズ文字列である。

入力例 1

6 1
(())()

出力例 1

2

((|))() を作るのが最適です。

入力例 2

8 2
((()))()

出力例 2

5

(((|)|))() を作るのが最適です。

問題文

A 枚のコインがある 1 つの山と、 B 枚のコインがある 1 つの山があります。 この2つの山を使ってAliceとBobがゲームをします。

Aliceを先手として、2 人は以下の操作を交互に繰り返します。

• 1 枚以上のコインがある山を 1 つ選ぶ。そこにあるコインの枚数を X とする。
• その後、2 つの山からそれぞれ 0 枚以上のコインを取り除く。
• ただし、取り除くコインの枚数の合計は X でなければならない。

どの山にもコインがなくなった時点で終了し、最後に操作した人が勝ちます。

2 人が最適に行動したとき、Aliceが勝つかどうか判定してください。

制約

• 1 \leq A \leq 10^5
• 1 \leq B \leq 10^5
• 入力はすべて整数である。

入力例 1

2 2

出力例 1

Yes

Aliceがそれぞれの山から 1 枚ずつコインを取って (1, 1) にすると、Bobは残りのどちらか 1 枚を取って (1, 0) にするしかなく、残りの 1 枚をAliceが取って勝利します。

入力例 2

3 3

出力例 2

No

問題文

N 頂点 N-1 辺からなる根付き木の形をしたグミ G があります。

頂点には 0 から N-1 の番号が、辺には 1 から N-1 の番号がついています。

根は頂点 0 です。辺 i は頂点 i と p_i を結ぶ無向辺であり、硬さは H_i です。

あなたは以下の操作を繰り返して、このグミ G をより多くの連結成分に分けようとしています。

• 根 0 以外の 1 つの頂点 X を選び、根 0 と X を両手で引っ張る。
• 根 0 と X を結ぶパス上にあるすべての辺の硬さが 1 減少する。
• 硬さが 0 になったすべての辺はちぎれて消滅する。
• これによって根と連結でなくなった頂点は 2 度と選ぶことができない。

操作を繰り返したあとの、G の連結成分の個数の最大値を求めてください。

制約

• 2 \le N \le 5000
• 0 \le p_i < i
• 1 \le H_i \le 10^9
• 入力はすべて整数である。

部分点

この問題には部分点が設定されている。

• N \le 300 を満たす入力に正解すると、500 点が得られる。

入力例 1

3
0 10
1 20

出力例 1

2

頂点 1 または 2 を合計 10 回選ぶと、1 番目の辺がちぎれ、これ以上操作ができなくなります。

このとき、G は \{0\},\{1,2\} という 2 個の連結成分に分かれています。

入力例 2

5
0 5
1 10
1 3
2 2

出力例 2

4

(10:40 更新) 頂点 4 を 2 回選び、頂点 3 を 3 回選ぶと、\{0\},\{1,2\},\{3\},\{4\} という 4 個の連結成分に分かれます。

入力例 3

10
0 12
1 6
1 3
1 6
3 7
4 2
4 8
5 5
5 1

出力例 3

6

問題文

N \times N のグリッドがあり、各マスにコインが 1 つずつ置いてあります。 グリッドの上から i 番目、左から j 番目のマスの位置を (i, j) と呼ぶことにします。例えば、左上のマスは (1, 1) 、右上のマスは (1, N) 、左下のマスは (N, 1) 、右下のマスは (N, N) です。

あなたは機械に強いトレジャーハンターであり、このグリッド上のコインをロボットを用いて回収しようとしています。

ロボットは全部で N 体あり、 1 から N までの番号がついています。 1 から N の順列 P と、長さ N の正整数列 A が与えられます。 ロボット i は初期位置 (i, P_i) に配置されていて、同時に最大 A_i 枚のコインを持つことができます。

大量のコインを一度に回収するのは難しいため、あなたはコインをロボットの初期位置に集めることにしました。あなたの目標は、どのコインも、ロボットの初期位置のいずれかに置かれている状態にすることです。

あなたはコストを 1 払うたびに以下の操作を行えます。

• ロボットを 1 つ選ぶ。選んだロボットを i とする。
• 上下左右いずれかの向きと、 A_i 以下の正整数 x を選び、これらをロボット i に伝える。
• ロボット i は、伝えられた方向に隣接するマスへ移動して、移動したマスにコインがあるなら取ることを繰り返す。
• ロボット i が x 枚のコインを回収すると、来た道を引き返して初期位置 (i, P_i) へ戻り、そこに持っているすべてのコインを置く。

これらのロボットは古く、誤作動を起こしやすいため、あなたはロボットに対して、他のロボットが一度でも入ったマスに入れようとする操作や、グリッドの外へ出そうとする操作をしてはいけません。

どのコインも初期位置のいずれかに置かれている状態にするのに必要なコストの最小値を求めてください。

制約

• 2 \le N \le 80
• 1 \le P_i \le N
• P は 1 から N の順列である。
• 1 \le A_i \le N-1
• 入力はすべて整数である。

入力例 1

3
1 2 3
1 1 2

出力例1

4

以下の 4 回の操作で達成できます。

• ロボット 1、 下、 x=1
• ロボット 3、 左、 x=2
• ロボット 2、 上、 x=1
• ロボット 3、 上、 x=2

入力例 2

3
2 3 1
2 1 2

出力例2

4

以下の 4 回の操作で達成できます。

• ロボット 1、 下、 x=2
• ロボット 3、 上、 x=2
• ロボット 2、 上、 x=1
• ロボット 2、 下、 x=1

入力例 3

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

出力例3

35

問題文

N 頂点 M 辺の単純無向連結グラフが与えられます。 i 番目の辺は頂点 u_i と v_i を結んでいて、重みは w_i です。 w_iは正整数の定数、もしくは変数 x です。 以下の Q 個のクエリをすべて処理してください。

• i 番目のクエリでは、正整数 a_i が与えられる。
• x=a_i としたときの最小全域木の重みを求めよ。

制約

• 2 \le N \le 5 \times 10^4
• N-1 \le M \le min(5 \times 10^4, N(N-1)/2)
• 1 \le u_i,v_i \le N
• u_i \neq v_i
• i \neq j のとき (u_i,v_i) \neq (u_j,v_j) かつ (u_i,v_i) \neq (v_j,u_j)
• 与えられるグラフは連結である。
• w_i が定数のとき、1 \le w_i \le 10^9
• 1 \le Q \le 5 \times 10^4
• 1 \le a_i \le 10^9
• 入力は、文字 x を除けば、すべて整数である。

入力例 1

3 3
1 2 0 1
2 3 0 5
3 1 1 x
3
4
5
6

出力例 1

5
6
6

このケースでは、

• x \le 5 のとき最小全域木の重みは x+1
• x \ge 5 のとき最小全域木の重みは 6

となります。

入力例 2

9 15
1 3 0 954291757
2 3 1 x
2 4 1 x
1 5 0 138996221
2 5 0 353195922
3 5 1 x
4 5 0 913575467
1 6 0 824284691
1 7 1 x
2 7 1 x
1 8 0 131381221
6 8 0 208032501
7 8 0 973708325
5 9 1 x
6 9 0 298309896
5
215208399
554374432
47628333
810900084
87027328

出力例 2

1554451938
2793039057
625183720
3562616013
861577690