「これがわからなかったから解けなかった…」みたいな情報まとめ(Topcoder SRM Easy 600番台)
Topcoder SRM Easyを100ACしたので、Topcoder SRM 600番台で勉強したことをまとめます。
僕の解説リストから、特に勉強したこと、新しい発想方法だけ抽出します。 docs.google.com
目次
- 目次
- 二分探索と全探索の順序は、全探索→二分探索のほうが枝刈りできて速い
- 成り立たないってことは…つまりどういうことだってばよ…
- DP書こうとしたらこれループするんですけど
- 「事前に分からない」場合分け
- その変数、探索する必要ありますか
- 整数計画に落とすしてもあまり意味ないので、sumなどを使ってうまく緩和する
- おいおい、辺を忘れてもらっちゃ困るぜ
- 可逆な状態変化とDFS
- 制限付きDPでは、制限ベースに一個ずつ殺していく
- 範囲素因数分解はけっこう速い
- DAGの考察は横一列にならべて、トポロジカルソート的に
- ハミルトン路(全頂点一筆書き)は閉路だろうがなんだろうがNP完全
- 木の中心と半径の全探索
- やりとりが発生しない場所はあるか
- 確率DP
- 一次元点群との距離の和が最小な位置は?
- 目的が階段
- 上書きは後ろから塗りはがす
- トポソされた木の配る再帰は再帰不要
- どうでもいいこと
二分探索と全探索の順序は、全探索→二分探索のほうが枝刈りできて速い
これはめっちゃ良い知識。
二分探索内(0からnまで)に全探索(0からsまで)をしないと判定できない問題があるとする。
普通に二分探索内全探索するとO(s log n)だが、枝刈り+全探索内二分探索ではO(s + log s log n)になる。
成り立たないってことは…つまりどういうことだってばよ…
成り立たせようと躍起になるのではなく、成り立たない場合を考えたら正当性が生えた。
集合A, Bが与えられる。集合Sに対して、LCM(S)={lcm(T) | T⊂S}と定義する。LCM(A)=LCM(B)か。
LCM(A) != LCM(B)⇒BにあるけどAからは構築できないみたいなlcmが存在する⇔あるb in Bが、Aからは構築できない
対偶を取る
全てのb in BがAから構築できる⇒LCM(A)=LCM(B)
DP書こうとしたらこれループするんですけど
それはDPではありません(DAGではないので)。ダイクストラかBFSです。
そういうのをDPで書くと、頂点回数再計算が必要になるので計算量が二乗になります。
ダイクストラに関しては、
- まずダイクストラは、事前にグラフを構築しなくとも、各状態に対して遷移を実装できる
- ダイクストラもBFS的で、一つ見つければいいだけなら、始めに見つかったやつが答えになる(関数内returnしてよい)
- usedフラグは要らない。dist = INFだけでOK
- priority_queueには、同じ頂点が複数回含まれる可能性がある。
BFSって重みなしグラフじゃないと使えないんじゃないの?
-> 01-BFSなるものを使うと、整数重みW以下でO(V)を担保できる(ソースコード)。
やっていることは、時間ステップ1ずつシミュレーションしていく感じ。
「事前に分からない」場合分け
答えに対して場合分けの条件が課されている場合がある。
事前にチェックできないので、それぞれの問題を解いて、その和集合を取ると良さそう。
その変数、探索する必要ありますか
何も考えないと、全探索の変数をいっぱい作りたくなるが、間に合わない場合にどうするか?
もしある変数の最適値を、他の変数から生成できるならば、ループが一つ減るのでうれしい。
整数計画に落とすしてもあまり意味ないので、sumなどを使ってうまく緩和する
整数計画に落とすと、何となく一仕事した感に包まれますが、それは罠で、NP困難です。
sumを全探索するなど、ここから問題に応じたひと工夫が必要。
おいおい、辺を忘れてもらっちゃ困るぜ
頂点ばっかり考えて、辺を忘れがちです。
Codeforces 395 D1Aもこれで解けなかった。
可逆な状態変化とDFS
超大きい状態を、木の頂点に載せたい場合のテク。
木を上下するときに、グローバルメモリを副作用で更新したり戻したりする。
これでも使った。
制限付きDPでは、制限ベースに一個ずつ殺していく
再帰的にダブり無く網羅するのはたいへん。
範囲素因数分解はけっこう速い
範囲1000万に対して構築含めて1秒くらいで終わる。びっくり。
エラトステネスみたいに、ぴょんぴょん飛ぶ更新をしてるからっぽい。
DAGの考察は横一列にならべて、トポロジカルソート的に
ハミルトン路(全頂点一筆書き)は閉路だろうがなんだろうがNP完全
典型的な難しい問題がわからないとダメな気がするなあ。
「この条件がないとNP完全になってポ」とか、「この情報を落としたらNP完全になるので、重要な情報はどこにある」とか考えられそう。
木の中心と半径の全探索
任意に頂点を2つ取ることに代えられる。これ結構便利っぽい。
やりとりが発生しない場所はあるか
円状だと、ループしちゃ行けない場合にどこかで情報のやりとりが無い場所が生まれがち。
これを全探索するという手がある。
Topcoder SRM 683 D1E MoveStonesもそうだった。
確率DP
全状態に確率を定義する。配るDPと相性がよい。
一次元点群との距離の和が最小な位置は?
それは中央値です。
codeforces educational 16 Bでそのまんま出ましたね。
目的が階段
始めから1,2,3,…を減らしておく
上書きは後ろから塗りはがす
後ろから塗りはがしていくと「塗り剥がしたところはどうでもいい」となる。全部をどうでもよくなあれ。
トポソされた木の配る再帰は再帰不要
どうでもいいこと
二次元閉区間[(x, y), (z, w)]の面積は間違えがち
小学生でもわかります。ですね。
nまでの素数構築はやめて
考察や実装をミスるとn=109とかでは、TLEします。定数で構築して。
任意の整数はフィボナッチ数列で表せる
へー。
文字列のfindは面倒
頭がこんがらがりコンドルなので使わない。
木はどこから見ても木
無向な木は、どの頂点を根付き木にすることができます(当たりまえ)。