AIで解説 AtCoder攻略　寄与分解

寄与分解ページの位置づけ

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

全体の組合せを要素ごとの寄与へ分解し、BITや順序付き構造で高速に集計するページです。

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

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

最初の一問として、ABC287 A Majority（公式解説）を解きます。各投票を1回ずつ読み、賛成票だけを合計します。全体の半分を超えるかを最後に判定する、最も基本的な集計です。

N = int(input())
for_count = sum(input().strip() == 'For' for _ in range(N))
print('Yes' if for_count > N / 2 else 'No')

入力を1回読むだけなのでO(N)時間、追加メモリはO(1)です。全票を何度も数え直すO(N^2)の実装を避けられます。

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

問題	公式解説	出題意図	difficulty
ABC287 A Majority	公式解説	賛成票の数が過半数か判定する。	-1023
ABC260 A A Unique Letter	公式解説	3文字の出現回数が1回の文字を探す。	-989
ABC447 A Seats 2	公式解説	Count the available seats satisfying the two-seat condition.	-904
ABC268 A Five Integers	公式解説	5個の整数の異なる値の個数を数える。	-876
ABC240 B Count Distinct Integers	公式解説	入力された整数を集合へ入れ、異なる値の個数を出力する。	-819

問題	公式解説	出題意図	difficulty
ABC365 B Second Best	公式解説	Official editorial intent is classified as second max.	-757
ABC378 A Pairing	公式解説	各値の出現回数を2で割った整数部分の総和を求める。	-755
ABC426 B The Odd One Out	公式解説	公式Editorialの方針を odd one out frequency として整理する。	-703
ABC359 B Couples	公式解説	Official editorial intent is classified as pair pattern.	-678
ABC216 B Same Name	公式解説	姓と名の組を集合に登録し、同一の組が再登場するかを判定する。	-537

問題	公式解説	出題意図	difficulty
ABC241 B Pasta	公式解説	注文ごとに在庫数を1つ減らし、全注文を供給できるかを判定する。	-503
ABC386 B Calculator	公式解説	連続する00を一回のボタン入力としてまとめ、必要入力回数を数える。	-497
ABC393 B A..B..C	公式解説	Enumerate the middle position and equal-distance endpoints of an A-B-C pattern.	-480
ABC338 B Frequency	公式解説	Official editorial intent is classified as frequency count max.	-449
ABC381 B 1122 String	公式解説	隣接2文字が等しいことと、各文字がちょうど2回現れることを同時に確認する。	-417