AIで解説 AtCoder攻略　組合せ

組合せページの位置づけ

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

順列の順位や組合せの数を、階乗と未使用要素の数え上げへ分解するページです。

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

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

最初の一問として、ABC225 A Distinct Strings（公式解説）を解きます。3文字の並べ方を全て作り、重複をsetで取り除きます。文字が同じ場合だけ同じ並べ方が重なることを、そのまま確認できます。

from itertools import permutations

S = input().strip()
patterns = {''.join(order) for order in permutations(S)}
print(len(patterns))

3!通りしかないのでO(1)です。文字数が大きい場合は階乗全探索ではなく、出現回数から数える方法を選びます。

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

問題	公式解説	出題意図	difficulty
ABC300 A N-choice question	公式解説	Ai+BiがXになる選択肢の個数を数える。	-1147
ABC225 A Distinct Strings	公式解説	3文字の重複個数に応じて異なる並べ方の数を場合分けする。	-994
ABC466 B Representative Balls	公式解説	Count representative-ball selections with combinations.	-552
ABC342 B Which is ahead?	公式解説	Official editorial intent is classified as permutation position query.	-378
ABC403 B Four Hidden	公式解説	公式Editorialの方針を four hidden string count として整理する。	-277

問題	公式解説	出題意図	difficulty
ABC392 C Bib	公式解説	Invert the bib-number permutation and compose it with the staring-person permutation.	-43
ABC285 C abc285_brutmhyhiizp	公式解説	Interpret the uppercase word as a one-indexed base-26 number.	25
ABC195 C Comma	公式解説	For each digit length, count how many numbers up to N contain each comma position.	235
ABC185 C Duodecim Ferra	公式解説	Split L centimeters into twelve positive parts, giving C(L-1,11).	373
ABC276 C Previous Permutation	公式解説	Apply the standard previous-permutation operation to the given permutation.	389

問題	公式解説	出題意図	difficulty
ABC150 C Count Order	公式解説	全順列を辞書順に生成し、PとQより小さい順列の個数の差から順位差を求める。	422
ABC382 D G. Keep Distance	公式解説	隣接差制約を変数変換して非減少列の個数へ落とし、組合せで数える。	685
ABC324 D G. Square Permutation	公式解説	Enumerate permutations of digits and test whether the square root is integral.	895
ABC163 D Sum of Large Numbers	公式解説	選ぶ個数ごとに作れる和が最小値から最大値まで連続することを使い、K〜N+1個の場合の範囲の個数を加算する。	960
ABC202 D aab aba baa	公式解説	At each position count strings beginning with a, and choose a or b according to K.	966