水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

Tenka1 Programmer Contest:D - Crossing

問題

beta.atcoder.jp

解法

図を書いてみると,1 ~ N の数字を三角形状に並べられるものがよいと気づくので,N が三角数であれば Yes,そうでなければ No となる.

どのように部分列を構成するかというと,

f:id:babcs2035:20181103143450j:plain

N = 15 の場合では,三角形の三辺を囲い,その後頂点の位置にある数字以外の辺上の数字と囲まれた中の数字を使いながら部分列を作るといい(図を見た方が分かりやすい).O(N).

解答

beta.atcoder.jp

N = 1 のときは三角形をなさないので,コーナーケースになる.

f:id:babcs2035:20181103143820p:plain