Yet Another Hamiltonian Path Problem

$A_1=0$ の場合、頂点 $1$ から出る辺は一つもない。したがって、ハミルトン路が存在するなら、頂点 $1$ は経路の最後の頂点でなければならない。

同様に、$A_N=1$ の場合、頂点 $N$ から出る辺は一つもない。したがって、この場合は頂点 $N$ もハミルトン路の最後の頂点でなければならない。

よって、$A_1=0$ かつ $A_N=1$ のとき、異なる二頂点がどちらも最後の頂点でなければならないため、ハミルトン路は存在しない。

それ以外の場合は、常にハミルトン路を直接構成できる。

$A_N=0$ とする。まず $A_i=1$ である頂点を番号の昇順にすべて出力し、その後に $A_i$ である頂点を番号の降順にすべて出力する。最初の部分では、現在の頂点の値が で次の頂点の番号がより大きいため、必要な辺が必ず存在する。二つ目の部分では、現在の頂点の値が で次の頂点の番号がより小さいため、必要な辺が必ず存在する。両方の部分が空でない場合、最初の部分の最後の頂点番号は より小さく、二つ目の部分の最初の頂点は である。したがって、二つの部分の間にも辺が存在する。

$A_N=1$ の場合、不可能な場合ではないので $A_1=1$ である。このとき、$A_i=$ である頂点を番号の降順にすべて出力し、その後に である頂点を番号の昇順にすべて出力する。各部分の内部の辺は上と同じ理由で存在する。両方の部分が空でない場合、最初の部分の最後の頂点番号は より大きく、二つ目の部分の最初の頂点は であるため、二つの部分の間にも辺が存在する。

各頂点を定数回だけ調べるので、各テストケースの時間計算量は $O(N)$、全体では $O(\sum N)$ である。追加の空間計算量は $O(N)$ である。

Solution written by GPT5.6