DP

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)となっている…

ARC087

https://arc087.contest.atcoder.jp/C はい。 D XY独立にできます。 E 本質っぽいgrundyのところまではわかったけどtrie木で敗北しました。 まずstringを2分木に対応させます。そうするといろいろな高さの2分木から頂点を取るゲームになります。 高さがdの2…

Codeforces Round #450(Div. 2)

http://codeforces.com/contest/900A はい。 B 解けなかったです。(絶望) でもこれまあまあ難しい気がするんだけどどうなんだろう。a*10^k/bの1の位を求めたいとします。以下の文字(a,b,c,d,e,f)はすべて整数です。a*10^k/b=e+d/b(d a*10^(k+1)/b=10*e+d*10/…

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