https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_fこれは簡単だった。どんなグラフになるかというと、連結成分を潰して1つの頂点と見れば直線になっています。 なので、dp[i][j][k]:=(i回目でまだとっていない点の数がj個、1を含…

https://agc007.contest.atcoder.jp/assignments期待値ってこんなこともできるのか…まずf(d1,d2,....d2n)を距離の間隔がそれぞれd1...d2nの時の期待値と定義します。 簡単な例でf(1,2,3,4,5,6)を取り上げます。 1手進めてみましょう。すると f(1,2,3,4,5,6)=…

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_eまずクッキーを食べる回数Tを固定します。これは40くらいまでやればいいです。クッキーを食べるまでA+si秒待ったとすると、 クッキーの総和はΠ(1 Σsiを固定してΠsiを最大化する…

https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasksにぶたんします。結局任意のi,jに対してS[i...i+M]とS[j...j+M]が高速に比較できればいいんですが、これはsuffix arrayでできます。suffix array知っていれば一瞬の問題なのかぁ。部分列…

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d最初の提出で3ケースだけWAだったのでオーバーフローとかどうでもいいミスでしょと思いましたが違いました… 同じ色内だったら1番小さいやつから辺を張ればいいです。 でも違う色だったら色の中で一番…

https://beta.atcoder.jp/contests/agc010/tasks/agc010_dやっぱこういうのは偶奇ですね…。操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecremen…

https://agc002.contest.atcoder.jp/tasks/agc002_d永続unionfindかぁと思ってたけど、想定解は並列二分探索というものらしいです。同じような二分探索を大量にしないと行けない時に、まとめてやる感じです。辺の数と点の数をswapしていて無限にバグらせた… …

https://agc001.contest.atcoder.jp/tasks/agc001_dこれ知識的には誰でも解けるけど結構思考しないといけなくて面白い。同じにならないといけない文字同士を結ぶグラフを考えると、直線+ループになる。これは各点の次数が2以下であることから示せる。 なので…

https://arc064.contest.atcoder.jp/tasks/arc064_df(l)=周期がちょうどlの条件を満たす数列の数とすると、f(l)=K^[(l+1)/2]-Σf(l/p)となって、求める値はΣ(lは奇数)f(l)*l+Σ(lは偶数)f(l)*(l/2)です。f(l)の式は高速メビウス変換の式に良く似ています。http…

https://colopl2018-final-open.contest.atcoder.jp/A オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。B スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。C 一次式にしてもよくわからなかったので分割統治でやった。これ解け…

https://beta.atcoder.jp/contests/agc020A A-Bの偶奇ですB 条件を満たすものは区間で表せるので端の値を持てばいいです。C 和をSとしてS/2以上で一番小さいものを選べばいいです。証明はSの部分列をA、B=S/Aとするとsum(A)=S/2となることからです。 bitのdp…

2017年重要なアルゴリズムはだいたい抑えられた。(特にflow)問題の解き方が少しわかってきた。(前まではひらめくまで途方に暮れていた)年末はコンテスト結構出れた。AtCoderのみだけど。2018年目標AtCoder Rate2600CodeForces Rate2200AtCoder精進(AGC,ARC)…