別解がある競技プログラミング(AtCoder)の問題を集めてみた

初めに

　本記事は競技プログラミングで有名なatcoderの問題の中から、別解がある問題たちの一部を集めた記事です。
　　ある程度の勉強時間を競技プログラミングに充てると、問題を見た際に一瞬で解法が浮かんでしまう状況がよくあります(たとえばAtcoderBeginnerContestの序盤の早解きなどがその例)。もちろん、一瞬で問題状況を把握して素早く処理することは素晴らしいことですが、それだと思考停止して問題を解いただけであり、いずれはレートが上がらない状況に陥ってしまいます。当然、手元でサンプルを考えて法則性をつかむような思考力が要求される問題では通用しません。
　また、個人的には水色コーダ中盤(レート1400ぐらい)からは1問からどれだけ学べるかが重要だと思ってます。(といいつつ筆者はこの記事公開当時(2024年５月)レート1200付近で停滞しています。)1つの問題をいろいろな見方で解けるようにすることで思考力が鍛えられます。並行して、より計算量を落とすテクニックや、知らなかったアルゴリズムを知ることができるきっかけにもなるためおすすめです.
　　掲載されている問題は全てABC(Atcoder Beginner Contest)からの出題です。難易度順に並んでいるとは限らないので、解けない問題の場合は、解法を見て復習することをお勧めします。
　atcoder界隈ではまだまだ弱いほうなので拙い部分等があるかもしれませんがご容赦ください。載せられている別解では実装例がない解説もあるため、解説に相当した実装コード(全てC++によるソースコード)をつけています。

問題

• ABC348E

  1. 重心を用いた解法(すぬけさんの解説はこの方針)
     ある頂点$v$に注目した際に$f(v)$の値がより小さくなる方向へ移動することをくりかえすといずれ$v$は重心になる。提出コード
  2. 全方位木DPによる解法。
     $val[v]$=$v$の部分木の重みの合計。
     頂点が$to$へ移る時に、コストの変化は$+(sumC-val[to])-val[to]$になる
     本番中にこちらの方針で解きました。提出コード

• ABC347D
  数学的な要素が強いと思います。
  1.桁DPとDPの復元 本番中にこの方法を思いつきました　提出コード
  2.各桁で(0,1)のうち、何が許されるかを考える。二進数の性質をうまく使う。MMNMMさんの解説　
  提出コード

• ABC331E

  1. 片方を固定して全探索　提出コード
  2. priority queueを用いた解法(公式解説)提出コード
  3. 二分探索を用いた解法 提出コード
  4. セグ木を用いた解法.setでの提出コード
     　いずれの解法もLの制約が小さいことをうまく利用します. たかだかL+1回目には食べ合わせのよいペアが出てくるため,Lを主役にした全探索をうまく思いつき,なにかしらのテクニック(二分探索やセグ木)を用いて高速化がポイントになります.

• ABC329E

  1. 逆から操作する解法(すぬけさんの解説はこの方法を使用)提出コード
  2. DPでの解法.本番中に思いつきたかった.(shiomusubi496さんの解説)
     提出コード1　提出コード2

• ABC326D
  方針はどちらも全探索ですが、実装の大変さが異なります

  • 1 physics0523の解法。再帰を用いた全探索とbitを用いてフラグを保持するというテクニックの組み合わせです。コードにコメントした提出コード
  • 2 すぬけさんの解法です。制約をうまく用いることで、探索すべき箇所を小さくします。 1と比べて実装が格段に楽です$O((N!)^3 \times N^2)$ 提出コード

• ABC323D

  • 1 二進数を用いた解法(公式解説の一つ目) この考え方ができるようなりたいです.提出コード
  • 2 愚直シミュレーション(公式解説の補足のほう)提出コード

• ABC315E
  典型のトポロジカルソートです。トポロジカルソートを解くアルゴリズムは2パターンの方針があります。

  • DFS　再帰を用いた解法 提出コード
  • BFS 幅優先探索 提出コード

• ABC312C

  • 1 二分探索 提出コード
  • 2 ソートを用いた解法 提出コード

• ABC311E
  1と2のどちらも公式解説参照

  • 1 二分探索 $O(HWlog(HW))$ 提出コード
  • 2 1を高速化したものです$O(HW)$ 提出コード

• ABC310D
  どちらも公式解説に載っています。

  • 1 bitDPを用いた解法。私が本番中に思いついたのはこの方針です。
    計算量$O(3^N TN)$提出コード
  • 2 再帰を用いる解法 計算量$O(N! \times N)$ 提出コード

• ABC308E

  • 1 累積和をもちいた解法(yuto1115さんによる公式解説はこちら) 提出コード
  • 2 {MEX} $\times${0,1,2}で分けた後に、Eを固定して二分探索　提出コード

• ABC307E

  • 1 包助原理 kyopro_friendsさんによる公式解説 提出コード
  • 2 円環DP　本番中に思いついたのはこの方針です。 提出コード
  • 3 漸化式を作る. MMNMMさんによる解説 提出コード

• ABC300F

  • 1 二分探索　けんちょんさんの記事を参考。　
    提出コード1
    提出コード2
  • 2 尺取り法 (すぬけさんの解説はこちらの方針)
    提出コード

