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についてですが、これ…

Easy dp[i]:=時刻iにバスがつく確率、でdpを更新して期待値求めればいいです。 struct WaitingForBus { vector<int> time; vector<int> prob; int s; double dp[200110]; double whenWillBusArrive(vector<int> _time, vector<int> _prob, int _s) { time = _time, prob = _prob,</int></int></int></int>…

https://beta.atcoder.jp/contests/arc084/tasks/arc084_biからi+1に移動する際、cost 1で、i*10に移動する際cost 0と考えてiのmodKのグラフで最短経路長を求めればいいです。 と言われると簡単だけど絶対本番思いつかない。解説に01bfsとかいうのが載ってい…

https://beta.atcoder.jp/contests/arc084/tasks/arc084_c0-originでfloor((X+1)/2)-1番目を求める問題です。Xが十分大きければ、最初の文字は(K+1)/2になり、 Nを１つ減らした時の((X+1)/2)-1-(X%2)番目を求めればいいです。なので、X%2の累積分を考えると…

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

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16084Easy 原点と2つの頂点がつくる角度a,b,cについて、 a+b+c=2*π,a よって2つ頂点を決めれば最後の頂点は2*π-a-b 本当はx軸からの角度でsortして解くのが正しくて、そうすればO(N^2)になり…

https://szkopul.edu.pl/problemset/problem/yGC3v6-xidN3ZW6QNlBAFZSU/site/?key=statementL(i+1)^x * L(i)^yを求める際に必要な情報を考えてみます。これを(x,y)と表記します。 L(i+1)^x = (L(i) + L(i - 1) + 1) ^ x = Σ(a+b+c L(i+1)^x * L(i)^y = Σ(a+b…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2107頂点を行列にするとうまく行かなくて、辺を行列にするといい。すなわち ある辺のうちどっちにいるかを値にして、次どこ行けるのか行列で持てば良い。 最初の1回はどこにもいけるので特別な辺…

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16083Easy Kruskalやるだけなんだけど貼るの遅かった…もうちょっとちゃんと整備します。 struct ChristmasTreeDecoration { vector<int> col; vector<int> x; vector<int> y; int solve(vector<int> _col, vector<int> </int></int></int></int></int>…

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16081Easy まずブロックがないとわかっているところを除外します。 あっても良いブロックで連結成分が何個かできたとします。 この連結成分を同時に2個取ることはできません。また各連結成分…

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

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16080Easy わかんないカードをS,それと対戦するカードをTとすると、勝つ回数の期待値Eは加法定理を使って、 E=Σ(T[i]がSに勝つ確率)=Σ(T[i]>S[j]となるjの数)/|S|となります。よって１つあた…

https://community.topcoder.com/stat?c=round_overview&rd=16079Easy 累積和で前処理しておけばいいだけです。 struct ChocolateDividingEasy { vector<string> chocolate; int S[2510][2510]; int findBest(vector<string> _chocolate) { chocolate = _chocolate; int n = </string></string>…

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