ACM-ICPC JAG Summer Camp 2010, Day 3

Algorithm

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

A

やるだけだが壮絶にバグる。

B

rが小さくて座標が整数なので答えは必ず10000以下になることがわかる。あとは dp[i][j][k] := ニンジンをk個貰っていて、現在いる都市が j、その前にいた都市が i という状態へ行くための最短の経路の長さ でDP。

C

数学臭がやばいので逃亡

D

無理ゲー臭が漂うので逃亡

E

それぞれの敵について T[i] = 敵iを倒すのにかかるターン数、 A[i] = 敵iから1回の攻撃で受けるダメージ とする。あとは敵を A/T の昇順に並べておわり。

F

DP。ただし加速しないと死ぬ。

G

幾何なので逃亡

H

a = b = 1 のときはチケットの番号は関係なくて、とりあえずチケットを x 枚使うと (p+q)*x だけ進めるので x について二分探索する。

そうでないときは実際に使えるようなチケットは少ないので、p*a^k + q*b^k が m を超えないような k を列挙して貪欲に使う。

I

六角形見て逃亡

J

n = 1 に気をつけてやるだけ。