読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

東京大学プログラミングコンテスト(UTPC)2014 D問題 ラボライブ タフグローバルフェスティバル

http://utpc2014.contest.atcoder.jp/tasks/utpc2014_d
タイトルがすごい、、、
状態数がとても増えそうだったので本番中飛ばした問題です。
complexのrealとimagをいちいち入力するのが面倒でどうしたものか考え中です。

- 問題概要

m本の指の初期位置とn個の点の座標及びs,tが与えられる。
sからtの間、いずれかの指でその座標を押さえ続けなければならない。
各指は1秒間にユークリッド距離で最大1移動できる。
最初の点の開始時間以降、どの時間も押さえなければならないという点が1つ存在するという制約が存在する。

- 解法

解説スライドそのままの解法です。
問題の制約上、一つ前に押した点と違う座標に存在する点は同じ指で押さえ続けることができない。
ある点の終了時間とその次の点の開始時間が一致するので前後の点が同じ座標であるならばあらかじめ合体させておく。

m=1のときは全ての点が同じ座標である必要がある。上記のようにマージしておけば必ず点は一つだけになる。
あとは開始時間までに移動が間に合うかどうか判定を行う。

m=2のときは前後の点を押さえる指が異なる必要があることから、各指を交互に動かす必要がある。
交互に指を動かす組み合わせは2パターン存在するためその二つを確かめてやれば良い。

m=3のときが面倒です。
座標を保持する方法として、最後に押さえた点が分かれば次にその指が押さえるべき点との時間差で到達可能か判定できます。
P_iと点P_{i-1}を押さえる指は必ず異なることを用いてDPを使います。
P_iと点P_{i-1}で使っていない点が最後にどこを押さえているかが気になります。
その点をjとすると、press(i,j)={T,F}とすることで、{i,i-1,j}という指の配置が可能かどうか判定が可能です。
press(i,j)=Tのとき、点P_{i-1}から点P_{i+1}への移動が時間内に可能ならばpress(i+1,j)=Tが成り立ち、
P_{j}から点P_{i+1}への移動が時間内に可能ならばpress(i+1,i-1)=Tが成り立ちます。
よってi,jの組み合わせを全て求めてやれば良いので[O(n^2)]で実現可能です。

- ソースコード

http://utpc2014.contest.atcoder.jp/submissions/378291
double型の距離計算でepsを使うときは正負に注意しましょう(戒め