A - 高橋君とお肉

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は友達とキャンプに行くことになった。

高橋君と友達は性能が同じである 2 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。2 つの肉焼き器にまたがって 1 つのお肉を置くことはできない。また、お肉は全部で N 個あり、お肉には 1 から N まで番号が付けられている。お肉 i を焼くのには、どちらの肉焼き器でも時間 t_i だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。

高橋君はお肉を焼く係であり、N 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。

すべてのお肉を焼くのにかかる時間の最小値を求めよ。

入力

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

N
t_1
t_2
:
t_N
  • 1 行目には、お肉の個数を表す整数 N (1 ≦ N ≦ 4) が与えられる。これは、お肉が N 個あることを表す。
  • 2 行目から N 行にはお肉の情報が与えられる。N 行のうち i 行目には整数 t_i が書かれており、これはお肉 i を焼くのにかかる時間が t_i (1 ≦ t_i ≦ 50) であることを表す。

出力

すべてのお肉を焼くのにかかる時間の最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

4
4
6
7
10

出力例1

14

一方の肉焼き器でお肉 1 とお肉 4 を、他方の肉焼き器でお肉 2 とお肉 3 を順に焼きます (下の図は参考図)。

入力例2

3
1
2
4

出力例2

4

一方の肉焼き器でお肉 3 を焼いている間に、他方の肉焼き器で残りすべてのお肉を焼きます。

入力例3

1
29

出力例3

29
B - 高橋君と禁断の書

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、部屋の整理をしていた。

高橋君が部屋の整理を行っているとき、中学生くらいのときに書いた「禁断の書」(という題名のノート)が出てきた！

数ページ見ただけでも(書いた本人が)悶絶するほどに人には見せられない「禁断」のノートであるため、箱にしまっちゃうことにした。

ノートは底面が縦 A センチ、横 B センチの長方形で高さ (厚み) がそれほどない直方体の形状をしている。

箱は N 個あり、それらには 1 から N までの番号がつけられている。箱 i (1 ≦ i ≦ N) の形状は、箱の内側の底面が縦 C_i センチ、横 D_i センチの長方形で、高さがノートの厚みよりわずかに大きいくらいの直方体の形をしている。

高橋君は几帳面なため、ノートの底面と箱の内側の底面を一致させて収納しなければ気が済まない。すなわち高橋君にとって、箱 i にノートが入る必要十分条件は、平面上で縦 A センチ、横 B センチの長方形 (ノートを表す長方形) を適切に回転および平行移動させて、同一平面上にある縦 C_i センチ、横 D_i センチの長方形の内部に完全に収まるように配置できるということである。

どの箱に収納するか吟味する前に、どの箱に収納可能かを調べなければならない。それぞれの箱について、ノートが入るか入らないかを判定するプログラムを作成せよ。

入力

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

A B
N
C_1 D_1
C_2 D_2
:
C_N D_N
  • 1 行目には、ノートの形状に関する情報を表す 2 つの整数 A (1 ≦ A ≦ 300,000) と B (1 ≦ B ≦ 300,000) が空白区切りで与えられる。これはノートを表す長方形の縦の長さが A センチで横の長さが B センチであることを表す。
  • 2 行目には、箱の個数を表す整数 N (1 ≦ N ≦ 5,000) が与えられる。
  • 3 行目から N 行では、箱の形状に関する情報が与えられる。N 行のうち i 行目では、2 つの整数 C_i (1 ≦ C_i ≦ 300,000) と D_i (1 ≦ D_i ≦ 300,000) が空白区切りで与えられる。これは、箱 i の内側の底面が縦 C_i センチ、横 D_i センチの長方形であることを表す。
  • 採点で用いられるすべての入力において、すべての箱 i (1 ≦ i ≦ N) に関して C_i および D_i の値を 0.01 だけ増減させても、ノートが箱 i に入るか入らないかは変化しない。

出力

N 行にわたって出力せよ。

i (1 ≦ i ≦ N) 行目には、箱 i にノートが入るなら文字列 YES を、入らないなら文字列 NO を出力せよ。出力の末尾にも改行を入れること。

入力例1

1 6
3
8 3
4 4
5 5

出力例1

YES
NO
YES
  • 箱 1 には、例えば下図のように配置することでノートを入れることができる (図中の斜線部分がノート)。
  • 箱 2 には、どのように配置してもノートを入れることができない。
  • 箱 3 には、例えば下図のように配置することでノートを入れることができる (図中の斜線部分がノート)。
C - 高橋君と国家

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はゲーム内で国家を運営している。

国家には N 個の都市と、M 本の道がある。それぞれの道は 2 つの異なる都市を直接結んでおり、道の途中に他の都市がない。また、どの 2 つの都市についても、それらの都市を直接結ぶ道は高々 1 つである。

最初、どの道も舗装されておらず、どの都市にも交易所が設置されていない。

