POI: Ploughing

https://szkopul.edu.pl/problemset/problem/6YiP6JA5U15hY94pLwuHoYPg/site/?key=statement実践的アルゴリズム貪欲編です。少し観察すると(列をstripする回数==M)または(行をstripする回数==N)が成立することがわかります。 対称なので(列をstripする回数==…

POJ 1284: Primitive Roots

http://poj.org/problem?id=1284答えはφ(p-1)個になります。証明しましょう。準備.n(|p-1)についてx^n≡1(modp)はちょうどn個の解を持つ。証明.p-1=nkとしたとき、 x^(p-1)-1=(x^n-1)(x^(n(k-1))+x^(n(k-1)-1)+...+1)であり、 x^(p-1)-1≡0(modp)の解はp-1=nk…

POJ 2115: C Looooopsなど

POJ 2115: http://poj.org/problem?id=2115A+Cx=B+(2^K)yの解(x,y)のうちxが非負で最小のものを求めればよい。これはユークリッドの互除法やるだけで求められるが、少し遠回りに書いたらREを起こしてえぇ…ってなりました。たぶんオーバーフロー起こしてまし…

POJ 1150: The Last Non-zero Digit

http://poj.org/submit?problem_id=1150初中国剰余定理かもしれない。 (X/10^k)mod10を求めればいいです。ここでkはXが10で割り切れる回数です。 中国剰余定理より (X/10^k)mod10 (X/10^k)mod2, (X/10^k)mod5となります。 対称性よりmod5についてのみ注目し…

CODE FESTIVAL 2017 qual B,E: Popping Balls

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_e赤のボールがA,青のボールがB個の状態から選ぶ方法の数を再帰的に求めます。これを(A, B)と定義しておきましょう。 赤を選ぶ場合単に(A-1,B)とすればいいです。青を選…

CODE FESTIVAL 2017 qual B,D: 101 to 010

DP

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d結局10111111...または111111...101となる文字列を見つける問題になるんですが、言い換えが甘くて場合分けをミスり、WAを量産しました。証明しながら解くことの重要性…

CODE FESTIVAL 2017 qual A,E: Modern Painting

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_eまず最初に縦の向きに人を動かすとします。すると領域は二つに分断されます。そのうち一つについて横に進む人がX人、上から下に進む人がY人、下から上に進む人がZ人だ…

天下一プログラマーコンテスト2016予選A,D: グラフィカルグラフ

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_d構築ゲー。まずゆるーく考えると適当な頂点を根にして辺の長さを2^n,2^(n-1)...としていけば作れることがわかる。 あとはこれを座標圧縮でキツくすればよい。構築ゲーで大事なのはお…

天下一プログラマーコンテスト2013 決勝D: 天下一ボディービルコンテスト

http://tenka1-2013-final.contest.atcoder.jp/tasks/tenka1_2013_final_d包除原理の良問です。目標を達成しないスケジュールを考えます。それはどれかの筋肉が目標を達成しなければいいです。 なのでS:=目標を達成しない筋肉の集合、f(S):=Sについて何通り…

AOJ 2427: ほそながいところ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2427全探索といえばこの問題だよね。最初を除いたどの馬車も最小値をとりうる場合、次のうち二つの条件のうちどちらかを満たします。 1.終点or少し広いところで交わるほかの馬車が存在する。 2.1…

Manthan, Codefest 17F: Nagini

http://codeforces.com/contest/855/problem/F平方分割強い(確信)平方分割してブロックでまとめて解く。 もしブロック内に0が存在したら普通に更新。 0がなかったら反対側を見て、0ではない値をとるようだったら配列に値を入れてsortする。 ブロックの更新が…

CODE FESTIVAL 2017 qual A,D: Four Coloring

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のブログメビウス:∩→∪ ゼータ :∪→∩と覚えればいいです。たぶんメビウスの方がよく使うと…

LCA Doubling + Sparse Table(?)

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

CF AIM Tech Round4C: Upgrading Tree

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

ECR029F: Almost Permutation

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流…

CF243E: Sereja and Sets

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

CF434E: Arkady and a Nobody-men

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

CF434D: Wizard's Tour

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

Atcoder Grand Contest 019E: Shuffle and Swap (部分点)

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の…

AtCoder Regular Contest 077F: SS

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

AtCoder Grand Contest 019D: Shift and Flip

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…

2-SAT

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

Euler Tour

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

永続segtree

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

AGC017C: Snuke and Spells

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

AGC017D: Game on Tree

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

grundy数

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