A - 正方形のチップ

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

半径 R cmのウェーハにダイシングという操作を行い、正方形のチップをいくつか作成することにしました。 作成される正方形のチップの個数を求めてください。

ウェーハとは、ある部品を作るのに使われる薄い円盤状の物体です。 ダイシングという操作は、ウェーハの中心から C cm間隔で水平方向と垂直方向に切れ目を入れてウェーハを分割する操作です。

例として、R=15, \, C=4 の例を示します。 破線で示されるようなマス目状に分割がなされ、緑色の領域で示されるような 32 個の正方形のチップを作成することができます。

3b83484e97d59df50e3ee39c4a3cbca7.png

制約

  • 1 ≦ R, \, C ≦ 100
  • R, \, C はいずれも整数

入力

入力は以下の形式で標準入力から与えられる。

R C

出力

作成される正方形のチップの個数を 1 行に出力せよ。

入力例 1

15 4

出力例 1

32
  • 問題文中で示した通りです。

入力例 2

5 1

出力例 2

60
  • ウェーハの中心を (0,0) としたとき (2,3),(3,3),(2,4),(3,4) の 4 点で表される正方形のチップは (3,4) がウェーハの周上にありますが、このようなチップも作成することが可能です。
B - デュアルカット

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

半径 R のウェーハを水平方向に等間隔で切って N 分割することにしました。ウェーハとは、ある部品を作るのに使われる薄い円盤状の物体です。

ウェーハを等間隔で N 分割するためのカットラインと呼ばれる線が N-1 本あります。 カットラインには上から順に 1 ～ N-1 の番号が付いています。 また、下図に示されるように 0 以下や N 以上の番号のカットラインも便宜上存在することにします。

b7d93ccb848ebe7e3e1956b68b97625f.png

ウェーハを N 分割するためにデュアルカットという手法を用いることにしました。

デュアルカットでは、カットラインに対してカットという操作を何度か行います。 1 回のカットでは、2 枚の刃を使用して 2 本のカットラインを同時に切断します。 切断に用いる機械の制約上、2 本のカットラインは一定以上離れている必要があります。 より正確には、同時に切断する 2 本のカットラインの番号をそれぞれ i,j (i<j) とすると、i+M ≦ j を満たしていなければなりません。 この問題では、同じカットラインを 2 回以上切断したり、0 以下や N 以上の番号のカットラインを切断したりしても構いません。

i 番と j 番のカットラインを同時に切るときのカット長は、2 本のカットラインの長さのうちの長い方の長さで表されます。 ここで i \, (1 ≦ i ≦ N-1) 番のカットラインの長さとは i 番のカットラインで示される直線とウェーハの共通部分の線分の長さであり、それ以外の 0 番や N 番などのカットラインの長さは 0 です。

機械の動作の具体例を示します。N=6, \, M=3 のときに i=2, \, j=5 として機械を稼働させると、下図（左）のように 2 番と 5 番のカットラインがカットされます。このときのカット長は 2 番のカットラインの方が 5 番のカットラインより長いため、2 番のカットラインの長さとなります。カットラインの長さは図中で赤色の実線で示されています。 ここで、下図（右）のような i=3,\,j=5 といった操作は i+M ≦ j を満たさないため、行うことができないことに注意してください。

25802968adbadeb2e8567108e61a5bdd.png

1 ～ N-1 番のカットラインそれぞれ 1 回以上切断するとウェーハを N 分割することが出来ます。 うまく機械を操作することで、ウェーハを N 分割するときのカット長の総和を最小化したいです。 カット長の総和の最小値を求めてください。

制約

  • 1 ≦ R ≦ 10^{3}
  • 2 ≦ N ≦ 10^{3}
  • 1 ≦ M ≦ N - 1
  • R は整数

部分点

  • M=1 を満たすデータセットに正解した場合は、300 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 400 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

R N M

出力

答えを 1 行で出力せよ。絶対誤差、あるいは相対誤差が 10^{-6} 以下であれば許容される。

