http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d45度回転をするとマンハッタン距離|x1-x2|+|y1-y2|がチェビシェフ距離max(|x1-x2|,|y1-y2|)に言い換えられて見通しが良くなります。 45度回転したGrid上でD*Dの正方形…

周期的なものの数え上げの時に役立ちそう。蟻本の周期的でない文字列の数え上げを考えましょう。 周期1,2,3,4,...みたいな感じでNの約数をすべて列挙して包除原理をすれば求まりますが、約数は100コとか200コになる可能性があるのでこれでは間に合いません。…

包除原理で活躍する二つのアルゴリズムです。この2つの記事がわかりやすかったです。 高速メビウス変換について - 篠突く雨の日記 ゼータ変換とメビウス変換 - pekempeyのブログメビウス:∩→∪ ゼータ :∪→∩と覚えればいいです。たぶんメビウスの方がよく使うと…

http://omochan.hatenablog.com/entry/2017/07/15/181512この問題で師匠のコードを見ていたら、Sparse Tableっぽいの使っているなあと思ったので僕も実装してみました。 vcost[v][k]:vから2^k個先の親までのpathで一番小さい辺のcostとすると、ダブリングと…

http://codeforces.com/contest/843/problem/C重心を根としてウニみたいなグラフを構成します。具体的な方法は http://kmjp.hatenablog.jp/entry/2017/09/05/0900 ここに書いてあります。 重心が複数個あるときもほとんど同じです。(複数といっても高々2つな…

http://codeforces.com/contest/863/problem/Fフローと言われちゃえばねぇ…。まず配列の各iについてA[i]以上B[i]以下ではならないという条件を求める。B[i] それからはフローで値を求めるのだが、区間N個にN * 2 + j(0 N * 2 + jからA[i] そうすると、xにk流…

http://codeforces.com/contest/425/problem/Eずっと前に解けなかった問題。ひさしぶりに見たらそんな難しくなかった。余分における区間の特性を考えよう。 区間スケジューリング問題の要領で、区間のうちとれるものの中で右側の座標が一番小さいものをとっ…

http://codeforces.com/contest/860/problem/EHL分解やるだけで通ってしまった… depthの浅い頂点から順番に見ていき、根まで+1をする更新を行うことで求められます。segtreeでやったら遅かったのでbitにして1824ms/2000msでAC。 struct BIT { //0-origin!!! …

http://codeforces.com/contest/860/problem/D解いたあとだとめっちゃ自明に見えるけどかなり苦労した。dfs木を作った後、2辺ずつ木の下からとっていく。 ある点vを中間の点としたpathがとれるときはとる。 取れない場合はvの親pに向かう辺(v,p)を残す。 そ…

http://agc019.contest.atcoder.jp/tasks/agc019_eaをS[i]=T[i]=1が成立している数 bをS[i]=1,T[i]=0が成立している数 cをS[i]=T[i]=1を満たす異なる二つのiについてswapを行った回数 としてdpを行う。 b=N-i-a+cが成立するので、O(N^3)で求められます。 1の…

http://arc077.contest.atcoder.jp/tasks/arc077_d実験的にやるのがたぶん正攻法だけど、もうちょっと文字列の周期のこととかに気を配れるとよかった。解説にも書いてありますが、g(n+2)=g(n+1)+g(n)になります。これは実験をすると比較的簡単に気づけます。…

http://agc019.contest.atcoder.jp/tasks/agc019_dなんとなくの解法はわかるけど詰めるのが結構難しいと思う。Sをiだけ右にshiftした場所でTと一致させることを考える。 移動したSとTを比較したとき、Si == 1 && Ti == 0のとき、その場でSiを0に反転させるこ…

最初に これいる?要はmergeとかsplitとかできるようになった強い配列です。ここらへんを参考にして実装しました。 https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf http://algoogle.hadrori.jp/algorithm/prbtree.html h…

(P||Q||...)&(R||S||...)みたいな連言標準形で書かれた論理式を真にする割り当てはあるかを判定する問題をSATといいます。 2-SATの場合カッコ内のリテラル数が高々2つ、つまり(P||Q)&(R||S)みたいになってます。2-SATの解き方は蟻本の通り、SCCを使って真のn…

Euler Tourは木を直線にして扱いやすくするテクニックです。 これを使うとLCA、二点間のpathの長さがO(logN)で求められます。でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。 HL分解は実装が重い…

永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。 単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。 普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量…

http://agc017.contest.atcoder.jp/tasks/agc017_c解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。 僕はこう考えたらしっくりきました。まず魔法をかける前、ボールがどうなって…

http://agc017.contest.atcoder.jp/tasks/agc017_d(ある点vのsubtree)と(vから親pへ向かう辺)で構成されるグラフについてgrundyが求まれば、あとはXORをとれば、pのsubtreeに対してgrundy(p)が求まります。grundy(v)は再帰的に求まるとして、このグラフにvか…

grundy数について勉強したのでお話します。grundy数はご存知の通り、ゲームの勝敗を求める際に使う数なのですが、こんな感じの性質があると思います。1.grundy数は非負整数であり、grundy数=0ならば負け、grundy数>=1ならば勝ちを意味する。 2.grundy数=kの…

http://poj.org/problem?id=3690蟻本に書いてあるように二次元hashをすればいいです。hashといえばこの記事 http://hos.ac/blog/#blog0003 が有名ですが、ここに書いてあるように3つのmodでhashをとるようにしてみました。注意：TLE解法です。 struct ll3 { …

SA+LCP+RMQで任意の2つのsuffixの組について先頭何文字が一致しているかをlog(N)で求めることができる。 前処理も全部O(N)でやることもでき、高速。(下のコードはRMQの前処理がO(NlogN)だが)HL分解した木に乗せることを考えながらライブラリ化した。 struct …