DP

POI: Ploughing

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

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を量産しました。証明しながら解くことの重要性…

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

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

CF243E: Sereja and Sets

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

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 081E: Don't Be a Subsequence

https://beta.atcoder.jp/contests/arc081Typical DP Contest FGHIJ - omochan's diary これのGとほとんど同じで、dp復元がくっついただけ。 でも1-originで逆から見ていくのでかなりこんがらがった。普通に0-originのstringを参照するときに-1をつければい…

Typical Dp Contest PQRST

DP

http://tdpc.contest.atcoder.jp/PQRSは結構難しい(はず)。解いたやつから順番にあげていきます。 P 木dpするだけのO(NK^2)、と言ってしまえばおしまいだが木dpはバグらせがち。 最初点を主役にして、dpの遷移が意味不明になった。 dp[v][K]:=((vのsubtreeに…

Typical DP Contest KLMNO

DP

http://tdpc.contest.atcoder.jp/K O(NlogN)ということは問題が簡単な構造をしていますね?区間dpなど複雑なものを考えないでください。 segtreeを使ってできます。 std::findはO(logN)と思っていたのでTLE出た時びっくりした。 あと区間を使う順番に気を付け…

Typical DP Contest FGHIJ

DP

http://tdpc.contest.atcoder.jp/F 駅に一回も止まらない方法は1or0通りなので 駅に一回は止まる方法を求めれば良い。 区間和を含んだ式になるが、大体形は決まっているので、代わりにsという値で更新を行っている。 あとは場合分けをきちんとする。 int N, …

Typical DP Contest ABCDE

DP

http://tdpc.contest.atcoder.jp/assignmentsTypical DP Contestの問題が最近のCodeforcesでも出たということを聞いて埋めておこうと思った。20問あるので5問ずつに分けます。A 配列使いまわしもして十分高速だけど、boolのdpだとどっかで無駄に情報持ってな…

POJ 3411: Paid Roads

http://poj.org/problem?id=3411問題文をよく読みましょう。(a,b)は有向辺です。無向辺でやったあとを残しておきました。 ベルマンフォードっぽくbitDPをやればよい。 int N, M; int A[20], B[20], C[20], P[20], R[20]; int dp[1 << 11][11]; int main() { …

AtCoder Regular Contest 078F: Mole and Abandoned Mine

http://arc078.contest.atcoder.jp/tasks/arc078_d3^Nの形になるdpなんて初めて見た。まず使う辺に注目して、それらのコストの和を最大化する。 dp[S][v]:=(集合Sの点を使う際で0~v間でpathがただ一つ存在するための最大値)とする。遷移は二種類ある。 (1)pa…

POJいろいろ8/2

2441 http://poj.org/problem?id=2441bitdpやるだけしたら3938MS/4000MSで超ギリギリだったw3254 http://poj.org/problem?id=3254sampleも一発で通って気持ちがいい。bitdp。3420 http://poj.org/problem?id=3420行列累乗。一行ごとのstateをbitで表して行列…

Codeforces Round #419C: Karen and Supermarket

http://codeforces.com/contest/815/problem/C3乗っぽいけど2乗な木dp。 5000*5000*2のlong longの配列持ったらMLEした。 さらに初期化を適当にやりすぎてO(N^3)になってしまった。 直してAC。 int N, B; vector<int> G[MAX_N]; int dp[MAX_N][MAX_N][2]; int dp2</int>…

AtCoder Regular Contest 073F: Many Moves

http://arc073.contest.atcoder.jp/tasks/arc073_ddp高速化。dp[i][j]:=(i番目のqueryまで処理して、2点の座標がx[i]とjの時の最小値)とする。 するとdp[i][j]+jとdp[i][j]-jの値についてrange_sumとrange_minが出来れば高速に更新できる。2つsegtreeを持た…

AOJ 2415: Sashimi

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 monge(もんじゅ)dp。http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915 と http://sssslide.com/www.slideshare.net/ikumihide/ss-50881829 を参考にした。単調性が本質で、それを…

AtCoder Regular Contest 070D: No Need

DP

http://arc070.contest.atcoder.jp/tasks/arc070_bなんとなくの解法ならすぐわかったけど、それを詰めるのがつらかった。0~i-1の和をsum[i]と表す。aをsortしてai~aNの要素のうちいくつかを選んで和を作る。その内、Kを超えないもので最大の値をJとする。 す…

AOJ 2749: ぼくのかんがえたさいきょうのおふとん

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2749&lang=jp sortしてbit dp。 int N, M; int dp[(1 << 16) + 10][110]; int O[20]; int A[110]; void solve() { while(true) { cin >> N >> M; if(N == 0) break; rep(i, 0, N) cin >> O[i]; re…

AtCoder Regular Contest 074 E: RGB Sequence

DP

http://arc074.contest.atcoder.jp/tasks/arc074_cひたすらdp[i][j][k](i番目まで見たときRがj個あり、Gがk個ある場合の数)みたいな感じでやろうとしたけど、区間内にRGBがそれぞれ存在するかどうかだけわかればいいのでどう見ても情報を持ちすぎていた。 dp…