DP

ARC097

https://beta.atcoder.jp/contests/arc097/tasks思考法を自分の中で確立して初めてのコンテストだったんですがうまくいったので舞い上がってます。C グッと睨むと5文字ずつとってsortすれば良いことがわかる。 D グラフにすればわかる。 E 条件がO(N)個あっ…

Google Code Jam Round 1C 2018

DP

A dfsっぽくやって途中でexitすれば速いです。 B InteractiveっぽかったのでSkip C なんでこれ解けないのかなぁ…。dp[at][count]:=atまで見た時count個stackしたとする。その時の重さの最小値でO(N^2)で、実はcountまず謎貪欲を考えてしまったのが原因。最初…

ARC096

https://beta.atcoder.jp/contests/arc096C. Cを全通り試します。 ll A, B, C, X, Y; void solve() { cin >> A >> B >> C >> X >> Y; ll ans = linf; for(int c = 0; c <= max(X, Y) * 2; c += 2) { ll res = 0; res += C * c; res += A * max(X - c / 2, 0l…

CODE THANKS FESTIVAL 2017,F: Limited Xor Subset

DP

https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_fこういうの最近Codeforcesでも見た。とりあえずdpを書いてみます。 dp[i][a]:=要素iまで見た時xor sumがaになるものの場合の数。 これはO(NK)になってとても間…

精進4/11

DP

https://beta.atcoder.jp/contests/arc063/tasks/arc063_c 範囲求めて木の根から決めていけば良い。証明が少しあやふやで本番WAしたら自信無くして通せなさそう。 https://arc079.contest.atcoder.jp/tasks/arc079_d 丁寧丁寧丁寧にやったのでバグらせなかっ…

精進3/29

DP

https://beta.atcoder.jp/contests/arc060/tasks/arc060_d 最小項数は1or2orNで、1とNの時は簡単。2はKMP法でできる。 [https://beta.atcoder.jp/contests/agc013/tasks/agc013_d DPにするのが難しいタイプの問題はホント苦手。でもこれはとりあえずdp[i][at…

COLOCON -Colopl programming contest 2018- Final,E: キャプテン・タカハシ

https://colopl2018-final.contest.atcoder.jp/tasks/colopl2018_final_e rep(i, H + 1) rep(W, M) AS[i] += min(i, A[j]); 通した人の多くがこのようなコードを書いているわけですが、これだけ解説します。 Bがsource側、Aがsink側だとします。 Bのうちi辺…

3/25精進

DP

https://beta.atcoder.jp/contests/arc093/tasks/arc093_a 3点を見比べる。 https://beta.atcoder.jp/contests/arc093/tasks/arc093_b 一面黒に塗って白をその中にちまちま塗る。逆も同じ。 https://beta.atcoder.jp/contests/arc064/tasks/arc064_b えー結…

CODE FESTIVAL 2017 Final,H: Poor Penguin

DP

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_hお気持ちはわかるし、結構惜しいところまではいけるけど…氷山を消すと、4辺全てに氷山がある長方形領域に分断されることがわかります。なのでそれにしたがってDPすればいいです。といえば簡単…

CODE FESTIVAL 2016 Final,H: Tokaido

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_h面白いです。良問。まずM=1の時を考えて普通にdpすると、 f(j)=max(Ai-sum(j,i)-f(i+1)|i>=j)となります。ただしsum(j,i)=Σ(k=j...i-1)Akです。よくある添字を1つ減らすテクニ…

AGC016F: Games on DAG

DP

https://agc016.contest.atcoder.jp/tasks/agc016_fやっぱりできることとできないことの差がまだわからない…。1と2のgrundy数が一致しないようなグラフを数え上げればいいです。 全ての頂点についてgrundy数を決めてしまえば、グラフを数え上げるのは多項式…

AGC013E: Placing Squares

https://agc013.contest.atcoder.jp/tasks/agc013_e一応知ってるテクニックの組み合わせにはなるんだけど…難しいですね。Degwerさんの数え上げテクニック集で紹介されている問題です。とりあえず自明DPを考えると dp(x)=Σ(y=1...x)y^2dp(x-y)となります。こ…

AGC010F: Tree Game

https://agc010.contest.atcoder.jp/tasks/agc010_fO(N)で心配になった…。まずある頂点vに対して、隣接している全ての頂点piに対してA[v] なぜなら高橋君がvからどこに動かしても、青木くんがvに駒を戻せばいいです。そうすればA[v]がいずれ0となり高橋君は…

AGC009E: Eternal Average

