inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ アルゴリズム 例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。このようなときは、適当に上限を決めるとよいです。例えば上限を1000と決めて、その範囲に解が無ければ、上限を2倍にして再び解を求めます。この方法は多くの場合にかなり有効です。上限を決めると問題がぐっと易しくなることはよくあります。また、直接解を求めるより時間がかかりそうですが、致命的にはかかりません。例えば、O(N)の問題のとき、解が8000で、いきなり上限を8000にして解を求… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20111031%2Fp1" title="上限が不明なときの問題解決法 - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%5Cfrac%7Ba%5E%7Be%28n%2B2%29%7D%7D%7Bae%20-%201%7D%20%5Capprox%20%5Cfrac%7BM%5Eea%5E%7B2e%7D%7D%7Ba%5Ee%20-%201%7D Hatena Blog https://hatena.blog 2011-10-31 00:00:00 rich https://inamori.hateblo.jp/entry/20111031/p1 1.0 100%