Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

解法キーアイデア集

競技プログラミング お話

やあ、こんにちは、もつ鍋です。お元気に日々をお過ごしでしょうか？
さて本記事は、どんなに考えても解法が生えねぇというときに、とっかかりとなるキーアイデアを書き溜めていくものです。以前バグった原因集という記事を書きましたが、これは問題がおおよそ解けたはずなのに、なぜか通らないというときにしか使えません。そこで今回の記事を書こうと至ったわけです。

この記事は思いつき次第その都度更新していくので、初期段階では情報量は無です、気にしないでください。あとみなさんからのいろんなキーアイデア、募集いたします。

⚠️そもそも誤読してませんか？

解法なんも思いつかん笑。ってなってるとき、割とあるのは誤読です。問題文をもう一度読み直して、誤読していないかしっかりチェックしましょう。

  • Nが思ったより小さかった
  • ただのグラフかと思ったら木でした
  • ただの有向グラフだと思ったらDAGでした
  • 最大かと思ったら最小でした
  • ちょうどhoge回かと思ったらhoge回以下でした
  • 特殊な制限(多種多様)

などの誤読はよくあるので、気をつけましょう。

天使の囁き

本項で、固まった思考の堰を崩せるような、キーアイデア、キーセンテンスを羅列していきます。使い方としては、問題が解けねぇ！ってなったときに眺めると、突然解法が降ってきます(マジ！？)。下の方は具体的すぎるので、今後増えてきたら問題ジャンル別に分けるかもしれません。

アイデアの詳細

制約からエスパーしましょう

制約をゆるくすると問題は難しくなりがちです。基本的に制約を見たら大雑把な解法のオーダーはわかるものです。オーダーが分かれば、大体の方針も察しがつくと言うものです。以下にまとめておきましょう*2。

制約 オーダー 解法
N\lesssim10 \tilde{O}(N!) 順列全列挙
\tilde{O}(4^N) 部分集合の組など全列挙
N\lesssim15 \tilde{O}(3^N) 部分集合全列挙
N\lesssim20 \tilde{O}(2^N) bit全探索,部分集合添字でほげ
N\lesssim40 \tilde{O}(2^{\frac{N}{2}}) 半分全列挙*3
N\lesssim50\sim500 \tilde{O}(N^3),\tilde{O}(N^4),\tilde{O}(N^5) 区間DP,添字えぐいDP,遷移えぐいDP,フロー
N\lesssim5*10^3 \tilde{O}(N^2) 色々
N\lesssim10^7 \tilde{O}(N) 色々
N\lesssim10^{12} \tilde{O}(\sqrt{N}) 素因数分解とか
N\gtrsim10^{12} O(1),O(log(N)^k) 算数,桁DP

と色々あるわけです。制約を見たときになんとなくこんな感じだろと思うのは、最悪テクニックではありますが、実際のところやってない人はいないと思うので、なんとなくは身につけておいていいとは思います。

制約に囚われるな

は？って感じですね。制約からエスパーすることは有用なことも多いですが、これのせいで思考が固定されて、本来の解法が全く生えなくなってしまうことは多々あります。これとかこれ*4とか。
制約を緩くしても本質的に問題が易しくならない場合、制約を緩くすることで制約エスパーされないように問題を作ることができます。またどうせ指数とか思ってたら、えぐい指数の多項式オーダーなんてこともあります。そのような問題は決して多くはありませんが、少なくもありません。制約で完全に解法を決め打ちしてしまうのはやめましょう。ただ、制約に騙せる問題は、結構高度な発想の転換が要求されることも多いです。まあそこは頑張ってください(は？)。

小さいケースで実験しましょう

どうしても何も思いつかないとき、特に数え上げやゲームのときなど、まず小さいケースで実験をすることは大事です。これは算数や数学をやっている時も同じことですが、実際に手を動かして、具体例を動かすと、思考のしやすさが段違いです。また手元には折角コンピュータがあるのですから、小さいとは言っても、それなりの大きさの具体例を解くことも可能です*5。

極端なケースで実験しましょう

小さいケースと同様、極端な場合での思考が、役に立つ場合があります。これは具体例がないと何言ってるのかわからないと思うので、いつか適当に具体例を探して追記しておきます。

決め打ち

最大値や最小値などを考えるとき、答えを決め打ちして、二分探索などをすることはよくあります。また複数の状態があるものを、状態を決め打って、その状態についてだけ解く、などということもよくあります。

必要条件を列挙

問題中の条件を同値な言い換えをしてみると、問題が解きやすくなるというのはよくあることです。ただ同値な言い換えはなかなか難しいものです。ここで、自明な必要条件を列挙すると、必要十分になってるみたいなことはよくあります。必要条件を考えることで思考が後退することはまずないですし、考えることがなくなったら、とりあえずいろんな必要条件を考えるのは、悪くない選択だろ思います。

終わり

今のままだと、すでに確認する癖のついているものを列挙しただけで、俺がおもんないので、いろんな人にキーセンテンスを教えて欲しいです。ご協力お願いします。Tot ziens!

*1:本質です。一度別のことを考えないと、凝り固まった思考はそうそうリセットできません。

*2:\tilde{O}(X)というのは、ある定数kに対して、O(X(logX)^k)となることを言います

*3:半分全列挙って言葉ちょっと変で好き

*4:この問題がなんなのかはネタバレなので言いませんが、知りたければDMとかで聞いてください

*5:つまり問題の制約ではTLEするようなコードを書いて、小さいケースを眺めてみるということです


スポンサードリンク