AtCoder Problems に「構築」というバチャがある
当記事では AtCoder 自体の説明はしません。AtCoder Problems の説明もしません。ごめんなさい！
AtCoderでは構築問題と呼ばれるジャンルの問題がしばしば出題されます。ある条件を満たす数列をひとつ作れとか、ある条件を満たすグラフをひとつ作れとか、そういうやつです。
そんな構築問題ばかりを集めたバチャ（バーチャルコンテスト。AtCoderの過去問を寄せ集めて作られた問題集のようなもの）を AtCoder Problems で発見しました。その名も「構築」です。
ところが全体的に難易度は高めであり、過去のARCやAGCから拾われてきた青や黄色の問題がほとんどですのでご注意ください。初心者には無理です。私も無理です。
構築問題を特訓したい上級者にはとても役立ちそうですね。このバチャの作成者に感謝ですね。（作成者が誰なのか不明ですが…）
せっかくなので1問目だけ紹介
上記のバチャの1問目は「Median Pyramid Easy」です。
問題文ページはこちら。↓
よわよわな私でもこの問題はなんとか正解できました。
以下、どんな問題か、私はどう解いたか、紹介してみようと思います。
問題の概要
下記ルールに従ってピラミッド型盤面に数字を書き込むことを考えます。
- 最下段には順列を書き込む
- マスの数を $N$ とすると、順列とは $1, 2, …, N$ を並び替えたもの
- それ以外のマスには左下、真下、右下のマスに書き込まれた整数の中央値を書き込む
- 例えば1と6と3の中央値は3
上図のサンプルだと、最下段の順列を 1 6 3 7 4 5 2 にした結果、てっぺんは 4 となりましたね。
では逆に、てっぺんの数字だけが分かっているとき、最下段の順列を言い当てることはできますか？
ピラミッドの高さ（何段あるか）と、てっぺんの数字が入力されたとき、
最下段の順列としてありえるものをひとつ求めて出力するプログラムを作成してください。
私が考えたこと
いろいろなピラミッドを試しに作ってみたところ、ただ順番に $1, 2, …, N$ を並べるだけでよい（並び替える必要はない）ことに気付きました。
下図をご覧ください。
例えばてっぺんを $3$ にしたかったら、最下段の中央も $3$ にして、
- その $3$ の右隣は $4$ で、その右隣は $5$ で、…と増やしていく（$7$の次は$1$）
- その $3$ の左隣は $2$ で、その左隣は $1$ で、…と減らしていく（$1$の次は$7$）
という流れで書き込んでいく感じです。
これにより、てっぺんの数字が $2, 3, 4, 5, 6$ であるようなピラミッドは作成可能であることが分かりました。
一方、てっぺんの数字が $1$ や $7$ であるようなピラミッドは絶対にありえません。なぜならこのピラミッドには $1$ より小さい数や $7$ より大きい数は登場しないため、「中央値を取る」ときに $1$ や $7$ は必ず捨てられてしまうからです。
ここまでの話は、最下段のサイズが $7$ でなくても、どんなサイズのピラミッドでも成立します。
私の提出ソースコード
これです。↓
ちなみに言語はJavaで書いたのですが、私の提出したコードの長さは 435 Byte でした。
これは本日 2025/6/25 時点で、Javaでの正解者のうち最も短いコード（短さランキングで第一位）です。
シンプルなロジックで正解を得られたので嬉しいです。
…とはいえ私のアイデアは試しにピラミッドをいくつか作っているうちに気付けるものだと思います。
当記事で紹介した「構築」のバチャを利用して、もっといろいろな構築問題にチャレンジしてみたいですね。
今回は以上です。