ウイルスの除去

サブタスク 1：感染している区画の集合をビットマスクで表す。相異なる三つの区画の選び方をすべて列挙し、そのビットを消した後、午前零時の同時感染を計算して遷移を作る。全区画が感染した状態から空集合まで BFS を行い、経路を復元する。ビット演算を使うと時間計算量は $O(2^N N^3)$、空間計算量は $O(2^N)$ となる。以下の構成から $N$ 日以内の経路が存在するため、BFS の最短経路も制限を満たす。

全体の解法：$X=N-2$ とし、$k$ 日目の正午に区画 $1,k+1,k+2$ を除去する（）。

$N=3$ なら初日にすべて除去できる。それ以外では、$1 \leq k \leq N-3$ について、$k$ 日目の午前零時の後に感染していない区画はちょうど $[2,k+$ となる。初日の正午に をきれいにすると、午前零時に両端が再感染し、区画 だけが残る。帰納的に、前日から残った区間 に を加えると、正午には がきれいになる。午前零時に外側の感染区画に接する両端だけが再感染するため、 が残る。

最後の $N-2$ 日目に残りの区画 $1,N-1,N$ を除去すると、感染源がなくなる。三つの番号は常に相異なり、範囲内にある。日数も $N-2 \leq N$ を満たす。

出力に要する時間計算量は $O(N)$、出力バッファを除く追加空間計算量は $O(1)$ である。チェッカーは各日を直接シミュレーションし、$O(NX)$ 時間、$O(N)$ 空間を使う。$$ より、一つの入力ファイルで行う区画の更新は高々 回である。

Solution written by GPT