Official
A - Three Cards Editorial by PCTprobability
[1]使うカードの条件
使うカードは書かれた整数が大きい \(3\) 枚です。これは、カード \(i\) が選ばれずカード \(j\) が選ばれていて、\(A_i > A_j\) の場合にカード \(j\) の部分をカード \(i\) にすることによって、整数が増加することから示すことができます。
[2]解の計算
使う \(3\) 枚のカードを決定できたため、カードをどの順番で並べるかの \(6\) 通りを全て試しその中から最大のものを出力すればよいです。大きい整数を先に並べることが必ずしも最大値を与えるとは限らないことに注意してください。
例えば、カードに書かれた整数が \(9,9,10\) の場合に大きい整数を先に並べてしまうと \(1099\) となりますが、\(9910\) を作ることが可能です。
よって、この問題を \(\mathrm{O}(N)\) で解くことができます。
posted:
last update: