メモ

yukicoderでゆるふわgolf

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…

ゼータ変換とメビウス変換

高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablogで誤りを指摘されたので、反省の意味を込めて自分でちゃんと考えた。 メビウスの反転公式 - Wikipediaを元にしているけど、よくわかってないので間違ってたら教えて 追記 全部隣接代数 (順序理論) - W…

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…

Garnerのアルゴリズム

この記事ではGarnerのアルゴリズムの「気持ち」を説明します。 アルゴリズムの説明のみであり、実装については一切説明していません。 合同式の取扱にある程度慣れていることを前提とします(「適当な条件の下ではmodをとっても加減乗除ができる」と知ってい…

atcoder青になるまでにやったこと

注:この記事はマジもんのポエムです こんなものを読むくらいなら精進しろ 2015年以前 学校の授業でBASICとCとSchemeを触る 2015年8月 ふるふわ競プロサイトyukicoderと出会う 最初のACがこれ https://yukicoder.me/submissions/41598 このときコードゴルフ…

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

yukicoder No.661 ハローキティはりんご3個分

問題はこちら No.661 ハローキティはりんご3個分 - yukicoder要するにFizzBuzz main(){ int n; scanf("%d",&n); while(n--){ int t; scanf("%d",&t); if(t%40==0)puts("ikisugi"); else if(t%8==0)puts("iki"); else if(t%10==0)puts("sugi"); else printf("…

yukicoder No.667 Mice's Luck(ネズミ達の運)

問題はこちら No.667 Mice's Luck(ネズミ達の運) - yukicoder本質的には累積和の概念だと思うので★1.5よりは高級だと思うんですがどうなんでしょ「セーフな箱があといくつ残っているか」を覚えておけば良い main(){ char s[1<<17]; int n,o; n=strlen(gets(s…

yukicoder No.676 C0nvertPr0b1em

問題はこちら No.676 C0nvertPr0b1em - yukicoder指示通り実装するだけ char s[1010]; main(){ scanf("%s",s); for(int i=0;s[i];i++){ if(s[i]=='l'||s[i]=='I')putchar('1'); else if(s[i]=='o'||s[i]=='O')putchar('0'); else putchar(s[i]); } } readとg…

yukicoder No.682 Average

問題はこちら No.682 Average - yukicoder(A+B+i)/3が整数⇔A+B+iが3の倍数 を使って全探索するだけ main(){ int a,b; scanf("%d%d",&a,&b); int ans=0; for(int i=a;i<=b;i++)if((a+b+i)%3==0)ans++; printf("%d",ans); } 「A≦i≦BのうちA+B+iが3の倍数になる…

yukicoder No.666 1000000007で割るだけ

問題はこちら No.666 1000000007で割るだけ - yukicoderやるだけ。オーバーフローに注意 main(a,b){ scanf("%d%d",&a,&b); printf("%ld",1L*a*b%1000000007); } 63B

yukicoder No.671 1000000007

問題はこちら No.671 1000000007 - yukicoder 文字列として受け取って、その長さがどれだけ違うかを見るのが一番簡単。 s;main(){printf("%d",abs(strlen(gets(&s))-10));} 48B

遅延セグメント木

この記事では遅延セグメント木の「気持ち」を説明します。 通常のセグメント木に関する知識を前提とします。 アルゴリズムの説明のみであり、実装については一切説明していません。 基本的には以下のサイトの記述を、自分好みにリライトしたものです。 beet-…

yukicoder No.658 テトラナッチ数列 Hard

問題はこちら https://yukicoder.me/problems/1975yukicoder No.657 テトラナッチ数列 Easy - メモと全く同じ long n; f(a,b,c,d){n--%4912?f(b,c,d%17,a+b+c+d):printf("%d\n",a);} main(i){for(;~scanf("%ld",&n);--i&&f(1,0,0,0));} 113B

yukicoder No.657 テトラナッチ数列 Easy

問題はこちら No.657 テトラナッチ数列 Easy - yukicoderT0=1として、n=0から数列が始まるとしてよい。 フィボナッチ数列同様、直前の4項を持って漸化式で求めることができる。 直前の4項は17^4=83521状態なので、高々83521の周期を持つ。 具体的に計算する…

yukicoder No.656 ゴルフ

問題はこちら No.656 ゴルフ - yukicoderやるだけ int main(){ int s=0; for(int i=0;i<9;i++){ int c=getchar()-48; if(c==0)s+=10; else s+=c; } printf("%d",s); } 1文字ずつ見るタイプの問題は、getcharとreadどちらを使うか、最後の改行をどうするか、…

yukicoder No.653 E869120 and Lucky Numbers

問題はこちら No.653 E869120 and Lucky Numbers - yukicoderまずは66……66という形の数を2つ足すことを考えてみる。 同じ桁数のものを足すと133……32に、違う桁数のものを足すと66……66733……32となる。 (ただし、3,6は0個以上。正規表現で言うなら、前者は13*…

yukicoder No.651 E869120 and Driving

問題はこちら No.651 E869120 and Driving - yukicoder算数 時速100kmでa km進むにはa/100時間=a*60/100分かかる。 int main(){ int a; scanf("%d",&a); a*=0.6; printf("%d:%02d",10+a/60,a%60); } 誤差が怖いが、実験する限り、与えられた入力制約の下では…

Tonelli–Shanks algorithm

この記事ではTonelli–Shanks algorithmの原理の「気持ち」を説明します。 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 ループ不変量に着目する考え方はmod_sqrtについて.md · GitHubを参考にしました。 (追記:上…

yukicoder No.646 逆ピラミッド

問題はこちら No.646 逆ピラミッド - yukicoder言われたとおりに二重ループを実装するだけ main(){ int n; scanf("%d",&n); for(int i=n;i>0;i--){ for(int j=0;j<i;j++)printf("%d",n); puts(""); } } 縮める。まずはささっと i,j; main(n){ scanf("%d",&n); for(i=n;i>0;i--,puts(""))for(j=0;j++<i;)printf("%d",n); } 頑張って縮める for(i=n;i>0;i--,puts(""))for(j=0;j++…</i;)printf("%d",n);></i;j++)printf("%d",n);>

yukicoder No.648 お や す み

問題はこちら No.648 お や す み - yukicoder1からmまでの和はm(m+1)/2になるので「m(m+1)/2=nとなるmが存在するか?」と同じ問題になる。 とりあえず誤差の問題は置いておく。 もしそのようなmが存在したとする。 √(m(m+1))=√(2n)となる。ここでm<√(m(m+1…

yukicoder No.638 Sum of "not power of 2"

問題はこちら No.638 Sum of "not power of 2" - yukicoder考察により、答えは次のようになることがわかる ・Nが1,2,3,4,5,7のとき-1 ・N-3が2ベキでないときa=3,b=N-3 ・N-5が2ベキでないときa=5,b=N-5 正当性を示す。 2ベキでない最小の数は3、2番目に小さ…

yukicoder No.643 Two Operations No.2

問題はこちら No.643 Two Operations No.2 - yukicoderいろんな解説が出来て楽しいのでいろいろ紹介 ○偏角を見る 座標平面(X,Y)の点との対応を考える。偏角をθとする。 操作によりθ=45°とすることが目的である。 操作1は直線Y=Xでの対称移動であり、操作2は…

yukicoder No.642 Two Operations No.1

問題はこちら No.642 Two Operations No.1 - yukicoder逆にやる。即ち問題を次のように読み替える 「X=Nから始めて次の操作でX=1に出来るか? 出来るならば最小操作回数を答えよ 操作1:Xを1増やす 操作2:Xが偶数のとき2で割る」 まず、Xが偶数なら操作2に…