Regionals 2009 :: North America - Southeast USA
練習会＠LiveArchive（個人）
よくある問題が多かった
ただハマると怖い
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=375
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=610
4600 - Block Game
問題
よくある脱出系スライドパズル。
6×6限定で、サイズ2か3のピースだけある。
special pieceを右から出すのにかかる最短手数を求めよ。
解法
BFS。
状態をvector
遷移のとき注意して時間をかけないようにする。
special pieceが最初から右端にあるとき注意。
4601 - Euclid
問題
点A~Fが与えられる。
ABC、DEFはそれぞれ同一直線上にない。
このとき以下を満たすようなH、Gを求めよ
- Hは半直線AC上にある
- ABGHが平行四辺形を構成する
- 平行四辺形ABGHの面積と三角形DEFの面積が等しい
解法
幾何やるだけ。
なのだが三角形の面積が負になることに気づかずWAを量産してしまった・・・・。ひどい。
4602 - Museum Guards
問題
n人の警備員が、以下のような制約のもと博物館を警備する。
- 各警備員は毎日同じ時間に警備する
- 各警備員は警備できる時間帯が決まっている
- 各警備員は１日に警備する時間の合計の最大値が決まっている
- 警備員は30分刻みでシフトに入ることが出来る（１日に（時間的に離れていても）複数のシフトに入ることも可能である）
- ある時間帯で警備する場合、その時間帯はその警備員が警備できる時間帯に含まれていなければならない
このとき、２４時間の内最も警備している人数が少ない時間での人数を最大にしたい。
最適なシフトの入り方をした場合、この人数は何人になるか。
制約
N<=50
解法
警備人数の最小をx人に出来るか調べたいとする。
source → 警備員ノード （容量：警備時間の最大値）
警備員ノード → 時間ノード（30分刻み48個） （容量：１）
時間ノード → sink （容量：x）
という有向辺を張ったグラフを作り、sourceからsinkへ最大流を流す。
この結果、x*48流れたら答えをx人に出来ると分かる。
xをループさせてもいいし、二分探索してもいい。
時間の入力は罠が多そうなので注意する。
4603 - Knitting
やるだけ
4604 - Minesweeper
やるだけ
4605 - The Ninja Way
問題
１直線上にn本の木を植える。
それぞれの木は、左からの順番と高さが決まっている。
それぞれの木は、次に高い木との距離がD以下でなければならない。
また、木は整数座標に植えなければならず、同じ場所に２本以上の木を植えることはできない。
このとき一番低い木と一番高い木の距離を最大にせよ。
このような植え方ができない場合-1を出力せよ。
制約
n<=1000
解法
1次不等式になるので、最短路に帰着される。
最大10^9くらいになるので、INFの大きさに注意。
4606 - Pool Table
問題
L×Wのビリヤード台がある。（横がL、縦がWに注意）
手球と的球の座標が与えられる。
手球を的球にちょうどN回バウンドさせて当てたい。
このとき、手球が動く距離の最小値を求めよ。
ただし、球の大きさは無視できるとし、球は壁と完全弾性衝突するとする。
またちょうど角に当たった場合、２回バウンドしたとする。
制約
L,W，N<=100
解法
反射して目標点に行くときの最短距離といえば、反射面を軸として反転させて考えるというのが定石だが、この問題もそれ。
何回も反射するのであれば、反転を何回も繰り返したものを想像すればよい。
L×Wを１つのセルとし、それを繰り返し上下左右に反転させたセルを並べた図を考える。
このとき的球も繰り返し射影する。
N回反射しているのは、元のセルからのマンハッタン距離がちょうどNのセルにおいてである。
そのようなセルはO(N)個あり、それぞれについて手球とそのセル内に射影された的球との距離を求め、最小値を答えとする。
ただし、手球と射影された的球を結ぶ直線上に、他のセル内に射影された的球があった場合、答えの候補から外す。
この処理はlong longを使ってロバストに行う。
結局O(N^3)になる。
4607 - Robot Challenge
問題
二次元座標があり、(0,0)から(100,100)までロボットを移動させる。
ただし、N個のターゲットがあり、それぞれのターゲットについて、座標と、そのターゲットをスキップした時に発生するペナルティが与えられる。
ターゲットは、その座標上で1s停止した場合訪れたとみなされる。
ターゲットを訪れなかった場合、対応するペナルティを受けることになる。
また、ターゲットは与えられた順番通りに訪れなければならない。
(0,0)から(100,100)まで移動するまでにかかった時間とペナルティの和をコストとする。
このときコストの最小値を求めよ。
ただし、ロボットは1移動するのに1sかかる。
制約
N<=1000
解法
dp[i] = i番目のターゲットを訪れ、その場にいるときのコストの最小値
でDPする。
0番目のターゲットを(0,0), n+1番目のターゲットを(100,100) とすると楽かもしれない。
4608 - Mosaic
問題
図のようなピースでN×Mの盤面を埋め尽くすとき、その埋め尽くし方は何通りあるか？（mod 10^6）
制約
N<=10
M<=500
解法
典型問題のドミノ敷き詰めと同様にbitDP。
ただし、この問題ではもう１セル分埋められてるかどうかのビットを考えなければならない。