https://agc009.contest.atcoder.jp/tasks/agc009_eまずK分木の葉に0や1を書き込んで、木の形状通りに平均を取っていく問題に言い換えます。するとK分木は葉が全て0の部分を除けば、縦1直線に繋げばいいことがわかります。 証明のアイディアとしては、葉が全…

AtCoder Grand Contest 009C: Division into Two

https://agc009.contest.atcoder.jp/tasks/agc009_c実家やるだけのはずなんですが通らないので後回しにします…。 int N; ll A, B; BIT bitx, bity; ll D[MAX_N]; const ll UB = 1e18; int cd(ll a) { return lower_bound(D, D + N, a) - D; } void solve() {…

AtCoder Petrozavodsk Contest 001F: XOR Tree

DP

https://apc001.contest.atcoder.jp/tasks/apc001_f 最近同じような問題を解いたのでわかったんですけども、O(3^N)DPをバグらせて悲しくなりました…。頂点に隣接しているすべての辺のXORを書き込みます。すると、2つの頂点についてある値XでのXORを行い、す…

AtCoder Grand Contest 012E: Camel and Oases

https://agc012.contest.atcoder.jp/tasks/agc012_eアイディア自体はすんなりいけたけどいろいろ勘違い+バグで無限に時間がかかった…。とり方を見てみると、容量Vでジャンプしないで取るオアシスの区間,V/2で取る区間、(V/2)/2で取る区間…があって、それぞれ…

DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦,D: シャツの部屋

DP

https://ddcc2016-final.contest.atcoder.jp/tasks/ddcc_2016_final_dこれは本当に良問だと思います。まずi-1回洗濯するとすると、i+k回洗濯すると破れる服は全部i回とみなせます。 Mが小さければdp[i][j]:=i回洗濯する服まで見てj日シャツを着られる方法で…

CODE FESTIVAL 2016 Grand Final,E: Water Distribution

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_e初手が難しい…。グラフの水の容量がB,水をやり取りする辺の距離の合計をA,都市の数をKとすると、なんと最大値は(B-A)/Kであることが証明できます。 Aは都市K個の最小全…

CODE FESTIVAL 2017 Final,G: Mancala

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_g答えは(f(a)の期待値)*(K+1)^Nなのでf(a)の期待値を求めることにします。まず最小値を達成する操作とはどのようなものなのか考えます。 i番目の値Aiについて最初からAi>iであれば何も操作を行…

AOJ2405: 姉妹港

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405解法をyosupoさんのブログとか見て理解したのでメモしておきます。とりあえずどっかで多角形を切り開いて区間の問題にします。 普通に考えるとO(N^2)のDPになって、更新式は [l r]に区間が張…

CODE FESTIVAL 2017 Exhibition,A: Awkward

https://cf17-exhibition-open.contest.atcoder.jp/tasks/cf17_exhibition_a包除原理してpathを何本含むかでdpすれば良いということはわかりました。 ただ自信がなく解法見てやっぱり合ってたってなりました。 これ絶対debug時間かかるやつだと思いましたが…

CODE FESTIVAL 2017 Elimination Tournament Round 3,F: Unicyclic Graph Counting

DP

https://cf17-tournament-round3-open.contest.atcoder.jp/submissions/2045180こんなのサイクルが1つあるだけのグラフ以外に考察の余地無いだろで、DPに行けたのは良かったです。dp[i][j][k]:=i番目まで見て、j点サイクルに使って、サイクルの次数がkの時…

CODE FESTIVAL 2016 Grand Final,F: Intervals

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_fまず真ん中の区間を動かさないで最小を達成する方法があることが示せます。 なので右左にそれぞれN/2個の区間を割り振ればいいです。 そして貪欲が厳しそうだと思える…

CODE FESTIVAL 2016 Final,F: Road of the King

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

ARC064F: Rotated Palindromes

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…

COLOCON -Colopl programming contest 2018- Final

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

AGC020

DP

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

ARC088

https://beta.atcoder.jp/contests/arc088C A*2^nD 結構詰まった人もいるっぽい。端は好き勝手変えられるので真ん中だけ考えればいいです。AtCoder Regular Contest 080F: Prime Flip - omochan's diaryのように区間→2点更新の問題に言い換えられますが、今…

ARC083

https://arc083.contest.atcoder.jp/C 全通り試しましょうD とりあえず全部辺を張ってみて矛盾がないかワーシャルフロイド確かめましょう。矛盾があったら-1を返します。 もし矛盾がなかったら、頂点u,v,kについてdist(u,v)=dist(u,k)+dist(k,v)となっている…