入力例 1

100 4 1

出力例 1

373.2050807569

以下のようにカットするのが最適な操作の手順の 1 つです。

  • 1 番と 2 番のカットラインを切断する
  • 0 番と 3 番のカットラインを切断する

このケースは部分点の制約を満たします。

入力例 2

100 4 3

出力例 2

546.4101615138

以下のようにカットするのが最適な操作の手順の 1 つです。

  • 0 番と 3 番のカットラインを切断する
  • 1 番と 4 番のカットラインを切断する
  • 2 番と 5 番のカットラインを切断する

M が入力例 1 と異なり 3 であるため、1 番と 2 番を同時に切断することや、1 番と 3 番を同時に切断することなどは、機械の制約上指定できないことに注意してください。

入力例 3

43 65 12

出力例 3

2208.8155789165

入力例 4

1000 1000 999

出力例 4

1570743.7385010704
C - 01文字列

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

文字列 s に対して以下の 3 種類の操作を何度か行い、文字列 T を作ることを考えます。 s ははじめ空文字列です。

  1. A 円払って s の先頭に0を挿入する。
  2. B 円払って s の末尾に1を挿入する。
  3. C 円払って s に含まれる0を全て1に、s に含まれる1を全て0に置換する。

文字列 T を作るために必要な資金の最小値を求めてください。

制約

  • 1 ≦ A, \, B, \, C ≦ 10^{9}
  • 1 ≦ |T| ≦ 2 \times 10^{5}
  • T は0と1のみからなる文字列
  • A, \, B, \, C はいずれも整数

部分点

  • 1≦|T|≦10 を満たすデータセットに正解した場合は、300 点が与えられる。
  • 追加制約のないデータセットに正解した場合は、上記とは別に 400 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

A B C
T

出力

答えを 1 行に出力せよ。

入力例 1

1 10 2
0011

出力例 1

6
  • はじめに操作 1 を 2 回行います。s は00となります。
  • 次に操作 3 を 1 回行います。 s は11となります。
  • 最後に操作 1 を 2 回行うことで s は0011となり、T と一致します。

このような手順で操作を行うと、1+1+2+1+1 = 6 円が必要であり、これが必要な資金の最小値です。

このケースは部分点の制約を満たします。

入力例 2

5 2 8
0000100111100101100101100000100

出力例 2

169

入力例 3

1000000000 1000000000 50
11011001001001

出力例 3

14000000200
D - シャツの部屋

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

太郎君はタンス、洗濯カゴ、ゴミ箱、服屋、コインランドリーがある部屋にいます。 はじめ、タンスと洗濯カゴとゴミ箱は空で、太郎君はシャツを 1 枚も持っていません。

太郎君は毎朝、部屋の中にある服屋でシャツを買うことができます。 服屋で売られているシャツは N 種類あり、それぞれ 10^{100} 枚あります。 種類 i のシャツは A_i 回洗濯すると破れてしまうシャツで、値段は B_i 円です。 買ったシャツは、即座にタンスに収納されます。

太郎君は毎日、以下のような生活を行います。

  • 朝：服屋でシャツを買うことができる。何種類でも何枚でも買ってよい。
  • 昼：タンスから 1 枚シャツを選んで着る。その後、着たシャツを洗濯カゴに入れる。
  • 夜：洗濯するかどうかを選択する。
    • 洗濯する場合：C 円払ってコインランドリーを利用して、洗濯カゴに入っているシャツを全て洗濯する。その後、洗濯によって破れてしまったシャツをゴミ箱に、それ以外のシャツをタンスにしまう。
    • 洗濯しない場合：何も起こらない。

今を 1 日目の朝として、M 日目の夜まで太郎君が毎日シャツを着るために必要な資金の最小値を求めてください。

制約

  • 1 ≦ N ≦ 500
  • 1 ≦ M ≦ 10^{9}
  • 1 ≦ A_i ≦ 500
  • 1 ≦ B_i ≦ 10^{9}
  • 1 ≦ C ≦ 10^{9}
  • B_i \, C はどちらも整数

