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

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

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

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

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

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

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

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

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…

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

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

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

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

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

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…

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

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

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

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

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

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

まずこの問題を考えてみましょう。 文字列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][…

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

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

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

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d結局10111111...または111111...101となる文字列を見つける問題になるんですが、言い換えが甘くて場合分けをミスり、WAを量産しました。証明しながら解くことの重要性…

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