604 d beautiful sequence
まず, 偶数に着目する
0 0 0 ... 0 2 2 2 ... 2 (1)
というようにする
1は(1)のどこにも入れられる
3は2 2の間か2の横の端にしか入れられない
1と3は並ばないので, 独立に考える
以上より, 制約のある3の入れられる場所をなるべく多くするため,
偶数は(1)のように並べる
ポイントは, 貪欲の証明
各々の数の可能な位置関係の制約
解法
スタートは存在する数のうち, 小さい方から2つを試す
0 ~ 3全てあるなら0と1
1 0 1 0 ... 0 1 2 1 2 ... 2 3 2 3 ...
スタートは
0 1 0 ...
かもしれない
誤った考察
入力に関して, 隣が0でない限り差が1以下だと思い込む
反例 : 3 5 3 0
テキトーに描いて作ったケース
2 1 2 1 0 1 2 3 2
で
1 3 4 1
が入力になる
ただ, 1 3 4 1から一意に上の答えにはならない
参考
テストケース
3 5 3 0
YES
0 1 0 1 0 1 2 1 2 1 2
1 3 4 1
YES
2 1 2 1 0 1 2 3 2
別解
0 1 2 1 2 1 2 3 2
