メモ

yukicoderでゆるふわgolf

ABC249Ex解説の解説

公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。 オリジナル:Editorial - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249) 数列 に対して、終了条件を満たすまでの操作回数の期待値…

Project Euler 201-250 解説

これの続き sugarknri.hatenablog.com201 DP202 前座パートは中受典型 No.306 さいたま2008 - yukicoder 本編前半は3種類の直線をZ[ω]座標系で書いて考える 本編後半は素因数分解してDPなり包除原理なり203 やるだけ クンマーの定理を思い出してもいい204 O(…

Project Euler 151-200 解説

これの続き sugarknri.hatenablog.com「DPの状態数が少ないので行列累乗や高速きたまさ法で計算量落ちまーす」の類は実りがないので以降言及しません。151 DP152 1/kpを使ったら、pがどこかで約分される必要があります バックトラックDFSで全探索 指数でも分…

Project Euler 101-150 解説

これの続き sugarknri.hatenablog.com101 ラグランジュ補間 普通にやるとO(N^3) 補間に使う点が等差数列なのでO(N^2)にできる ラグランジュ補間したときの係数をぐっと睨むと求めるものをexplicitにも書ける102 多角形の内外判定 普通は半直線と線分の交差判…

project Euler 51-100 解説

これの続き sugarknri.hatenablog.com51 3の倍数で枝刈り52 有名問題すぎる53 尺取 rが小さいうちは境界を直接計算すると早い54 気合55 多倍長整数56 多倍長整数 嘘下界を使って嘘枝刈りで高速化57 連分数の最後に1項増やしたときの挙動を知っていますか 分…

project Euler 1-50 解説

間違ってたりより良い解法があったら教えて計算量は四則計算の回数。桁が増えすぎると壊れる 1 包除原理 これくらい手で解け2 愚直で解ける 項数を先に求めて行列累乗すればO(loglogN) 一般項を出して適当なmodを取ってCRTすると実質O(1)3 素因数分解の計算…

segment tree beats 覚書

これを読め rsm9.hatenablog.com ~終わり~ 以下ポエム ひとなのでさんによるこの記事を読むまでbeatsの理解が困難だったが、この記事を読むと全てを3秒で理解できた。 これ以前に存在していた記事で理解が困難だったのは、まずそもそもbeatsというデータ構…

a+b=a^b+2(a&b)の一般化

bit毎の排他的論理和を 、論理積を と置くと、 任意の非負整数 に対して が成り立ちます。 これは を観察すれば成り立つことが示せます。 この等式は競技プログラミングで非常によく使われるテクニックの一つです。 Yukiちゃんはこの等式を一般化して、 の形…

線形漸化式と微分方程式

微分方程式を微分作用素で解くやつ知ってる?f''-3f'+2f=0 の解は? 微分作用素をDとして、与えられた方程式は(D-1)(D-2)f=0 ここで一般に(D-k)f=0の解はC*e^kxなので、f(x)=C1*e^x+C2*e^2x全く同じようにして線形漸化式の一般項が出るんですよねa[n+2]-3a[n…

sum of multiplicative function

これはなに?Min_25さんの以下の記事を自分が読みやすいように書き換えたものです。 min-25.hatenablog.com Min_25さんによる実装はこちら https://ideone.com/9F9amv 要求知識 ・平方根の上下で分けるテク ・fenwick tree ・線形篩の"気持ち"を知っていると…

A Sequence of Permutations

a[i]=a[i-1]-a[i-2]の特性方程式が1の6乗根だからmod6で見れる、なるほどなぁという気持ちに— お気持ち表明を控える (@tk0_math) 2021年2月10日 ほんまか? は を満たすので、mod 6で見たいという気持ちで式変形をすると となって として を得る。よってで解…

yukicoder 1322

お断り:提出してないので間違ってるかもO(N^0.75) prime countingを完全に理解していてこれが解けないのは端的に言ってカスなんだよね・そもそもφはmultiplicativeなので、当然素因子ごとにわけて考えたくなる ・dp[i][j]=#{n | nの全ての素因子はPi以下、φ…

純粋培養競技プログラマが就職して1年

■スペック 国立大理系院卒 就職まで競プロ以外でのプログラミング経験なし 今はAtCoder橙 社会性破滅・就活破滅 英語壊滅 IT中小企業にどうにか潜り込む就活編はこちら sugarknri.hatenablog.com■1年経過時点での環境 pythonで機械学習やってる git使ってな…

指数型母関数

この記事は 37zigenさんによる以下の記事をもとに、お気持ちパートを自分にとってわかりやすいようにメモしたものです。 真面目な解説は書いていないので、そういうのを読みたい人は元記事の方をみてください。 37zigen.com ・物を数える気持ち:「互いに区…

コネと学歴は就活の役にたつ

就活記事です M2 5月 なんで就活の記事がM2から始まるんですか? 社会のことを何も知りません。人々はいつから就活をしているんですか? 実は修論どころか単位がそろわない可能性があって、就活どころじゃなかったし、この時点でもそれどころじゃない けどま…

FFT

何回見ても非再帰FFTの話が覚えられないのでメモ1のN乗根をgとする。 をFFTしたい。 その結果は になる。ということで、全てのiについての が求められればよい。 これを頑張って計算する。 ところで、再帰FFTの気持ちには2種類あることをご存じでしたか?ぼ…

純粋培養競プロerが応用情報技術者試験に合格するまで

Q.これはなに笑 A.う笑 ・スペック 理系だが情報系ではない 競プロ以外のプログラミングをしたことはない ・2019年2月 基本情報技術者試験とかいうのを受けておくといいことがあるらしい 適当に参考書を1冊買う・2019年3月 とりあえずノー勉で過去問を1回分…

位数Xのアーベル群

出典さて、この問題はopが可換群であればBITを用いて解くことができます数列aの全ての要素、i, j, kが全て1以上X以下の値であることが分かっている時、任意の数列aに対しBITで解くことのできる演算opが全部で何通りあるか求めてください— 31536000 (@Curious…

yukicoder No.712 赤旗

問題はこちら No.712 赤旗 - yukicoder'W'の数を数えるだけ。 s; main(c){ scanf("%*d%*d\n"); while(c=getchar(),~c)if(c=='W')s++; printf("%d",s); } 2行目以降は'\n'(10),'R'(82),'W'(87)のいずれかしかないので&1で識別可能。1行目の読み飛ばしとうまく…

yukicoder No.706 多眼生物の調査

問題はこちら No.706 多眼生物の調査 - yukicoderstrlen(s)-2の最頻値を見るだけ int a[1010]; int main(){ int n; scanf("%d\n",&n); for(int i=0;i<n;i++){ char s[1010]; gets(s); a[strlen(s)-2]++; } int ans=2; for(int i=2;i<=1000;i++)if(a[i]>=a[ans])ans=i; printf("%d",ans); } ぐっと睨んでループをまとめる。文字列を読み込む変数をごまかしたり</n;i++){>…

yukicoder No.701 ひとりしりとり

問題はこちら No.701 ひとりしりとり - yukicoderまずn個の相異なる文字列を生成しよう。これは前にやった。 yukicoder No.327 アルファベット列 - メモ こうしてできた文字列の前後に'a'を付け、最後の単語にはさらに'n'をつければよい //No327の使い回し v…

yukicoder No.700 LOVE

問題はこちら No.700 LOVE - yukicoderstrstrという便利な関数があるのでそれを使うだけ s,f;main(){for(;gets(&s);f+=strstr(&s,"LOVE"));puts(f?"YES":"NO");} 67B

yukicoder No.693 square1001 and Permutation 2

問題はこちら No.693 square1001 and Permutation 2 - yukicoder数列の順序は関係ないのでソートしてから考えて良い。 1から順に作ることを考えると、小さい方から順に使うのが最適であることがわかるので、Σ|a[i]-i|が解 #define swap(p,q)(p^=q^=p^=q) int…

yukicoder No.692 square1001 and Permutation 1

問題はこちら No.692 square1001 and Permutation 1 - yukicodern=1かどうか判定するだけ値を1つ見ればよいのでgets+atoiやるだけ a;main(){puts(atoi(gets(&a)-1)?"Petr":"square1001");} ……と思ったら、scanfを使う方が短くなるらしい。 未定義動作だから…

yukicoder No.683 Two Operations No.3

問題はこちら No.683 Two Operations No.3 - yukicoder逆向きに再帰で全探索すると解ける。 int f(long x,long y){ if(x==0||y==0)return 1; int flag=0; if(x%2==0)flag|=f(x/2,y-1); if(y%2==0)flag|=f(x-1,y/2); return flag; } int main(){ long x,y; sc…

yukicoder No.689 E869120 and Constructing Array 3

問題はこちら No.689 E869120 and Constructing Array 3 - yukicoderバラバラに考えれば良さそう つまりa+b,c+d,e+f,……はそれぞれ素数だが、それ以外の組み合わせは素数にならないようなものを構成することを考える。 そのようなものが作れれば、それらをそ…

yukicoder No.688 E869120 and Constructing Array 2

問題はこちら No.688 E869120 and Constructing Array 2 - yukicoder明らかに並び順には依存せず、0と1の個数のみで決まることがわかる。 1がi個、0がj個あるとき、和が2になる部分集合はi*(i-1)/2*pow(2,j)個あるので、i,jを全探索する main(){ int k; scan…

yukicoder No.687 E869120 and Constructing Array 1

問題はこちら No.687 E869120 and Constructing Array 1 - yukicodern/2とn-n/2を出力するだけ。特に工夫することはない main(n){ scanf("%d",&n); printf("%d %d",n/2,n-n/2); } 50B

yukicoder No.668 6.0*10^23

問題はこちら No.668 6.0*10^23 - yukicoder桁上りなどに気をつけて、3桁目を四捨五入するコードを書く char s[1000010]; int main(){ gets(s); int s0=s[0]-48; int s1=s[1]-48; int s2=s[2]-48; int n=strlen(s)-1; if(s2>=5)s1++; if(s1>9){ s1=0; s0++; …

yukicoder No.677 10^Nの約数

問題はこちら No.677 10^Nの約数 - yukicoder約数は2^i*5^jの形をしている。全て求めてソートすればよい。 ここでは約数を保存せず、毎回「今まで出力したものより大きい最小のもの」を探すようにしている。O(N^4) main(){ int n; scanf("%d",&n); long M=0;…