ICPC Tokyo/Asia Regional Preliminary Contest

オンライン参加できるらしいので参加。10問中8問解けた。4位らしい。

A

やるだけ

B

i個目までやっていて、直前に右足を使った場合の最小を lr、左足の場合を rl とでもする。i+1個までの lr_next, nr_next を求められるとうれしい。i個目の場所をS[i]とすると

左足S[i+1]、右足S[i]が valid な配置なら rl_next = min(lr, rl+1) 、そうでないなら rl_next = infinity

左足S[i]、右足S[i+1]が valid な配置なら lr_next = min(rl, lr+1) 、そうでないなら lr_next = infinity

で計算するだけ。

C

dp[i][j] := i歩目でポーションの使用状況がjのときに実現可能な最大HP

でDPする。普通に部分集合を列挙してると 1000*3^P で間に合わないので j を大きいほうから回してやって 1個ずつ使うようにする。

D

やるだけ

E

頂点、爆弾と頂点を通る線と多角形の交点、爆弾と頂点を通る線へおろした垂線の足でダイクストラするとできそうだけど幾何は無理

F

左車輪と右車輪を LSpeed : RSpeed に外分する点を中心として回転させることになるのでやるだけ。

G

幾何無理

H

距離でダイクストラしながらできるだけコストの低い辺を採用する。

I

少人数から全部試す。ちょっと前にTopCoderで出た、パッと見二分探索っぽいけど、実際は二分探索はうまくいかなくてたくさんの人がハマった問題と同じ匂いがした。

計算量は結構きつくなるけど、まあそんなにたくさんオペレータは必要じゃない気がするので普通に通る。二分探索は落ちるんだろうか。

J

注文を頂点とするDAGの最小経路被覆を求めればよい。

最小経路被覆の求め方がアルゴリズム・イントロダクションに載ってた気がしたので読んでみたら演習問題として載っていたので解くハメになった。頑張って考えた結果頂点2倍した2部グラフを作って最大マッチング求めるとよいらしい。