SRM642 Div2

Easy(250)

数字をある桁で2分割した和の最小値を求める。

stoi書く必要なかったっぽい。

Middle(500)

N個ライトとスイッチがあり、i番目のスイッチは、iの倍数の番号のライトに対応している。全てのライトをOFFにする最低何回スイッチを押さないといけないか。

小さい方から順番に消していく。

Hard(1000)

N個の都市があり、都市には0~N-1の番号が付いている。また、都市間にN*(N-1)/2本以下の道路があり、それぞれの道路には高さ制限が設けられている。予算Bが与えられ、予算を用いてそれぞれの道路の高さ制限を一度だけ上げることができる(k上げるのにk^2掛かる)。0からN-1の都市に行くことができる最大の高さを求めたい。

2分探索だなぁとは思ったけど時間内には解法は思いつかず。その後、二分探索で高さ決めて、残りの予算をキーにした優先度付きキューで幅優先したらできた。 

次で緑にあげられるように頑張る!