0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

選手 1 から選手 2^N までの 2^N 人の選手がトーナメント形式のプログラミング対決をします。選手 i のレートは A i です。どの 2 人の選手のレートも異なり、 2 人の選手が対戦すると常にレートが高い方が勝ちます。

トーナメント表は完全二分木の形をしています。より正確には、このトーナメントは以下の要領で行われます。

i= 1 , 2 , 3 , … , N について順に、以下のことが行われる。

各整数 j ( 1 ≤ j ≤ 2^N−i ) について、まだ負けたことのない選手のうち、 2 j − 1 番目に番号の小さい選手と 2 j 番目に番号の小さい選手が対戦する。準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求めてください。

2.制約

1 ≤ N ≤ 16
1 ≤ A i ≤ 10⁹
A i は相異なる
入力に含まれる値は全て整数である

3.入出力例

入力

4
6 13 12 5 3 7 10 11 16 9 8 15 2 1 14 4

出力

4.初見の感想

勝負を一つ一つ計算していると計算量が大きすぎる

5.学びポイント

試合の方法はきまっているので、1~2^N-1番までのトーナメントの勝者と2^N-1+1~2^N番目の勝者が決勝を行う
1~2^N-1番までの数の最大値と2^N-1+1~2^N番目の数の最大値を比較すると準優勝がわかる

6.コードと簡単な解説

using System;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            String[] input = Console.ReadLine().Split();
            long max = (long)Math.Pow(2, N);
            long[] A = new long[max];
            for (long i = 0; i < max; i++)
            {
                A[i] = long.Parse(input[i]);
            }
            long max_left = 0;
            long max_left_point = 0;
            for (long i = 0; i < (max / 2); i++)
            {
                if (A[i] > max_left) { max_left = A[i]; max_left_point = i+1; }
            }
            long max_right = 0;
            long max_right_point = 0;
            for (long i = (max / 2); i < max; i++)
            {
                if (A[i] > max_right) { max_right = A[i]; max_right_point = i + 1; }
            }
            if (max_left < max_right) { Console.WriteLine(max_left_point); }
            else { Console.WriteLine(max_right_point); }
        }
    }
}

7.最後に

すこし発想に時がかかってしまったので精進します

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 188 C - ABC Tournament