AIで解説 AtCoder攻略　数列構成

数列構成ページの位置づけ

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

移動や選択のパターンを添字で表し、候補を構成して評価します。ABC128 Fでは累積和を使って候補を高速に比較します。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

最初の一問として、ABC247 C 1 2 1 3 1 2 1（公式解説）を解きます。S0=[0]から、前の列・n・前の列を再帰的に連結します。定義をそのままコードにすると構成を間違えにくくなります。

def build(n):
    if n == 0:
        return [0]
    previous = build(n - 1)
    return previous + [n] + previous

N = int(input())
print(*build(N))

出力長が2^(N+1)-1なので、出力を含めてO(2^N)時間・O(2^N)メモリです。

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

問題	公式解説	出題意図	difficulty
ABC389 A 9×9	公式解説	入力された1桁を9倍して9×9の値を出力する。	-1170
ABC343 A Wrong Answer	公式解説	Official editorial intent is classified as simple avoidance construction.	-960
ABC382 B Daily Cookie 2	公式解説	クッキーを左から食べる規則を区間更新としてシミュレーションする。	-732
ABC452 B Draw Frame	公式解説	Draw the requested rectangular frame by filling boundary cells.	-713
ABC436 B Magic Square	公式解説	Construct the prescribed odd-order magic square by the standard cyclic placement.	-387

問題	公式解説	出題意図	difficulty
ABC301 B Fill the Gaps	公式解説	Insert every integer between consecutive checkpoints in order.	-314
ABC395 B Make Target	公式解説	Construct the requested target matrix by applying the row/column conditions directly.	-286
ABC425 B Find Permutation 2	公式解説	公式Editorialの方針を permutation construction として整理する。	-233
ABC250 B Enlarged Checker Board	公式解説	各ブロックの行列番号の偶奇で#と.を切り替え、拡大チェッカー盤を出力する。	-119
ABC247 C 1 2 1 3 1 2 1	公式解説	S_n=S_{n-1},n,S_{n-1}の再帰で数列を構成し、指定Nの列を出力する。	5

問題	公式解説	出題意図	difficulty
ABC140 C Maximal Value	公式解説	各A_iの上限が隣接するBの小さい方であることを示し、その上限を全要素に採用して総和を最大化する。	39
ABC380 C Move Segment	公式解説	1の塊の位置と長さを取得し、K番目の塊を直前の塊へ移した文字列を構成する。	166
ABC139 D ModSum	公式解説	各項の余りの上限i−1を同時に達成する順列を構成し、1からN−1の総和を最大値とする。	354
ABC357 C Sierpinski carpet	公式解説	Official editorial intent is classified as recursive sierpinski.	370
ABC335 D G. Loong and Takahashi	公式解説	Fill the grid in spiral order and place T at the center.	431