Logfiles

AGC 006: B Median Pyramid Easy

問題

B: Median Pyramid Easy - AtCoder Grand Contest 006 | AtCoder

$i$ 段目に $2 * i - 1$ 個のブロックがあり、ピラミッド型に積まれている。ブロックには数字がかかれていて、あるブロックの数字はその左下と真下と右下のブロックに書かれた数字の中央値である。ブロックの段数と、最上段のブロックに書かれた値が入力として与えられる。このとき、最下段が $1〜N$ の順列となるような場合は存在するか。存在するならば、1行目に"Yes"と出力し、2行目以降は条件を満たす順列を1つ出力せよ。そのような順列がひとつも存在しない場合は"No"と一行に出力せよ。

$2\le N\le 10^5$
$1\le x\le 2\times N−1$

解説

小さめのケースで順列を総当りして手で試してみる。するとまず第一に得られそうな観察として、最上段は1か2*N-1以外なら何でも"Yes"となりそうだというものがある。次に、段中の適当な2段に着目してその関係を考える。上の段の値を $x$ とおく。 $x$ は下の段の3つの値の中央値であるので、下の段のうち少なくとも2つは $x$ 以上で、そのうちの1つが $x$ である。2つ $x$ 以上の値が並ぶと、その上も2つはx以上の値、その上も…と続く。つまり、最下段の中央が以下の何れかのようであれば、最上段を必ず $x$ にすることが出来る。

$[ ..., x-2,x,x+1,x-1,... ]$

$[ ..., x+2,x-1,x,x+1,... ]$

中央以外は残った数を適当に並べれば良い。また、上の2ケースは何れも中央に4つの値を用いているので、最下段が3つしかない $N\ =\ 2,\ x\ =\ 2$ のケースだけは、別個に場合分けして"1 2 3"と出力しておくと良い。

int main() {
 
  int N, x; scanf("%d%d",&N,&x);
  // N段目は必ず奇数
  int M = 2 * N - 1;
  if((M + 1) / 2 == x) {
    puts("Yes");
    for(int i=0; i<M; i++) {
      printf("%d\n", i + 1);
    }
    return 0;
  }
  else {
    if(x == 1 || x == M) {
      puts("No");
    }
    else {
      puts("Yes");
      if(N == 2) {
        cout << "1\n2\n3\n";
        return 0;
      }
      deque<int> vs1 = {x-2,x,x+1,x-1};
      deque<int> vs2 = {x+2,x-1,x,x+1};
      bool ok1 = 1;
      for(auto e: vs1) if(e <= 0) ok1 = 0;
      if(ok1) {
        bool flag = 1;
        for(int i=1; i<=M; i++) {
          if(x-2==i||x==i||x+1==i||x-1==i) continue;
          if(flag) vs1.push_back(i);
          else vs1.push_front(i);
          flag ^= 1;
        }
        for(auto e: vs1) cout << e << endl;
      }
      else {
        bool flag = 1;
        for(int i=1; i<=M; i++) {
          if(x+2==i||x-1==i||x==i||x+1==i) continue;
          if(flag) vs2.push_back(i);
          else vs2.push_front(i);
          flag ^= 1;
        }
        for(auto e: vs2) cout << e << endl;
      }
    }
  }
  
  return 0;
}

感想

AtCoderはEditorialが日本語で丁寧だし動画もついてるので解説することがなくなるけど、解説記事書かないと復習を忘れやすいのでブログを出来るだけ書いていきたい