1/6 PKU

1984 Navigation Nightmare

農場がいくつかあって、それらを結ぶ道の情報が与えられるから、各クエリに対して、2つの農場の間のマンハッタン距離を答えよ。道の情報を全部処理すると木構造になるし、道同士は交差しない。

全部の農場で木構造をなすので、全部処理してある農場からの相対位置をすべて決めてからunion findで「まだつながってないから-1」というのを管理するか、union findで相対位置情報を同時に持っておくかのどっちか。

1985 Cow Marathon

「Navigation Nightmare」と同じような感じだが、今度は「道のみをたどったとき、最長の経路の長さ」を求める問題。

道同士は交差しないし、木構造をなしてるので、木DPでやるだけ。

2261 France '98

16カ国でなんかのトーナメントをやる。2つのチームが対戦したときの勝つ確率が与えられるから、各チームが優勝する確率を求めよ。

DP？やるだけ
送ったらWaiting祭りで、その後Runtime Error祭りになって、あとで送りなおしたらACで、そのあとみたら「リジャッジメントですの！」ってなってた

3617 Best Cow Line

牛(というか'A'から'Z'までのアルファベット)の列があって、一番前か一番後ろかから牛を選んで新しい列の先頭に持ってくることができる。列のうち辞書順最小のものを求めよ。

greedyで解ける。残ってる列の先頭と末尾が異なるときは小さいほうを選ぶ。同じときは、中に潜ってみていくけど、同じだけ潜って文字が違ったらとりあえず小さいほうの端を取る。文字が同じだったら、先頭＝末尾の文字以下だったらそのまま続けて、大きかったらどっちか取る。

2948 Martian Mining

火星のある地域では2種類の鉱石が取れる。鉱石輸送用に、西行きのベルトコンベアと北行きのベルトコンベアを各マスに建設することにした。輸送のときには、鉱石が動くルートはまっすぐでないといけない。また、1マスに2つのコンベアを設置することはできない。北と西に鉱石処理場があって、処理できる鉱石は異なる。処理場に輸送される鉱石の量を最大化せよ。

コンベアの配置を想像して、DPやるだけ

1265 Area

頂点が格子点上にある多角形の、面積と、周上の格子点の数と、内部の格子点の数を求めよ。

ピックの定理やるだけ

1252 Euro Efficiency

コインの種類が与えられて、1から100セントの金額をコインで払うとき、払うコインまたはお釣りとして返されるコインの数の平均と、最大値を求めよ。（できるだけこの和が小さくなるようにコインを払う）

DPやるだけ。払う金額がけっこう大きくなるかもしれないことに注意