本ページは twitter 等で見かけた競技プログラミングに関する質問へコメントする際に、文字数制限や数式の描画などの理由から、元のメディアでのコメントが面倒なときにコメントを書いているページになります。
コメントを書いた際に、転載の許諾をいただくようにしていますが、私の手違いや、後日禁止したくなった場合は twitter アカウント までご連絡ください。削除いたします。
jsc2021C (Max GCD 2) のような問題での計算量改善方法の思いつき方
すみません、申し訳ないのですが、皆様のお知恵をいただきたく。どうしても、計算量のカベを破れるようになりたいのです。でも、最近限界を感じています。
画像のような課題が典型的な悩みのタネです。
どう対処されていますか？#atcoder #プログラミング初心者 pic.twitter.com/V1MLBngQJq— Coding頑張ることにした人 (@EnjoyUrHobby) May 6, 2021
一意見ですが、解き方のパターンと数学 or アルゴリズムの知識を覚えていくといいかもしれません。
挙げていただいた問題 だと、探索する変数の候補 (x, y, \gcd(x, y)) のどれか 1 つを固定し、計算量を減らすことを考えるのは良く見る解き方のパターンだと思います。
解き方のパターンを踏まえた上で、数学 or アルゴリズムの知識があれば以下のように解法を思いつきやすくなります。
ケース 1
1 から b までの範囲にある、正の整数 c の倍数の個数は \lfloor b / c \rfloor (切り捨て除算) 個であることを知っているならば、\gcd(x, y) の候補 (1 から b までの整数) を全探索する公式の解法を思いつく可能性があります。
ケース 2
エラトステネスの篩 の要領で、a から b までの整数の範囲にある、正の整数 c の倍数の個数を計算量 O((b – a) / c) で数えられることを知っているならば、u2dayo さんの Qiita の解法 を思いつきやすくなります。
ケース 3
整数 x の約数の列挙を計算量 O(\sqrt{x}) でできることを知っていれば、a から b までの整数の約数を全て列挙する解法 を思いつくかもしれません。
解き方のパターンや数学 or アルゴリズムの知識を覚えていく順番は人それぞれだと思いますが、私はだいたい レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 に沿って進めています。
