AGC 006 B Median Pyramid Easy

構築じゃなくとも愚直を書いてから高速化するのって強い動き？教えて強い人

問題概要

要素数2N-1個の順列が与えられたとき、その数(i番目とする、2<=i<=2N-2)の一つ上にi-1番目、i番目、i+1番目の中央値を書き込む、という操作を考える。
この操作をN回繰り返すと数は1つになるが、その数をxとする。数xと回数Nが与えられた時、元の順列としてありえるものを答えよ。ない場合はNoと答えよ。

取った方針

N=5くらいまでなら愚直にやっても間に合うので、順列をnext_permutationで全列挙して全部試すと、1と2N-1は最後の一つ(以後頂点とする)にはならないことが分かる。最初の操作で消えてしまうのでそれはそう。
ここで、頂点に行くのが一番難しいのは2もしくは2*N-2であるという気がしてくるので(理由:2より小さい数は1しかなく、中央値になるには3つの組の中に必ず1が含まれるか2つ以上の2が含まれる必要があるため。)、2が頂点にくる順列を出力してみる。例えば以下である。(N=4)

      2
    2 2 5
  3 2 2 5 6
3 4 1 2 5 6 7

これを眺めると、2が2つ隣り合っている場合その上も2が2つ隣り合うことが容易にわかるので、頂点の下にxを二つならべればよいことが分かる。
N=2の時とN=2N-2の場合をいい感じに例外処理して終了。

正しい方針(解説の方針)

同上

得られた知見

• 構築->愚直にできるなら愚直に試して解を眺めてみる(解を眺められる場合のみ)
  • 解を眺められない場合の方が多い気がする
• 解を眺める際、一番厳しい制約が分かるならばそのケースを試してみる

  解くのに必要な要素

• 解を出力して眺めてみる心

  周辺調査によって得られた知見

  なし