動的計画法を行い答えを求める \(O(N)\) 時間の解法と、うまく式を変形して答えを求める \(O(\log N)\) 時間の解法の \(2\) つを紹介します。

\(O(N)\) 解法

\(dp[i]\) を \(i\) 人の選手が大会に参加する時の試合回数とします。明らかに \(dp[1]=0\) です。

試合の順番によって試合回数が変わることがないので、\(i-1\) 人で試合を行った後に \(1\) 人追加することを考えます。

まず \(i-1\) 人で \(dp[i-1]\) 回の試合を行うと列 \(0\) から列 \(i-2\) には \(1\) 人が並んでいます。

そこに列 \(0\) に一人追加して列 \(0\) から列 \(i-2\) まで順に \(i-1\) 回の試合をしていきます。

すると列 \(0\) に \(i-1\) 人が、列 \(i-1\) に \(1\) 人が並びます。

最後に \(dp[i-1]\) 回の試合を行うと、全ての列に \(1\) 人が並び大会が終了します。

よって \(i\) 人で大会を行うときには \(2 \times dp[i-1] + i - 1\) 回の試合が行われ、

\[ dp[i] = 2 \times dp[i - 1] + i - 1 \]

という式を得られます。

\(i=2,\dots ,N\) の順に \(dp[i]\) の値を求めていくことで、この問題を \(O(N)\) 時間で求めることができました。

\(O(\log N)\) 解法

先ほど出てきた式をうまく式変形することで、より高速に答えを求めることができます。

\[ \begin{aligned} dp[n] &= 2\times dp[n-1] + n - 1 \\ &= dp[1] \times 2^{n-1} + \sum_{i=2}^{n} (i-1)\times 2^{n-i} \\ &= \sum_{i=2}^{n} \sum_{j=i}^{n} 2^{n-j} \\ &= \sum_{i=2}^{n} 2^{n-i+1} - 1\\ &= (2^n - 2) - (n - 1) \\ &= 2^n - n - 1\\ \end{aligned} \]

となり、繰り返し二乗法を利用することで \(O(\log N)\) 時間で求めることができます。