Math

New Year Contest 2015

https://snuke21.contest.atcoder.jp/tasks/snuke21_e懐かしの。ムズイ。 ->初手でいけそうなのが、強連結の条件を考えてみるだけだった。 ->強連結成分がL個以上ならまあまあできそう。これが求まればあと引き算するだけ。 -->N!Σ(n+m+...=N)(2^(n(n-1)/2) …

AGC028

https://agc028.contest.atcoder.jp/A map使った。 B 方針ミスって式が複雑になってダメでした…。式で考察するのが苦手すぎる。 てか式で考察が進むことはあまりないんだよなぁ。 C 結構場合分けがあって難しいと思う。1発で通してる人はすごい。 D おそらく…

AOJ 1181

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jpものを回転させる問題は他にも http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2169 がありますが、置換で回転をあらわす時の注意事項。 例えば、 (0, 1, 2, 3, 4, 5) (4…

Codeforces Round #497 (Div. 1)

https://codeforces.com/contest/1007A 普通にループ回しましょう。 B 包除原理で美しく書きましょう。 C やりたくない… D 2-SATだけど、普通にやったら間に合わないのでsegtreeっぽく構築するやつですね。HL分解すれば論理式がO(Nlog^2N)個になって多分解け…

Codeforces Round #493 (Div. 1)

A 作業の合計回数は一定です。 B 勉強になりました。数が埋まってる区間がありそうだからそれをずっと探そうと思っていたけど、冷静になるとこれは十分条件から攻めているのであまり良い戦略とは言えませんね。やっぱり「ありえない」ものを除去していって、…

Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

http://codeforces.com/contest/983A えーABCの中で一番手間取った。QとBの最大公約数gをとってQをgで割ることを繰り返す。こういうの苦手。 B dpしてまたdp C dp[i][j][k][l][m][n]:=i番目の人までみて、場所jにいる。エレベーターに乗っている人はk,l,m,n…

IMO

解けそうなやつ解いてみました。2017 5番 N+1要素以上の単調増加列を使って構成する方法をまず考えましたが、うまく行かず。 そのときに数の区間で考える発想が浮かんだので、1-N+1,N+2-2(N+1),...,(N-1)(N+1)+1-N(N-1)のN個に分割してみました。 そうすると…

AGC023

https://agc023.contest.atcoder.jp/A map B (i,j)と同じでなければならないのは(j+B-A,i+A-B)です。よってB-Aの値だけが重要なのでO(N^3)です。 C あーなるほどなぁ。自分の中で全ての問題は貪欲orDPに落とせるって考えていたのが間違えでした。 なのでDPし…

ARC096

https://beta.atcoder.jp/contests/arc096C. Cを全通り試します。 ll A, B, C, X, Y; void solve() { cin >> A >> B >> C >> X >> Y; ll ans = linf; for(int c = 0; c <= max(X, Y) * 2; c += 2) { ll res = 0; res += C * c; res += A * max(X - c / 2, 0l…

AGC013E: Placing Squares

https://agc013.contest.atcoder.jp/tasks/agc013_e一応知ってるテクニックの組み合わせにはなるんだけど…難しいですね。Degwerさんの数え上げテクニック集で紹介されている問題です。とりあえず自明DPを考えると dp(x)=Σ(y=1...x)y^2dp(x-y)となります。こ…

AtCoder Grand Contest 020D: Min Max Repetition

https://agc020.contest.atcoder.jp/tasks/agc020_dお気持ちそのままが解法ですが、実装がめんどくさすぎる…。1発ACだけど詰めるのにすごい時間かかった。 A>Bとします。Bまず文字が何個まで連続できるかを求めます。これは少し考えればfloor( (A+B)/(B+1) )…

AGC003E: Anticube

https://agc003.contest.atcoder.jp/tasks/agc003_d本質を勘違いした…まず素数のうちa個あるものはa%3個にしてよいです。それでvをcubeにする値uをつなげたグラフを考えると二部グラフになるので、max( (vの数),(uの数) )の合計を求める問題に帰着できます。…

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であれば何も操作を行…

CODE FESTIVAL 2016 Grand Final,G: FESTIVAL

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_g昇順に並んでいる数列S{1,a,b,c,...X}があって、隣り合っている数の比がa(自然数)より小さいとします。 するとX以下の自然数NはSの線形結合で表されて、係数の和はO(a*…

CODE FESTIVAL 2016 Grand Final,D: Dice Game

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_d面白い。petrが赤のサイコロを選ぶ確率をX,touristがiが出た時に赤という確率をxiとします。するとtouristが勝つ確率は f(X,x1...x6)=1-X+Σ((pi+qi)X-qi)xiとな…

AGC007C: Pushing Balls

https://agc007.contest.atcoder.jp/assignments期待値ってこんなこともできるのか…まずf(d1,d2,....d2n)を距離の間隔がそれぞれd1...d2nの時の期待値と定義します。 簡単な例でf(1,2,3,4,5,6)を取り上げます。 1手進めてみましょう。すると f(1,2,3,4,5,6)=…

CODE FESTIVAL 2016 Final,E: Cookies

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_eまずクッキーを食べる回数Tを固定します。これは40くらいまでやればいいです。クッキーを食べるまでA+si秒待ったとすると、 クッキーの総和はΠ(1 Σsiを固定してΠsiを最大化する…

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…

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

AtCoder Regular Contest 084F: XorShift

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

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…

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

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について解けば…

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…どうやって小さくする…

POJ 1284: Primitive Roots

http://poj.org/problem?id=1284答えはφ(p-1)個になります。証明しましょう。準備.n(|p-1)についてx^n≡1(modp)はちょうどn個の解を持つ。証明.p-1=nkとしたとき、 x^(p-1)-1=(x^n-1)(x^(n(k-1))+x^(n(k-1)-1)+...+1)であり、 x^(p-1)-1≡0(modp)の解はp-1=nk…

POJ 2115: C Looooopsなど

POJ 2115: http://poj.org/problem?id=2115A+Cx=B+(2^K)yの解(x,y)のうちxが非負で最小のものを求めればよい。これはユークリッドの互除法やるだけで求められるが、少し遠回りに書いたらREを起こしてえぇ…ってなりました。たぶんオーバーフロー起こしてまし…

POJ 1150: The Last Non-zero Digit

http://poj.org/submit?problem_id=1150初中国剰余定理かもしれない。 (X/10^k)mod10を求めればいいです。ここでkはXが10で割り切れる回数です。 中国剰余定理より (X/10^k)mod10 (X/10^k)mod2, (X/10^k)mod5となります。 対称性よりmod5についてのみ注目し…

CODE FESTIVAL 2017 qual A,E: Modern Painting

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_eまず最初に縦の向きに人を動かすとします。すると領域は二つに分断されます。そのうち一つについて横に進む人がX人、上から下に進む人がY人、下から上に進む人がZ人だ…