高橋君は国家の発展のため、道路の舗装および交易所の設置を行うことにした。

どの都市についても以下のいずかの条件が満たされていれば、国家は「良い状態」であると呼ぶことにする。

  • その都市には交易所が設置されている。
  • その都市には交易所が設置されていないものの、その都市から舗装された道のみを経由して、交易所が設置されている別の都市に移動できる。

都市には 1 から N まで、道には 1 から M までの番号がつけられている。都市 i に交易所を設置するのには金貨が c_i 枚必要である。また、道 i を舗装するのには金貨が r_i 枚必要である。

あまり金貨を多く持ち合わせていないので、国家を「良い状態」にするのに必要な金貨の枚数をできるだけ少なくしたい。

必要な金貨の枚数として考えられる最小値を求めるプログラムを作成せよ。

入力

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

N M
c_1
c_2
:
c_N
a_1 b_1 r_1
a_2 b_2 r_2
:
a_M b_M r_M
  • 1 行目には、2 つの整数 N (2 ≦ N ≦ 100,000) と M (1 ≦ M ≦ 200,000) が空白区切りで書かれている。これは、都市が N 個、道が M 本あることを表す。
  • 2 行目から N 行には、都市に関する情報を表す整数 c_i (1 ≦ c_i ≦ 1,000,000,000) が与えられる。これは、都市 i に交易所を設置するのには金貨が c_i 枚必要であることを表す。
  • N+2 行目から M 行には、道に関する情報を表す 3 つの整数 a_i, b_i (1 ≦ a_i ＜ b_i ≦ N), r_i (1 ≦ r_i ≦ 1,000,000,000) が空白区切りで与えられる。これは、道 i は都市 a_i と都市 b_i を端点に持ち、舗装するのにはコスト r_i かかることを表す。

部分点

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

  • N ≦ 8 かつ M ≦ 10 を満たすデータセット 1 に正解した場合は、10 点が与えられる。
  • N ≦ 12 かつ M ≦ 66 を満たすデータセット 2 に正解した場合は、上記とは別に 20 点が与えられる。
  • N ≦ 3,000 かつ M ≦ 6,000 を満たすデータセット 3 に正解した場合は、上記とは別に 30 点が与えられる。
  • 追加制約のないデータセット 4 に正解した場合は、上記とは別に 40 点が与えられる。

出力

国家を「良い状態」にするのにかかるコストの合計値として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

出力例1

350

都市と道の配置は下図のようになっています。

以下の条件で交易所の設置および道の舗装をします。

  • 都市 1 に交易所を設置する。交易所の設置には金貨が 40 枚必要である。
  • 都市 3 に交易所を設置する。交易所の設置には金貨が 30 枚必要である。
  • 都市 5 に交易所を設置する。交易所の設置には金貨が 70 枚必要である。
  • 道 1 (都市 1 と都市 2 を結ぶ) を舗装する。舗装には金貨が 40 枚必要である。
  • 道 3 (都市 1 と都市 4 を結ぶ) を舗装する。舗装には金貨が 60 枚必要である。
  • 道 7 (都市 5 と都市 6 を結ぶ) を舗装する。舗装には金貨が 60 枚必要である。
  • 道 8 (都市 6 と都市 7 を結ぶ) を舗装する。舗装には金貨が 50 枚必要である。

最終的な都市と道の状態は下図のようになります。ここでは、交易所が設置されている都市の枠を二重に、舗装された道を二重線にして表示してあります。

この場合、国家は「良い状態」といえます。実際、

  • 都市 1 には交易所が設置されている。
  • 都市 2 には交易所が設置されていないが、舗装されている道 1 を経由して、交易所が設置されている都市 1 に移動することができる。
  • 都市 3 には交易所が設置されている。
  • 都市 4 には交易所が設置されていないが、舗装されている道 3 を経由して、交易所が設置されている都市 1 に移動することができる。
  • 都市 5 には交易所が設置されている。
  • 都市 6 には交易所が設置されていないが、舗装されている道 7 を経由して、交易所が設置されている都市 5 に移動することができる。
  • 都市 7 には交易所が設置されていないが、舗装されている道 7 と舗装されている道 8 を経由して、交易所が設置されている都市 5 に移動することができる。

となっています。金貨は 40 + 30 + 70 + 40 + 60 + 60 + 50 = 350 枚必要となります。

入力例2

3 3
50
50
50
1 2 60
1 3 60
2 3 60

出力例2

150

すべての都市に交易所を設置する方が安上がりです。

入力例3

5 7
80
70
60
50
40
1 3 20
1 4 70
1 5 30
2 3 30
2 4 90
3 4 40
4 5 80

出力例3

160
D - 高橋君と木のおもちゃ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は妹から誕生日プレゼントに木のおもちゃを貰った。

木のおもちゃは N 個の球と N-1 本の節からなる。各球には 1 から N まで番号がつけられており、各節には 1 から N-1 まで番号が付けられている。

