[AtCoder] AGC 041 A – Table Tennis Training

問題

方針

両者の距離が \( 2 \) の倍数のとき、向かい合うように進む事が最適です。また、卓 \( 1 \) または \( N \) に留まり続けることは最適ではありません。

\( (B – A) \bmod 2 = 0 \) のとき

このとき、両者は向かい合うように進めばいいので、\( \dfrac{B – A}{2}\) となります。

\( (B – A) \bmod 2 \neq 0 \) のとき

\( 2 \) 通り考えます。一つ目は、卓 \( A \) にいた選手が卓 \( 1 \) に向かって進み、卓 \( 1 \) で一回勝利したあと負け続けます。このとき、卓 \( B \) にいた選手は勝ち続けます。二つ目は、卓 \( B \) にいた選手が卓 \( N \) に向かって進み、卓 \( N \) で一回敗北したあと勝ち続けます。このとき、卓 \( A \) にいた選手は負け続けます。

したがって、

\[ \min( A + \dfrac{B – A – 1}{2}, \ N – B + 1 + \dfrac{B – A – 1}{2})\]

が答えとなります。

コード