ARC090 People on a Line

所見

グラフに見えるかどうかゲー
問題がグラフに見える程度の能力は類題を解いた直後2週間程度は急上昇する(だがこれは罠でFalse Positiveも増える)ことが知られているので精進って感じだ

問題概要

x軸上にN人の人が居る。これらの人間の位置に関する情報がL,R,Dの形式でM個与えられる。すべての情報と矛盾しない人間の置き方があるかどうかを判定せよ。

取った方針

人の座標が負になったとしても最後にその分移動すれば同じである、かつ人間が10⁵人、間隔が最大10⁴なので、座標の数値が0以上10⁹以下であることは考慮しなくてよいことがわかる。
順番に情報を見ていって、初出の人ならば0に置き、既出の点なら条件を満たすように配置し、矛盾が発生したらそこで決定、という実装を行ってWA
これは、例えば以下のようなケースで落ちる。
6 3
2 3 1
5 6 1
3 6 2
この場合、位置0に2,5、位置1に3,6が置かれ、3 6 2の条件を満たせず矛盾となるが、実際には2 3 5 6(それぞれの間は1)のように並べることで条件を満たすことができる。
以上より、情報を辺、人間を頂点と見たグラフにおいて到達可能な頂点の組は同時に考えないといけないことがわかる。

正しい方針(解説の方針)

情報を辺、人間を頂点と見た重み付き有向グラフを考える。1 2 114514 なる情報に対して、1->2 コスト114514 なる辺と2->1 コスト-114514なる辺を張る。
グラフについてdfsをして、辺の重みに基づいて頂点に数字を振る。具体的には、数字iが振ってある頂点uからコストcの辺を通ってvに移動した場合、vの数字はi+cとなる。
このようにdfsをしたとき、すべての辺について矛盾なく数字を振ることができればOK、できなければNGとなる。

得られた知見

・二つのものの関係(+コスト)*大量 が与えられる->グラフにできないか考える
・dfs

解くのに必要な要素

・問題がグラフに見える能力
・dfs

周辺調査によって得られた知見

なし