x回のスワップ後に2人のライバル学生間の最大距離を求めるC++プログラム

4つの数値 n、x、a、b が与えられているとします。一列に並んだ n 人の学生がおり、その中に2人のライバル関係にある学生がいます。1人は位置 a に、もう1人は位置 b にいます。位置は左から右へ 1 から n まで番号が付けられています。この2人の学生の間の距離を最大化したいと考えています。次の操作を x 回まで実行できます。隣り合う2人の学生を選んで入れ替えるというものです。x 回のスワップ後に実現可能な最大距離を求める必要があります。

例えば、入力が n = 5、x = 1、a = 3、b = 2 の場合、出力は 2 になります。これは、位置 3 と位置 4 の学生を入れ替えることで、2人の学生間の距離が |4 − 2| = 2 になるためです。

解法のアプローチ

この問題は非常にシンプルな計算で解くことができます。考え方のポイントは次のとおりです。

• 1回のスワップで距離は最大 1 ずつ増やせます。したがって、x 回のスワップで距離は最大 |a − b| + x まで伸ばせます。
• しかし、距離には物理的な上限があります。列の両端に2人が到達した場合の最大距離は n − 1 です。

以上をまとめると、答えは次の式で求められます。

min(|a - b| + x, n - 1)

つまり、「スワップで伸ばせる距離」と「列の構造上の最大距離」のうち、小さい方を採用します。

実装例

以下にC++による実装を示します。

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int x, int a, int b) {
    return min(abs(a - b) + x, n - 1);
}
int main() {
    int n = 5;
    int x = 1;
    int a = 3;
    int b = 2;
    cout << solve(n, x, a, b) << endl;
}

入力

5, 1, 3, 2

出力

2

計算量

この解法は単純な算術演算のみで構成されているため、時間計算量は O(1)、追加のメモリ使用量も O(1) で済みます。入力サイズが大きくなっても高速に動作するのが特徴です。