Regionals 2009 :: Europe - Northwestern
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=362
B - 4610 - Common Subexpression Elimination
問題
二分木を縮約する。
文字列表現した際に、前に出てきた部分木は出てきた順に付けられた番号によって置き換える。
制約
ノード数 <= 50000
C - 4611 - Divisible Subsequences
部分和のmodを取ったときの値がそれぞれ何回現れたかのテーブルを用意し、ループを回せば出来る。
D - 4612 - Fractal
問題
折れ線が与えられる。
折れ線の各線分に同じ折れ線を縮小・回転して埋め込むという操作を、再帰的にd-1回行なってフラクタルを作る。
このフラクタルにおいて、始点から割合f進んだ場所の座標を求めよ。
制約
頂点数<=100
d <= 10
解法
フラクタルを構成しても、初めの折れ線の各線分に対応する部分の長さの全体からの割合は変わらない。
そこでまず、初めの折れ線の、どの部分に目標とする点が存在するかを見つける。
どの部分か分かったら、折れ線を縮小・回転し、新たな折れ線とする。
また、割合fもその部分の中での割合になるように適切に変更する。
このような操作を全部でd回行う。
d回行った後は、現在の折れ線の始点と終点をf:(1-f)に内分する点を答えとすれば良い。
E - 4613 - Mountain Road
問題
1本道を両方の向き（両端をA、Bとする）に計n台の車が通る。
道は狭いので、一方の向きから車が通ってる時は、もう一方の向きから車は通れない。
また安全のため、同じ向きの場合、ある点を車が通過したあと10秒未満で他の車が通過することは許されない。
車がA、Bどちらから通るか、何秒にスタートできる状態になるか、道を通過するのに何秒かかるか、が与えられる。
このとき、車が全て通過し終わるのにかかる時間の最小を求めよ。
ただし、A,Bそれぞれに対し、先にスタートできる状態になった車が先にスタートする（待っている車の順番を入れ替えることは出来ない）。
制約
n <= 200
解法
dp[i][j][k] = Aの車がi台、Bの車がj台通過し終わっており、前に通過し終わったのが{A(k=0)/B(k=1)}のときの最短時間
初期値は、dp[0][0][0]=dp[0][0][1]=0,それ以外INF。
更新のときは、AまたはBから車を一気に通すことを考える。
このとき10秒制約に注意して、次の車がスタート出来る最短時間とゴール出来る最短時間を保持して利用する。
計算量はO(n^3)となる。
F - 4614 - Moving to Nuremberg
問題
重み付きの木が与えられる。
このとき、以下の和の最小値と、最小値を達成するuを全て求めよ。
・・・ ☆
制約
頂点数 <= 50000
解法
まず、ある頂点における☆をO(n)で求め、その頂点から１つ動いた時の☆をO(1)で求めることを繰り返すことにより、全体としてO(n)で全てのuについて☆を求める。
適当に根を決めて、DFSすることにより、頂点i以下のfの和sum[i]を求めておく。
また、根における☆もDFSで求まる。
１つ動いたとき、☆がどう変わるかはsum[i]を上手く使うことによって求めることが出来る。
intでは微妙にオーバーフローするので注意。
G - 4615 - Room Assignments
問題
n人とn部屋がある。
n人は1部屋に割り当てられ、1部屋に複数人が割り当てられることは許されない。
n人は、部屋を2つ希望することができる。
n人がコインを投げ、裏表によって希望した２つの部屋のうち、どちらかが採用される。
このとき、割り当てに失敗したら、成功するまで繰り返す。
何回やっても失敗するときは誰も部屋に割り当てられずに終わる。
今、n-1人の希望は揃っている。
最後の１人はどの部屋を希望すれば、得られる満足度の期待値を最大に出来るか。
ある部屋に割り当てられた時の満足度は与えられる。
どうやっても失敗に終わるときはImpossible。
部屋の選び方が複数あるときは辞書順最小。
制約
n <= 50000
解法
人と部屋の関係は特殊な二部グラフとなる。
ここではまだn-1人分を考える。
連結成分に分けた時、人に対応する頂点数をn1、部屋に対応する頂点数をn2とする。
このとき、以下が成り立つ。
- n1>n2のとき、割り当ては存在しない。
- n1=n2のとき、条件を満たす割り当てが存在する。
- n1
n1=n2のときの条件を満たす割り当ての存在性は、部屋から１本しか辺が出てないときその辺が接続する頂点を消去すると、単純な閉路しか残らないことから言える気がする。
n1
- n1>n2な成分があればimpossible
- 成分が１つの時は満足度が大きい２つ
- それ以外では、n1=n2-1となる成分における満足度が大きい部屋と、同じ成分で満足度が同じ値もしくは他の成分の部屋
で解けるが、辞書順最小もあり結構だるい。
H - 4616 - Settlers of Catan
六角座標における螺旋の動きを実装するだけ。
I - 4617 - Simple Polygon
問題
自己交差のないように与えられた点を頂点とする多角形を構成せよ。
制約
点数<=2000
解法
凸包を下半分作り、あとはx座標の順に点を選んでいく。
凸包を使わない方法ってなんだろ。
J - 4618 - Wormholes
ベルマンフォードを何回かやるっぽいけど何で動くのか良く分からん。
