二分探索
欲しい値の取りうる範囲が大きい場合、それをlog(n)で出せる方法。

欲しい値がちょうど条件の境界線にある場合に有効。

ex.最大の中の最小値,条件を満たす中での最大値

そのようなケースは数列の単調増加(減少)がある場合に見られる。数列ではなく、実数上でも有効

木

木の直径を求め、そこから最大の閉路を求める。

木の直径は以下の手順で求める。

1.任意の頂点から一番深い頂点をdfsで求める。それをuとする。

2.uからもう一度dfsし、uから一番深い頂点をvとする。

3.uからvまでのパスが木の直径

ナップサック問題

各状態の個数を持っておきDP

この場合は{“a”,“at”,“atc”,…}のように文字をpushした時点での状態（個数）を保持

UnionFind

赤マスの連結状態をチェック

グリッド上での操作をグラフとしてみる。

たどり着ける＝＞２端点は同じ連結成分

木

どの頂点も隣り合わない＝＞二部グラフ

二部グラフを生成し、N/2より多いグループの頂点をN/2個出力

二部グラフの特徴は奇数閉路を持たないこと。

木は二部グラフ

imos法

+….-..
……..
……..
-….+..

左から右への累積のあと、上から下への累積

尺取法

実装詰まりがち

とりあえず、半開区間を[l,r)として定義し、lをfor文で回しながらrをできるだけ右に持っていくような実装にする。

メモ化再帰orDP

DPだとO(k^2)になると勘違いしてた。

単純にBFSでやるとまずい

例えば、vからuへの経路でくねくねしてる短い道と真っ直ぐの多い遠回りな道の２つがあるとする。

頂点を一度しか調べない単純なbfsをした場合、uに先にたどり着くのは前者の経路であるが、実際は後者が最適経路。

ダイクストラ法を用いる。

priority_queueで方向転換回数が少ないものを優先的に取り出す。

前述の例だと遠回りでも後者が先にuにたどり着いて最小コストを記録できる。

拡張BFSでデータの持ち方を工夫しても出来るらしい。

この場合、各頂点にどちらの方向を向いてるかの状態を保持させるといい。

グリッド上での探索問題は様々なケースを考慮した上で最適なアルゴリズムやデータの持ち方を選択することが重要

ボタンを2^x回押した時の今表示されている数字の遷移先を考える。2^x回の遷移先は2^(x-1)の遷移を２回行ったものであることがポイント。

この情報はx<=60まで見て記録すればいい。

あとは、Kの立っているbitに応じて2^x回押した時の遷移先を参照していけば、最終的にK回押した時の数字の遷移になるはず

同じ処理を10^18回ほど繰り返す問題は大体bitごとに考えるのがいい気がする。

もしくは、二倍ずつや半分ずつにするような反復処理を考えて、その中に何か法則性がないかを模索するのが良い。

Kがとんでもなくでかい数字だったら通用しない

想定解答は周期性を見つけるとのこと

bit全探索

明らかにHが少ないことに気づけば解ける。

全探索のうちの１つに着目して、問題を簡略化する。

この場合、同じ数字で構成された列の個数のうち、一番多かった列の個数を求める。

x,yは独立に考えることが出来る。

マンハッタン距離の総和が最小となる点は中央値

すべての経路を再現する。バックトラック

再帰関数を用いる。

関数に潜る前にvisitedをtrueに、帰ってきたらfalseにする。

visited[{ny,nx}]=true;

dfs({ny,nx},visited);

visited[{ny,nx}]=false;

約数の個数を記録

その中でfor文を回す。

約数の個数が少ないことに気づけるかどうか

例2^32=>33個、10^12=>13*13=169個