読者です 読者をやめる 読者になる 読者になる

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