Math

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

AtCoder Regular Contest 077D: 11

http://arc077.contest.atcoder.jp/tasks/arc077_bARC077に参加。CとEは結構すぐわかった。D解けないのはさすがにまずい。 余事象で考えればすぐわかる。ずっと足し合わせで求めようとして頭がこんがらがった。 でも足し合わせても求められるくらい頭良くし…

Codeforces Round #419B: Karen and Test

http://codeforces.com/contest/815/problem/B手を動かすのは大事ですね…実験すると4周期ごとにパスカルの三角形が出てくることに気づく。 int N; ll A[MAX_N]; ll F[MAX_N]; ll D[10][10]; bool sign[10][10]; ll mod_pow(ll a, ll n) { if(n == 0) return …

AtCoder Grand Contest 016C: +/- Rectangle

http://agc016.contest.atcoder.jp/submissions/1365887 まあわかれば大したことないんだけど。Hがhで割れて、Wがwで割れる時、h*wの長方形を左上から詰めていくと(H/h)*(W/w)個の長方形がきれいに収まる。 これらの長方形内のh*w個の数の和は負なのでH*W全…

AtCoder Regular Contest 075 E: Meaningful Mean

http://arc075.contest.atcoder.jp/tasks/arc075_c条件を数式に落とし込むと ∑(i=0→r)Ai - rK という値について考えればいいことがわかる。数式を使うと独立性に気付ける問題だった。 あとは適当に座圧してBITで数え上げればよい。 int n; //BIT 1-origin ll…