Tenka1 Programmer Contest:D - Crossing
問題
解法
図を書いてみると,1 ~ N の数字を三角形状に並べられるものがよいと気づくので,N が三角数であれば Yes,そうでなければ No となる.
どのように部分列を構成するかというと,
N = 15 の場合では,三角形の三辺を囲い,その後頂点の位置にある数字以外の辺上の数字と囲まれた中の数字を使いながら部分列を作るといい(図を見た方が分かりやすい).O(N).
解答
N = 1 のときは三角形をなさないので,コーナーケースになる.