問題文中の \(2\) つの条件をそれぞれ順に条件 \(1\) 、条件 \(2\) と呼びます。 \(G\) が DAG でないときは、条件 \(1\) を満たす \(P\) は明らかに存在しないので、以下では \(G\) は DAG とします。

\(P\) が \(2\) つの条件を満たすには 全ての辺 \((s, t)\) について、\(P_s \leq R_s\) と \(P_s \leq P_t-1 \leq R_t-1\) を満たすことが必要です。 よって、辺 \((s, t)\) について \(R_s \leftarrow \min\{R_s, R_t-1\}\) という置き換えの操作をしても、問題の答えは変わリません。 \(G\) の適当なトポロジカル順の後方から順に、上の置き換えの操作を繰り返し行うことで、元の問題との等価性を維持したまま、全ての辺 \((s, t)\) で \(R_s \lt R_t\) を満たすようにできます。 そこで、以下では全ての辺 \((s, t)\) で \(R_s \lt R_t\) が成り立つと仮定します。

各整数 \(1, 2, \ldots, N\) を いずれかの頂点 \(v\) に \(P_v\) として割り当てていくことで順列 \(P\) を作ることを考えます。 その過程で、整数 \(1, 2, \ldots, i-1\) までは既にいずれかの頂点に割り当て済みで、次に整数 \(i\) をいずれの頂点に割り当てる状況を考えます。 出来上がる \(P\) が条件 \(1, 2\) を満たすためには、整数 \(i\) を割り当てる頂点 \(v\) は、

• \(L_v \leq i\) （条件 \(2\) より）かつ
• \(v\) に入る全ての辺 \((u, v)\) について、\(u\) には既に整数が割り当てられている（条件 \(1\) より）

ことが必要です。 そのような頂点を割り当て可能な頂点と呼ぶことにします。 実は、条件 \(1, 2\) を満たす \(P\) を作るには、割り当て可能な頂点 \(v\) のうち \(R_v\) が 最小のものに整数 \(i\) を割り当てるのが最適です（証明は後述）。

つまり、本問題を解くには、

\(i = 1, 2, \ldots, N\) についてこの順に「現在割り当て可能な頂点 \(v\) のうち \(R_v\) が最小のものに整数 \(i\) を割り当てる」

という貪欲な手順を試し、 これによって条件 \(1, 2\) を満たす \(P\) が実際に得られるどうかを判定すれば良いです。 「割り当て可能な頂点 \(v\) のうち \(R_v\) が最小のもの」を得るのに優先度付きキューなど用いることで、本問題を \(O(N\log N)\) 時間で解くことができます。

最適性の証明

\(P\) を条件 \(1, 2\) を満たす順列とします。 頂点の番号を適切に振り直すことにより \(P = (1, 2, \ldots, N)\) と仮定できます（整数 \(i\) を割り当てられた頂点を頂点 \(i\) と振り直す）。

この \(P\) を作る過程において、整数 \(x\) を割り当てる局面で「割り当て可能な頂点 \(v\) のうち \(R_v\) が最小のもの」が頂点 \(y\) であったにもかかわらず、\(R_x \gt R_y\) を満たす頂点 \(x\) に整数 \(x\) が割り当てられたとします。 つまり、\(1 \leq x \lt y \leq N\) を満たす整数の組 \((x, y)\) で、

• 頂点 \(x, x+1, \ldots, N\) から頂点 \(y\) への辺が存在しない。
• \(L_y \leq x\)
• \(R_x \gt R_y\)

を満たすものが存在したとします。 このとき、整数 \(x\) を頂点 \(x\) の代わりに頂点 \(y\) に割り当てていた場合に得られる順列

\[P' = (P'_1, P'_2, \ldots, P'_{N-1}, P'_N) \coloneqq (1, 2, \ldots, x-1, x+1, x+2, \ldots, y, x, y+1, \ldots, N)\]

も条件 \(1, 2\) を満たすことを示します。

まず、\(P'\) が条件 \(1\) を満たすことは、\(P\) が条件 \(1\) を満たすことと「頂点 \(x, x+1, \ldots, N\) から頂点 \(y\) への辺が存在しない」から従います。

次に、すべての \(i\) で \(L_i \leq P'_i\) を満たすことは、 \(P\) から \(P'\) にかけて割り当てられた整数が小さくなった唯一の頂点 \(y\) について、\(L_y \leq x = P'_y\) が成り立つことから従います。

最後に、すべての \(i\) で \(P'_i \leq R_i\) が成り立つことを示します。 \(P\) から \(P'\) にかけて割り当てられた整数が大きくなった頂点 \(x, x+1, \ldots, y-1\) について示せば十分ですが、 これらの任意の頂点 \(z\) について \(R_y \leq R_z\) が成り立つことが以下の通りわかります。

• \(z\) が割り当て可能なら、\(y\) が「割り当て可能な頂点 \(v\) のうち \(R_v\) が最小のもの」であったことから、\(R_y \leq R_z\) を得ます。
• \(z\) が割り当て可能でないなら、割り当て可能なある頂点 \(w\) から、頂点 \(z\) へのパスが存在しますが、全ての辺 \((u, v)\) で \(R_u \lt R_v\) という仮定から、\(R_ y \leq R_w \lt R_z \) となります。

よって、\(P'_z = z+1 \leq y \leq R_y \leq R_z\) が成り立ちます。