各人は以下のどちらかの行動をするのが最適です。

• タイプ \(1\) : 左隣の人に出会うまで左に速さ \(1\) で移動し、その後右に速さ \(1\) で移動する
• タイプ \(2\) : 右隣の人に出会うまで右に速さ \(1\) で移動し、その後左に速さ \(1\) で移動する

互いに最初に出会う \(2\) 人 (つまり、人 \(i, i + 1\) がそれぞれタイプ \(2, 1\) に従って行動するときの人 \(i\) と人 \(i + 1\)) をペアにすることを考えます。
すると、ペアに属さない人が \(2\) 人連続する箇所があるような行動の仕方は考えなくて良いことが証明できます。
ここまで行動を絞れば、この問題は \(1\) 次元 DP (動的計画法) で \(O(N)\) で解くことができます。

以下は上記の事実の証明です。

以下の図で横軸は数直線の軸、縦軸は時間です。
緑、赤、紫、黄の点または線はそれぞれ人 \(i - 1, i, i + 1, i + 2\) の行動の一部を表します。
人 \(i\) と人 \(i + 1\) は両方ペアに属さないものとします。
また、人 \(i - 1\) がタイプ \(1\) なら、緑の線は人 \(i - 1\) が人 \(i - 2\) に出会って折り返した後の軌跡を表します。黄色の線についても左右対称に同様です。

このとき、人 \(i\) と人 \(i + 1\) が両方ペアに属さないとしていたので、以下のように局所的に青の点の時刻までパーティーが開かれている必要があることが分かります。

• 人 \(i, i + 1\) がそれぞれタイプ \(1, 1\) だった場合 : 人 \(i + 1\) と人 \(i + 2\) が出会うのが青の点になる
• 人 \(i, i + 1\) がそれぞれタイプ \(1, 2\) だった場合 : 人 \(i\) と人 \(i + 1\) が出会うのが青の点になる
• 人 \(i, i + 1\) がそれぞれタイプ \(2, 2\) だった場合 : 人 \(i - 1\) と人 \(i\) が出会うのが青の点になる

一方でここで人 \(i\) と人 \(i + 1\) をペアにすると (つまりそれぞれタイプ \(2, 1\) にすると) 局所的に必要なパーティーの長さは青の点の時刻より短くなります。
ペアに属さない連続する \(2\) 人をペアにしても損をしないので、これを繰り返せば損をせずペアと次のペアとの間に人が高々 \(1\) 人しか入っていない状態にすることができます。