Codeforces Round #450(Div. 2)

A はい。 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/bとなり、d*10/bの1の位がcと一致す…

ARC086

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) { dep[d]++; rep(i, 0, sz(G[v])) { int</int>…

マージテクUF

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

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

SRM 642

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

AtCoder Regular Contest 084D: Small Multiple

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

AtCoder Regular Contest 084E: Finite Encyclopedia of Integer Sequences

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

AtCoder Regular Contest 084F: XorShift

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

SRM 641

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)になり…

SZKOpuł: Leonardo's Numbers

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…

AOJ 2107: Can I go there?

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

SRM 640

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

SRM 638

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

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…

SRM 637

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|となります。よって1つあた…

SRM 636

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

数え上げ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][…

SRM 371

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

AtCoder Regular Contest 070E: NarrowRectangles

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

JOI2012春day1-2: 魚

https://www.ioi-jp.org/camp/2012/2012-sp-tasks/setを使う問題といえばコレ。直方体の体積を断面図を考えて求めていく問題です。こういう問題でsetを使う際、 (1)番兵を使うと便利。 (2)lb,ubを覚えてまとめてerase(lb,ub)する。 (3)ある要素を見つけてそ…

Codeforces Round #441E: Delivery Club

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

Tenka1 Programmer Contest: ModularPowerEquation!! (AC解法(解法なんだからACなのは当たり前だろ))

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_fhttp://omochan.hatenablog.com/entry/2017/10/20/004232の続きです。普通に蟻本通りにやればいいだけでした…。 x≡k(modm) x≡k'(modm')を満たすxは x=mt+kとして mt≡k'-k(modm')をtについて解けば…

Codeforces Round #441F: Royal Questions

http://codeforces.com/contest/875/problem/Fprinceを点、princessの二人のprinceの候補を辺とみます。それからkruskalっぽいことをします。具体的には 1.違う連結成分どおしで、二つともlockedじゃなければ繋ぐ。 2.同じ連結成分どおしで、lockedじゃなけ…

Tenka1 Programmer Contest: ModularPowerEquation!! (WA解法(は?))

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_fある十分大きいx(A A^A^A^A...を考えるとKのmodφ(M)とmodMの値が求められるので、あとはユークリッドの互除法をして解を構成すればよい…なんですが、値がでかくなりすぎてWA…どうやって小さくする…