3056

円卓に偶数人の人が並んでいて、それぞれが飲み物の入ったグラスを持っている。手が他の組と交差しないように二人一組で乾杯を行うとき、同じ飲み物を持った組は最大でいくつ作れるか、という問題。

典型的なDPなので、何も考えずにやれば人数NについてN^3くらいで終わる。これだとさすがに通らないので、後は定数倍高速化するだけ。

円卓であるという性質は、実際には円卓のどこかを決めて、そこを跨ぐような処理を禁止できる。この処理は、各組について、両方の人から見たときの処理をするのではなく、円卓の決められた位置から見て(たとえば)時計回りに近い方の人から見たときの処理だけをすることに等しい。(つまり倍程度の高速化が実現される。)

もしかするとオーダーを変えるような方式があるのかも知れないけれど、この程度の高速化で通ったので想定解だと思う。(他の問題に比べて若干長めに時間が取られている。)