第20回日本情報オリンピック　一次予選(第1回)

2020年9月20日
情報オリンピック日本委員会

解説

この課題には様々な解法が存在する．

解法 1 (単純な場合分け)

3 つの整数 A, B, C の大小関係は次の 6 通りしかない．

• A ≦ B ≦ C．
• A ≦ C ≦ B．
• B ≦ A ≦ C．
• B ≦ C ≦ A．
• C ≦ A ≦ B．
• C ≦ B ≦ A．

ただし，与えられる整数のうちいくつかは等しい場合があるため，これらの関係には等号がついている．また，ある入力が複数の大小関係に該当する場合もある．

if 文などを用いてこれら 6 つの関係を分岐させ，2 番目に大きい整数を出力すればよい．

解答例(C言語) はこの解法 1 を実装している．

解法 2 (並び替え)

入出力例 2 の説明にあるように，3 つの変数 A, B, C の中身を入れ替え，降順になるようにする．このとき，2 番目に大きい整数は B の中身になる．

では具体的にどのように中身を入れ替えればよいのか．その一例を次の疑似コードに示す．

if(A < B) swap(A, B);
if(B < C) swap(B, C);
if(A < B) swap(A, B);

ただし，swap(x, y) は変数 x と変数 y の中身を入れ替える操作を意味する．

この 3 回の入れ替え操作を行うことで，必ず A, B, C の中身が昇順になることは証明できる．

なお，数を昇順などに並び替える操作をソートと呼び，様々なソートアルゴリズムが知られている．特に，上記操作はバブルソートと関係がある．

解法 3 (最小値と最大値)

3 つの整数 A, B, C の最小値を m，最大値を M とおく．このとき，2 番目に大きい整数は A + B + C - m - M と表せる．

最小値や最大値を求めることは 2 番目に大きい数を求めるのと同じくらい難しいが，各プログラミング言語に標準的に実装されている min 関数と max 関数を用いると簡単に求められることがある．

解答例(C++,別解) はこの解法 3 を実装している．