【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた

2021.01.02

はじめに

E869120 さんが レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 にまとめた「分野別　初中級者が解くべき過去問精選 100 問」を C++ で解いてみました。解きっぱなしだと忘れそうなため、各問題の解答例と解説のようなものを書きました。

先行記事と先行動画

投稿前に見つけた過去問精選 100 問の解説・コメント記事を挙げておきます。

過去問精選 100 問の動画もありました。

注意

  • 私 は 元記事 の目標 (水色) に未達の緑色コーダーです。 Highest は水色に達しましたが、本記事は目標未達のときに書きました。所々誤りがあるかもしれません。本文を読む際は鵜呑みになさらず、疑ってお読みください。
  • 私が書いた解法とは別の有名な解法があるかもしれません。基本的には 1 問につき 1 解法について記載します。主要な解法を網羅したわけではないこと、ご留意ください。
  • (時間) 計算量と実行時間については以下の記事を参考して書いています。正確に測ったわけではありませんが、AOJ と AtCoder の環境では参考元の見積もりはおよそ正しい印象です。
  • 計算量オーダーから計算ステップ数を概算する際、定数倍をあまり考慮していないなど、粗い見積になっています。参考程度に考えていただければと思います。
  • 解答例は C++14 で書いています。コンパイラは gcc (9 以降) を想定しています。
    • ローカルでは -std=c++14 -Wall -Wextra -Werror -g をつけてコンパイルしています。
    • AOJ と AtCoder での実行環境については各提出結果の言語の設定をご確認ください。
  • 数式としての変数とプログラムの変数を同一視している箇所が多数あります。急に i という変数が出てきて定義がわからない場合、直前に i という変数が無いかご確認ください。
  • 参考文献は問題ごとにリンクを貼るなどの形で記載します。ただし、AtCoder の解説、JOI の解説、有志コンテストの解説、及び、AOJ の解説は全問参考にしております。冗長性を避けるため、各問題での言及はせず、ここに参考にする旨を記載します。
  • unordered_map と unordered_set の使用は避けます。実行時間の制約に違反しない限りは map, set の使用のみ言及します。理由は下記の 2 点です。
    1. map, set で間に合うことが多いです。
    2. Key の型によってはハッシュ関数を実装する必要があるため、少し面倒です。(例: pair )
  • AtCoder Library を使用します。

解答例

分野別に記事を分けて、解答例と解説を書きました。