7K12 blog

猫でも分かるアルゴリズム解説

AGC006 B - Median Pyramid Easy

f:id:tkr987:20210302163244p:plain

https://atcoder.jp/contests/agc006/submissions/20609588

  • 中央値なので小中大(x-1, x, x+1)で並べる
  • x, x, y の中央値は x

f:id:tkr987:20210304145103p:plain

まず、一番上の段がxになるようにしないといけないので真ん中にxを置きたくなる(ぇ 次に、中央値なので x-1, x, x+1 と数字を並べてみる。残りの数字をどうするかだが実は適当で良く、とりあえず昇順に並べる。N段目の中央1つ隣のブロックが [大小中] となるため、N-1段目に [x, x, y] のような数列が出現する。x, x, y の中央値はxなので1段目がxになる。なお、xの値によってはN段目の中央1つ隣のブロックが [中大小] のようになることもあるが、結果的に同じなので大丈夫。

実装はdequeを使うと先頭と末尾にO(1)で挿入できて楽。

コーナーケースは x-1, x, x+1 と並べることから x=1 と x=2 * N - 1