2/3 PKU
1991 Turning in Homework
C個の宿題を提出しないといけない。それぞれの宿題について、提出する位置と、提出できる時間が決まっている。最初は位置0にいて、最後は位置Bにいたい。時間を最小化せよ。
まだ訪れていない左端と右端をキーにDP
2983 Is the Information Reliable?
N個の基地の位置関係の情報が与えられる。情報は、2つの基地の位置の差を表すものか、2つの基地のうちどちらが北にあるか表すものかのどちらかである。矛盾ないデータかどうか判定せよ。
情報をすべて総合すると、「a >= b + K」の形の式の組み合わせで表すことができる。これを重み付きグラフに翻訳し、負閉路がないかをBellman-Fordで確認する。
3225 Help with Intervals
数の集合があり、最初は空集合である。集合に対する操作が与えられるので、逐次処理し、最終的な結果を出力せよ。
閉区間や開区間が入り交じってわかりにくいので、n/2の形で表される数について集合に含まれるか含まれないかを管理する。含まれるなら1、含まれないなら0を割り当てる。
そのためにSegment Treeを使う。各ノードには、「以下全部0」「以下全部1」「下のノードを見よ」「下のノードを見て反転させよ」の4通りの値を割り当てておき、set（ある範囲を0/1にする）、flip（ある範囲の0/1を入れ替える）を実装すると、要求される5通りの処理はset/flipの合成で表現できる。
1033 Defragment
ディスク上にデータが散らばっている。それぞれのデータを適切な位置に戻したい。戻すために、データを空き領域に移動させるという行為のみができる。最短手順を示せ。
移動元->移動先のグラフを作り、閉路ができている部分は空き領域を借りて移動し、閉路がない部分は先端から順に移動を行う。
