http://arc070.contest.atcoder.jp/tasks/arc070_c関数dpとかいうやつ。僕のいうところの「愚直に値を持つ」dpと同じです。 愚直にx座標すべて持ってみることを考えて、実は本当に持つ必要があるものは少なくて、更新も簡単にできる、みたいな感じです。 |x-…

https://www.ioi-jp.org/camp/2012/2012-sp-tasks/setを使う問題といえばコレ。直方体の体積を断面図を考えて求めていく問題です。こういう問題でsetを使う際、 (1)番兵を使うと便利。 (2)lb,ubを覚えてまとめてerase(lb,ub)する。 (3)ある要素を見つけてそ…

http://codeforces.com/contest/875/problem/Eならし計算決めるアレです。 とりあえず距離kのとき行けるかどうかを判定する。 setでi番目まで処理し終わったとき、もう一人がどこにいるかを管理する。 i+1番目を考えて、もう一人の候補の座標としてありうる…

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_fhttp://omochan.hatenablog.com/entry/2017/10/20/004232の続きです。普通に蟻本通りにやればいいだけでした…。 x≡k(modm) x≡k'(modm')を満たすxは x=mt+kとして mt≡k'-k(modm')をtについて解けば…

http://codeforces.com/contest/875/problem/Fprinceを点、princessの二人のprinceの候補を辺とみます。それからkruskalっぽいことをします。具体的には 1.違う連結成分どおしで、二つともlockedじゃなければ繋ぐ。 2.同じ連結成分どおしで、lockedじゃなけ…

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_fある十分大きいx(A A^A^A^A...を考えるとKのmodφ(M)とmodMの値が求められるので、あとはユークリッドの互除法をして解を構成すればよい…なんですが、値がでかくなりすぎてWA…どうやって小さくする…

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

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

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についてのみ注目し…

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

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

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

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

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

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

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

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…