• ABC296E

  • 1 DAG。再帰でサイクルを見つけます 提出コード
  • 2 ダブリング(shakayamiさんの解法)提出コード
  • 3 強連結成分分解 (evimaさんの解法)提出コード

• ABC292C
  けんちょんさんの解説

  • 1 $O(N√N)$の解法 提出コード
  • 2 $O(NlogN)$の解法. 調和級数を用いて1の解法を高速化します 提出コード

• ABC282F

  1. スパーステーブルの解法 提出コード
  2. 分割統治法の解法. (こちらは実装がすこし面倒)提出コード
     どちらもsunukeさんのコード解説あり.

• ABC271C
  以外と難しいと思います。本番中に解けませんでした。
  すぬけさんが解説しています。

  • 1 二分探索 提出コード
  • 2 ハッシュマップ(c++ではsetなど)を用いた解法 提出コード
  • 3 愚直シミュレーション（m_99さんによる公式解説）　提出コード

• ABC270E
  1,2の両方の解法ができるようになりたいです.

  1. 何周でKを超えるかを考える. 周期を用いて高速に求める(すぬけさんの解説はこの方針)
     提出コード
  2. 何周するかを二分探索して求める(kyopro_friendsさん解法)
     提出コード

  2の解法は実装が簡単になるためおすすめです.二分探索手法を知っていても言われるまで思いつくことができませんでした.

• ABC267E

  1. 二分探索「最大値の最小化」というキーワードなので決め打ちで考えると二分探索が思いつきます。 (公式解説)提出コード
  2. 優先度付きQueue (kyopro_friendsさんの解法)提出コード

• ABC258E

  • 1 ダブリングを用いた解法(すぬけさんが解説しています) 提出コード
  • 2 周期を用いた解法 方針が書かれた参考記事. 提出コード
    周期がかかわるものはダブリングを使うという考えも取り入れたいです.

• ABC256F

  • 1 遅延セグメント木 (potato167さんの解法)提出コード
  • 2 セグメント木 (kyopro_friendsさんの解法 すぬけさんによる解法もこの方法)
    提出コード

• ABC249D
  $M=\max(A_{i})$とする。$M \leq 2 \times 10^5$であることがポイントになります。

  • 1 $O(M √M)$この解説の解法1. 個人的には思いつきやすい解説です
    提出コード
  • 2 $O(MlogM)$ 公式解説はこちらを用いています
    提出コード

• ABC247E
  要素がY以上,X以下のみからなる数列へAを分断します.各々の数列考えたときに

  • 1 包助原理 $(Y \leq v \leq X) - (Y < v \leq X)-(Y \leq v < X) + (Y < v < X)$
    提出コード
  • 2 尺取り法　提出コード

• ABC238D

  • 1 xorとandがわかる形に持っていく(penguinmaさんの解説)提出コード
  • 2 x,yを2進数で表した際に各位の値が0か1かの$2^2$通りを調べる(すぬけさんの解説)提出コード

• ABC238G

  1. Moのアルゴリズムによる解法 提出コード
  2. ハッシュを用いた解法 physics053さんの解説
     提出コード

• ABC237D

  • 1 逆から見ていく公式解説 提出コード
  • 2 双方向リスト(c++の場合はlist)を用いて解くcirno3153さんによる解法
    提出コード

• ABC234D

  • 1 multisetを用いた解法$O(NlogK)$ 提出コード
  • 2 BIT(セグ木でも可)と二分探索を用いた解法.$O(Nlog^2N)$ 提出コード

• ABC228D

  • 1 インデックスの集合(c++ならsetやmap)を用意し,2分探索で求める
    提出コード
  • 2 経路圧縮を用いた解法(UnionFindでよく用いる)
    提出コード

• ABC217G

  • 1 包助原理、スターリング数を用いた解法.sunukeさんの解説はこちらを使用。数え上げに慣れていれば思いつきやすい方針だと思います。
    スターリング数についてはけんちょんさんの記事を参照
    提出コード

  • 2 dpを用いた解法. kyopro_friendsさんの解説。
    提出コード(forループver)
    提出コード(再帰ver)

• ABC159F
  ナップザックDPの派生

  1. ナップサックDPの状態に区間の情報を追加して考える
     hamayanhamayanさんの解法
     耳DP (けんちょんさんの記事も参考になります)
     提出コード

  2. 多項式の掛け算の係数と考えが同じ
     すぬけさんの解説の前半　 提出コード1
     すぬけさんの解説の後半 maspyさんの解説と同じ。 提出コード2

• ABC137D

  1. 制約が厳しいものから貪欲法、どうすれば正当な貪欲法に落とし込めるかが考えるポイントになります.(こちらが王道のやり方。すぬけさんが解説しています)
     提出コード
  2. マトロイドの性質を用いる解法.公式解説pdfを参照.
     マトロイドであることが貪欲法の正当性を保証します.
     (マトロイドについてはけんちょんさんの記事を参照)提出コード

最後に

この記事に掲載された問題を通して、みなさんの競プロのレベル向上に貢献できれば幸いです。今回掲載した問題達はごく一部なので、時間があれば第二弾を執筆するつもりです。ここまで読んでいただきありがとうございました。