DP

COLOCON -Colopl programming contest 2018

https://colopl2018-qual.contest.atcoder.jp/久しぶりの投稿です。いろいろ忙しかった。 やっぱりコンテストだと結構焦ってまともに考えられないなぁ。C 偶数は一緒に使えないので、すべて奇数or奇数+偶数1つという組み合わせしかありません。 あと、35以上…

AOJ 1169: The Most Powerful Spell

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1169dp[i][j]:=j番目のnodeについた時、文字列の長さがiのもののうち辞書列最小のもの を更新していきます。i最小の呪文が決まるときは辞書列最小文字列の長さN*6以下になりますが、決まらないと…

Codeforces Round #438F: Yet Another Minimization Problem

http://codeforces.com/problemset/problem/868/F良問of良問だと思う。まず簡単なdpから考えて、dp(i,j):=j番目までの数列をiコに分割した時の最小コスト、と定義すれば dp(i,j)=min(dp(i-1,j')+cost(j',j1))でできます。この時dp(i,j)が最小値となるj'をp(j…

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest,D: Packmen Strike Back

http://codeforces.com/problemset/problem/883/Dこれは考察系のDP。場合分けでtrivialな場合は別で処理します。非自明(Pが2つ以上ある)の時、まず二分探索して、距離Kすすめるとき*をすべて覆えるか?という問題を解くことを考えます。dp(i):=i番目のPを使っ…

CODE FESTIVAL 2017 qual C,F: Three Gluttons

https://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_f解説と完全に同じことしたけどそれでも結構バグらせた。頑張って問題を変形していくと、解説の2つめの四角で囲ってあるような問題に落とし込めます。 ここからが難し…

AtCoder Regular Contest 085F: NRE

https://beta.atcoder.jp/contests/arc085/tasks/arc085_d配るDPともらうDPでわけわかんなくなってしまった…。 配るDPは操作を考えて、1手進めるとどこに遷移するかを考えるのが基本となります。 対して、もらうDPは漸化式を立ててからメモ化再帰に持ってい…

Codeforces Bubble Cup X - Finals,E: Casinos and travel

http://codeforces.com/problemset/problem/852/E初全方位木DPです。観察するとGood Moodになる方法とBad Moodになる方法は同じ数だけあります。なのでGood Moodのみ考えれば良くて、 全方位木DPをすれば簡単に求められます。全方位木DPについてですが、これ…

AtCoder Regular Contest 084F: XorShift

https://beta.atcoder.jp/contests/arc084/tasks/arc084_dbitの扱いもうちょっとわかってたらもうちょっと早く思いついたかな。すべての数がある数Pによって構成できることが証明できます。これときPはgcdに他なりません。 なのでgcdをユークリッドの互除法…

SRM 639

DP

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16082Easy なんも難しいことないのに題意勘違いして無限に時間溶かした。さらにオーバーフローもするしいいことなし。 struct AliceGame { long long x; long long y; long long findMinimumV…

数え上げDPについて

まずこの問題を考えてみましょう。 文字列S,Tが与えられる。最長共通部分列の長さを求めよ。これは蟻本にあるようにdp[i][j]:=Sのi字目とTのj字目までの最長共通部分列の長さとすれば良くて dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) (S[i]!=T[j]) dp[i][…

AtCoder Regular Contest 070E: NarrowRectangles

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

Codeforces Round #441E: Delivery Club

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

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…