以下を満たす \(N\times W\) 頂点の有向グラフ \(G\) を考えます。

• 頂点は整数組 \((x,w) \ (1\leq x\leq N,1\leq w\leq W)\) で表される
• 任意の \(1\leq x,y\leq N\) および \(1\leq w\leq W\) に対し、以下が共に成り立つとき有向辺 \((x,w)\to(y,w\bmod W+1)\) が存在する
  • \(x=y\)、または都市 \(x,y\) が直接道路で結ばれている
  • \(S_{x,w},S_{y,w\bmod W+1}\) は共に o である

曜日 \(w\) の昼に都市 \(x\) に居ることを頂点 \((x,w)\) に対応づければ、条件を満たすように移動を続けられることは \(G\) においてサイクルが存在することと同値です。

有向グラフにおけるサイクルの検出は DFS、またはトポロジカルソートの要領で行うことができ、\(O((N+M)W)\) 時間で計算できます。

実装例(C++) 実装例(PyPy)