IJPC - A解説
- 2. 問題概要 ? ?人の人が一列に並んだ ?個の座席に座っ ている ? ?番目の人の座っている座席の両側ともに少 なくとも ?? 個の空席が連続して存在している ? このとき、?の最小値を求めよ
- 3. 解法 ? ?人の人が並ぶ順番が決まったら、あとは隣 り合う二人の間隔はその?の値のmaxだけ開 ければよい ? 予想として、空席の数は(?の合計)+(?のmax) が最小になるのではないかと思う
- 4. 証明 ? ?? が小さい順に並べればこれは実際に構成 できるので、これが最小であることを示せば よい ? これは、帰納法により、各ステップで?? が最 大のものを取り除いていくことで示すことがで きる