http://codeforces.com/contest/909/problem/E全体的に問題文の把握に手間がかかっていますね…A はい。 B 親の顔より見た問題。一番重なっているところを累積和で求めます。 C 勘違いした… D 削除は奈良市計算量チャンスです。 E 問題を理解するのに無限に時…

https://beta.atcoder.jp/contests/arc068C はい。D 結局2枚捨てるという操作なので。E 解法2つあります。dの倍数のdを小さくすると、r - l 区間、つまりl区間の数は増えていきます。 これを利用する方法が1つです。もうひとつは区間(l,r)を二次元plotすると…

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

C はい。 D min(B, A * dist)で移動すればいいです。 E 普通にdpするとO(N^3)と見せかけてO(N^2logN)なので間に合います。速く書けてよかった。 void solve() { cin >> N >> A >> B >> C >> D; C_init(N + 50); dp[A][N] = 1; for(int i = A; i <= B; i++) {…

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://arc086.contest.atcoder.jp/C ノーコメントD 符号を全部揃えれば簡単です。E（部分点) 木dpしただけ。満点解法はマージテクらしいです。 int N; int P[MAX_N]; vector<int> G[MAX_N]; int dep[MAX_N]; ll dp[2010][2010][2]; void loop(int v, int d) { d</int>…

todoリストに載っていたので。 struct mergeUF { //O(logn^2) int n; vector<set<int>> g; vector<int> gat; void init(int mx) { n = mx; g.resize(n); gat.resize(n); rep(i, 0, n) { g[i].insert(i); gat[i] = i; } } mergeUF(int mx = 0) { init(mx); } void unite(int</int></set<int>…

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

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][…

Topcoderの環境をUbuntuで作ったので試してみました。昔のSRMだとあまり考察がなくて解きやすく、実装力をつけるのにもってこいですね。Easy 一周するとwidth-2, height-2の場合に帰着できて、あとはwidth==2or1の場合分けをやる。 struct SpiralRoute { int…