N-1 本の節は、異なる 2 つの球を接続しており、これらはすべて番号の大きい方の球から番号の小さい方の球へと向きが付けられている。また、球 1 以外のどの球からも、その球から番号の小さい別の球へと向きがつけられている節がある。

どの球もちょうど 1 つの整数を格納することができる。最初、球 i (1 ≦ i≦ N) には整数 s_i が格納されている。

高橋君は妹と一緒に、手元にある M 個の整数を使って木のおもちゃでゲームをすることにした。

ゲームの目的は、木のおもちゃのそれぞれの球に格納されている整数の合計ができるだけ大きくなるようにすることにした。

高橋君は M 回、以下のステップを行う。

  1. 手元にある整数を 1 つ取り出す。i (1 ≦ i ≦ M) 回目のステップで取り出す整数は t_i である。
  2. 以下のいずれかの操作を行う。
  • 木のおもちゃに対して何もせず、整数 t_i を捨てる。
  • 木のおもちゃを構成する球から 1 つ選び、整数 t_i を置く。

球 j (1 ≦ j ≦ N) は、整数が置かれたとき、以下の動作を行う。

  • j = 1 のとき、球 1 は元から格納してある整数を捨て、球 1 に置かれた整数を格納する。
  • j ≧ 2 のとき、球 j は元から格納してある整数を、球 j から出ている節の行き先となる球におき、球 j に置かれた整数を格納する。

木のおもちゃの変化が止まるまで、高橋君と妹は次のステップに移動することができない。

最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を求めよ。

入力

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

N
s_1
s_2
:
s_N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
M
t_1
t_2
:
t_M
  • 1 行目には、妹から貰った木のおもちゃを構成する球の個数を表す整数 N (2 ≦ N ≦ 5,000) が与えられる。
  • 2 行目から N 行には、球に最初から格納されている整数に関する情報が与えられる。これら N 行のうち上から i (1 ≦ i ≦ N) 行目には整数 s_i (1 ≦ s_i ≦ 1,000,000,000) が与えられる。これは、球 i には最初に整数 s_i が格納されていることを表す。
  • N+2 行目から N-1 行には、節に関する情報が与えられる。これら N-1 行のうち上から i (1 ≦ i ≦ N-1) 行目には整数 a_i, b_i (1 ≦ a_i ＜ b_i ≦ N) が空白区切りで与えられる。これは、球 b_i から出て、球 a_i に入る節があることを表す。
  • 2N+1 行目には、手元にある整数の個数を表す整数 M (1 ≦ M ≦ 5,000) が与えられる。
  • 2N+2 行目から M 行には、手元にある整数に関する情報が与えられる。これら M 行のうち上から i (1 ≦ i ≦ M) 行目には整数 t_i (1 ≦ t_i ≦ 1,000,000,000) が与えられる。これは、i 回目のステップで整数 t_i を取り出すことを表す。

部分点

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

  • N ≦ 7 かつ M ≦ 8 を満たすデータセット 1 に正解した場合は、10 点が与えられる。
  • N ≦ 16 を満たすデータセット 2 に正解した場合は、上記とは別に 20 点が与えられる。
  • 追加制約のないデータセット 3 に正解した場合は、上記とは別に 70 点が与えられる。

出力

最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

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

出力例1

40

以下の手順で操作を行います。

  1. 整数 2 を取り出す。木のおもちゃには何もしない。
  2. 整数 8 を取り出す。木のおもちゃの球 4 に置く。
  3. 整数 1 を取り出す。木のおもちゃには何もしない。
  4. 整数 3 を取り出す。木のおもちゃには何もしない。
  5. 整数 6 を取り出す。木のおもちゃの球 6 に置く。
  6. 整数 3 を取り出す。木のおもちゃには何もしない。
  7. 整数 7 を取り出す。木のおもちゃの球 2 に置く。
  8. 整数 5 を取り出す。木のおもちゃの球 1 に置く。
  • 最初、木のおもちゃは下図のようになっています。以降数枚の図では、節を矢印で、球の番号を枠の添字で、球に格納されている整数は枠の内部に書かれた整数で表現されています。
  • ステップ 2 (整数 8 を球 4 に置く動作) の直後、木のおもちゃは下図のようになっています。
  • ステップ 5 (整数 6 を球 6 に置く動作) の直後、木のおもちゃは下図のようになっています。
  • ステップ 7 (整数 7 を球 2 に置く動作) の直後、木のおもちゃは下図のようになっています。
  • ステップ 8 (整数 5 を球 1 に置く動作) の直後、木のおもちゃは下図のようになっています。

最終的には、各球に格納されている整数の合計値は 5 + 7 + 5 + 8 + 5 + 6 + 4 = 40 となり、これが考えられる最大値です。

入力例2

6
21
5
5
5
5
5
1 2
1 3
1 4
1 5
1 6
5
8
8
8
8
8

出力例2

46