はむこの勉強記録

http://bit.ly/2ktf20t の写し

「これがわからなかったから解けなかった…」みたいな情報まとめ(Topcoder SRM Easy 600番台)

Topcoder SRM Easyを100ACしたので、Topcoder SRM 600番台で勉強したことをまとめます。

僕の解説リストから、特に勉強したこと、新しい発想方法だけ抽出します。 docs.google.com

目次

二分探索と全探索の順序は、全探索→二分探索のほうが枝刈りできて速い

これはめっちゃ良い知識。

二分探索内(0からnまで)に全探索(0からsまで)をしないと判定できない問題があるとする。
普通に二分探索内全探索するとO(s log n)だが、枝刈り+全探索内二分探索ではO(s + log s log n)になる。

docs.google.com

成り立たないってことは…つまりどういうことだってばよ…

成り立たせようと躍起になるのではなく、成り立たない場合を考えたら正当性が生えた。

docs.google.com

集合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ずつシミュレーションしていく感じ。

docs.google.com

「事前に分からない」場合分け

答えに対して場合分けの条件が課されている場合がある。
事前にチェックできないので、それぞれの問題を解いて、その和集合を取ると良さそう。

docs.google.com

その変数、探索する必要ありますか

何も考えないと、全探索の変数をいっぱい作りたくなるが、間に合わない場合にどうするか?
もしある変数の最適値を、他の変数から生成できるならば、ループが一つ減るのでうれしい。

docs.google.com

整数計画に落とすしてもあまり意味ないので、sumなどを使ってうまく緩和する

整数計画に落とすと、何となく一仕事した感に包まれますが、それは罠で、NP困難です。
sumを全探索するなど、ここから問題に応じたひと工夫が必要。

docs.google.com

おいおい、辺を忘れてもらっちゃ困るぜ

頂点ばっかり考えて、辺を忘れがちです。

docs.google.com

Codeforces 395 D1Aもこれで解けなかった。

docs.google.com

可逆な状態変化とDFS

超大きい状態を、木の頂点に載せたい場合のテク。
木を上下するときに、グローバルメモリを副作用で更新したり戻したりする。

docs.google.com

これでも使った。

docs.google.com

制限付きDPでは、制限ベースに一個ずつ殺していく

再帰的にダブり無く網羅するのはたいへん。

docs.google.com

範囲素因数分解はけっこう速い

範囲1000万に対して構築含めて1秒くらいで終わる。びっくり。
エラトステネスみたいに、ぴょんぴょん飛ぶ更新をしてるからっぽい。

docs.google.com

DAGの考察は横一列にならべて、トポロジカルソート的に

docs.google.com

ハミルトン路(全頂点一筆書き)は閉路だろうがなんだろうがNP完全

典型的な難しい問題がわからないとダメな気がするなあ。
「この条件がないとNP完全になってポ」とか、「この情報を落としたらNP完全になるので、重要な情報はどこにある」とか考えられそう。

docs.google.com

木の中心と半径の全探索

任意に頂点を2つ取ることに代えられる。これ結構便利っぽい。

docs.google.com

やりとりが発生しない場所はあるか

円状だと、ループしちゃ行けない場合にどこかで情報のやりとりが無い場所が生まれがち。
これを全探索するという手がある。

docs.google.com

Topcoder SRM 683 D1E MoveStonesもそうだった。

docs.google.com

確率DP

全状態に確率を定義する。配るDPと相性がよい。

docs.google.com

一次元点群との距離の和が最小な位置は?

それは中央値です。

docs.google.com

codeforces educational 16 Bでそのまんま出ましたね。

docs.google.com

目的が階段

始めから1,2,3,…を減らしておく

docs.google.com

上書きは後ろから塗りはがす

後ろから塗りはがしていくと「塗り剥がしたところはどうでもいい」となる。全部をどうでもよくなあれ。

docs.google.com

トポソされた木の配る再帰再帰不要

docs.google.com

どうでもいいこと

二次元閉区間[(x, y), (z, w)]の面積は間違えがち

小学生でもわかります。(z-x+1) * (w-y+1)ですね。

docs.google.com

nまでの素数構築はやめて

考察や実装をミスるとn=109とかでは、TLEします。定数で構築して。

docs.google.com

任意の整数はフィボナッチ数列で表せる

へー。

docs.google.com

文字列のfindは面倒

頭がこんがらがりコンドルなので使わない。

docs.google.com

木はどこから見ても木

無向な木は、どの頂点を根付き木にすることができます(当たりまえ)。

docs.google.com