入力

入力は以下の形式で標準入力から与えられる。

N M C
A_1 B_1
:
A_N B_N

出力

答えを 1 行に出力せよ。

入力例 1

2 3 1
1 2
2 3

出力例 1

6

以下のような行動をするのが最適な行動で、このときに必要な資金は 6 円です。

  • 1 日目
    • 朝：種類 1 の服を 1 枚買う。これを服 a と呼ぶことにする。
    • 昼：タンスにある服 a を着た後、洗濯カゴに入れる。
    • 夜：洗濯をしないことを選ぶ。
  • 2 日目
    • 朝：種類 2 の服を 1 枚買う。これを服 b と呼ぶことにする。
    • 昼：タンスにある服 b を着た後、洗濯カゴに入れる。
    • 夜：洗濯をする。服 a は破れてしまうためゴミ箱に、服 b はタンスにしまわれる。
  • 3 日目
    • 朝：何も買わない。
    • 昼：タンスにある服 b を着た後、洗濯カゴに入れる。
    • 夜：洗濯をしないことを選ぶ。

入力例 2

15 551 34
7 78
24 9
7 20
23 17
22 64
3 37
5 18
14 11
1 16
23 43
19 51
2 4
14 11
23 44
21 78

出力例 2

788

入力例 3

1 1000000000 1000000000
1 1000000000

出力例 3

1000000000000000000
E - 根付き木とクエリ

Time Limit: 5 sec / Memory Limit: 512 MB

配点 : 1500 点

問題文

N 頂点の根付き木が与えられます。 各頂点には 1, \, 2, \, ..., \, N と番号がついており、頂点 1 はこの根付き木の根です。 i(1 ≦ i ≦ N-1) 番目の辺は頂点 A_i と頂点 B_i をつなぐ、長さ C_i の無向辺です。

Q 個のクエリが与えられるので、順番に処理してください。 クエリには 2 種類あり、入力形式とクエリの内容は以下のとおりです。

  • 1 v k x： 頂点 v を根とする部分木において、k 代目の頂点と k+1 代目の頂点をつなぐ辺それぞれについて、辺の長さに x を加算せよ。ここで、頂点 v は 1 代目の頂点と定義され、n 代目の頂点の直接の子であるような頂点は n+1 代目の頂点と定義される。
  • 2 u v： 頂点 u から頂点 v への最短経路長を求めよ。

詳細はサンプル 1 で確認してください。

制約

  • 1 ≦ N, \, Q ≦ 10^{5}
  • 1 ≦ A_i, \, B_i ≦ N
  • 1 ≦ C_i ≦ 10^{5}
  • 1 ≦ u, \, v, \, k ≦ N
  • 1 ≦ x ≦ 10^5
  • 与えられるグラフは木にである
  • 種類 2 のクエリで与えられる頂点 u, \, v は相異なる
  • C_i, \, x はいずれも整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
Query_1
:
Query_{Q}

出力

2 u vというフォーマットのクエリに対する答えを、クエリが与えられた順にそれぞれ 1 行ずつ出力せよ。

入力例 1

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

出力例 1

20
27
6

はじめに下図のようなグラフが与えられます。

14719568c70b794384d9267713fc28f1.png

1 1 2 5というクエリを処理したあとの辺の長さは下図のように変化します。2 代目の頂点である頂点 2, \, 4 と 3 代目の頂点である頂点 3, \ 5, \ 6 をつなぐ辺の長さに 5 が加算されます。

344f145215af530aec7fe65e98c2ec9c.png

さらに、1 4 1 2というクエリを処理したあとの辺の長さは下図のように変化します。1 代目の頂点である頂点 4 と 2 代目の頂点である頂点 3, \, 6 をつなぐ辺の長さに 2 が加算されます。

293c37ff6545b9d841490366cc4f1153.png

入力例 2

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

出力例 2

1

加算の対象となる辺が存在するとは限りません。