メモ

yukicoderでゆるふわgolf

yukicoder No.637 X: Yet Another FizzBuzz Problem

問題はこちら No.637 X: Yet Another FizzBuzz Problem - yukicoderFizzBuzzは8文字、FizzとBuzzは4文字、それ以外のときは100以上なら3文字、そうでなく10以上なら2文字、さもなくば1文字 main(){ int ans=0; for(int i=0;i<5;i++){ int n; scanf("%d",&n);…

yukicoder No.593 4進FizzBuzz

問題はこちら No.593 4進FizzBuzz - yukicoder頭の桁から順に見て、4倍しながら足していくことで求める事ができる char s[1000010]; main(){ gets(s); int n=strlen(s); int m3=0,m5=0; for(int i=0;i

yukicoder No.597 concat

問題はこちら No.597 concat - yukicoder言われたとおりやるだけ 実際に繋げなくても、入力をそのま順番に出力していけば繋がる main(){ int n; char s[99]; scanf("%d",&n); while(n--){ scanf("%s",s); printf("%s",s); } } 1行目の読み飛ばしをどうするか…

yukicoder No.591 (^o^)/

問題はこちら No.591 (^o^)/ - yukicoder言われたとおりにやるだけ main(){ char a,b; scanf("%c %c",&a,&b);//"%c%c"だと2文字目が得られない(改行の読み飛ばし) printf("(%c%c%c)/",a,b,a); } 読み込みを次のようにまとめることが出来る a; main(){ gets…

yukicoder No.627 ランダムウォークの軌跡

問題はこちら No.627 ランダムウォークの軌跡 - yukicoder言われたとおりにやる。 X[0]=0とするとT=1における場合分けをしなくて良くなるので楽 int x[999],t; main(){ scanf("%d",&t); for(int i=1;i<=t;i++)scanf("%d",x+i); for(int i=1;i<=t;i++)if(abs(…

yukicoder No.632 穴埋め門松列

問題はこちら No.632 穴埋め門松列 - yukicoderありえる入力は6通りしかないので全て手で確認してみよう 2,3,?→1 2,?,3→14 3,2,?→4 3,?,2→14 ?,2,3→4 ?,3,2→1 ということで、「真ん中がそれぞれ2,3,?のとき答えはそれぞれ4,1,14」となることがわかる char s[…

yukicoder No.605 板挟みの球面

問題はこちら No.605 板挟みの球面 - yukicoder数学するだけ 曲線y=f(x)を、x軸を中心に回転させて出来る回転体の表面積は で与えられる。 よってを代入して計算するとが得られる float l,r; main(){ scanf("%f%f",&l,&r); printf("%f",6.28318*(r-l)); } 65B

yukicoder No.604 誕生日のお小遣い

問題はこちら No.604 誕生日のお小遣い - yukicoder算数するだけ。 A年間で(A-1+B)円もらえる。 残りの端数は、A-1以下なら1円ずつもらってる内に貯まり、それ以上ならA年目までかかる。 よって答えはC/(A+B-1)*A+min(A,C%(A+B-1))となる。 long a,b,c; main…

yukicoder No.601 Midpoint Erase

問題はこちら No.601 Midpoint Erase - yukicoder(x1,y1)と(x2,y2)の中点が格子点 ⇔「(x1+x2)/2が整数」かつ「(y1+y2)/2が整数」 ⇔「x1とx2の偶奇が等しい」かつ「y1とy2の偶奇が等しい」よって与えられた点たちを、「x座標が偶数/奇数、y座標が偶数/奇数」…

yukicoder No.64 XORフィボナッチ数列

問題はこちら No.64 XORフィボナッチ数列 - yukicoderxorを表す記号をとする。 が成立する事に注意すると、 となるから、結局 となることが分かる。つまり、nの3での剰余について場合分けすればよい。 long a,b,n; main(){ scanf("%ld%ld%ld",&a,&b,&n); if(…

yukicoder No.598 オーバーフローファンタジー

問題はこちら No.598 オーバーフローファンタジー - yukicoder攻撃し続けてHPを0以下にするか、回復し続けて2^(N-1)以上にするかのどちらか。 よって求めるべきはmin( ceil(X/A) , ceil((2^(N-1)-X)/B) ) ここで一般にx,y>0に対し、ceil(x/y)=1+floor((x-1)/…

Berlekamp–Massey algorithm

この記事ではBerlekamp–Massey algorithmの「気持ち」を形式的べき級数(母関数)を用いて説明します。 (日本語で詳しく説明しているサイトが見つからなかったので) 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 …

きたまさ法

この記事ではきたまさ法の「気持ち」を多項式剰余を用いて説明します。 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 数式により厳密に議論を追いたい方は高速 Kitamasa 法 - みさわめもなどをご覧ください。 アル…

yukicoder No.243 出席番号(2)

問題はこちら No.243 出席番号(2) - yukicoder出席番号を1ずらして1-based index、すなわちとする。 とおく。 をのべき集合、すなわちとする。 を が嫌いな人の数 とする。 を (「が嫌いな人に出席番号が割り当てられている」を満たす割り振りの個数 とする…

yukicoder No.565 回転拡大

問題はこちら No.565 回転拡大 - yukicoder90度回転する操作により(i,j)にうつるようなマスは(h-1-j,i)である。(0-based index) よって new[i][j]=old[h-1-j][i]; という感じのことをi,jについてループでやればよい。 180度、270度回転はこの操作を繰り返…

yukicoder No.326 あみだますたー

問題はこちら No.326 あみだますたー - yukicoder{1,…,N}上の順序 " このとき、「あみだくじによって数列{Ai}を作ること」と「順序"バブルソートをすること」が対応する (完成するあみだくじにおいて左にある数ほど"小さい"と考えるということ)ということ…

yukicoder No.556 仁義なきサルたち

問題はこちら No.556 仁義なきサルたち - yukicoderUnion-Findするだけ int uniroot[10010],unicnt[10010]; void ufinit(int n){for(int i=0;i

yukicoder No.553 AlphaCoder Rating

問題はこちら No.553 AlphaCoder Rating - yukicoderほとんどそのまま数式を計算すればよいが、g^(-1)とF(∞)だけは非自明。 gの逆関数はにぶたんで、F(∞)は適当に大きなxを用いてF(x)で近似することで、問題文の数式をそのまま実装して答えを得ることもでき…

yukicoder No.588 空白と回文

問題はこちら No.588 空白と回文 - yukicoderまず線対称の軸となるべき場所を固定する。 (そのような場所は、文字の中心か、文字と文字の間となる) 中心から外側へ向かって、各文字が回文を構成するかどうかをチェックする。 中心に対して対称な位置にある…

yukicoder No.571 3人兄弟(その2)

問題はこちら No.571 3人兄弟(その2) - yukicoderその1と同様 a[身長][体重]=人 という配列を作っても良いが a[身長*(大きな数)-体重]=人 とすることで1次元配列にできる a[30010],t,s; main(){ for(int i=1;i<=3;i++){ scanf("%d%d",&t,&s); a[t*101-s]…

yukicoder No.570 3人兄弟(その1)

問題はこちら No.570 3人兄弟(その1) - yukicoder場合分けでも簡単に解けるが、別の方針で考える a[身長]=人 という配列を作って身長が大きい方からチェックする a[999],t; main(){ for(int i=1;i<=3;i++){ scanf("%d",&t); a[t]=i; } for(int i=200;i>10…

yukicoder No.587 七対子

問題はこちら No.587 七対子 - yukicoder各文字が何個あるかを数える。 ちょうど2個ある文字がちょうど6種類あるとき、その時に限り、残りの1種類と同じ文字を加えることで7ペアにできる a[999],ans,c,i; main(){ for(i=0;i<13;i++)a[getchar()]++; for(i='a…

yukicoder No.589 Counting Even

問題はこちら No.589 Counting Even - yukicodernを2進法で表したときの1の個数をpopcnt(n)とおく 結論からいうとN+1-2^popcnt(N)が答え 方針はいろいろあるがいずれの場合も奇数が2^popcnt(N)個あることを示す・パスカルの三角形 (以下、「n段目の左からm…

yukicoder No.586 ダブルブッキング

問題はこちら No.586 ダブルブッキング - yukicoder各部屋について最初の1人で部屋を予約することにする。 2人目以降は振替により(P1+P2)円の損失が発生する。 a[1000],p1,p2,n,x,s; main(){ scanf("%d%d%d",&p1,&p2,&n); for(int i=0;i

yukicoder No.581 XOR

問題はこちら No.581 XOR - yukicoderXORを表す演算子を^とする。XORの基本的な性質を確認する ・順序に依らない(可換かつ結合的) ・任意のXについてX^X=0C=A^Bの両辺にAをXORすることでA^C=A^A^B=Bが得られる long a,b;main(){scanf("%ld%ld",&a,&b);prin…

yukicoder No.555 世界史のレポート

問題はこちら No.555 世界史のレポート - yukicoderDP解法との賢い数学解法がある・DP解 N文字以上を作る最小コスト=min{ちょうどK文字を作る最小コスト|K≧N} K文字を作る際には、その過程で必ずK/2文字以上の状態を経由するので、Kの上限は2Nとしてよい。 …

yukicoder No.566 だいたい完全二分木

問題はこちら No.566 だいたい完全二分木 - yukicoder○激ヤバ解法 シャッフルすれば高確率で通る○まじめな解法 普通に完全二分木をつくると高さはK-1になる。そこで適当にいじって高さをKにする ・方針1 完全二分木を作る過程で、2と3を入れ替える。 そうす…

yukicoder No.567 コンプリート

問題はこちら No.567 コンプリート - yukicoder包除原理やるだけ(説明は後述) main(n){ scanf("%d",&n); printf("%.9f", 1 - 6*pow(5/6.,n) +15*pow(4/6.,n) -20*pow(3/6.,n) +15*pow(2/6.,n) - 6*pow(1/6.,n) ); } 事象A1,…,A6を、 A1:1が出ない … A6:6…

yukicoder No.564 背の順

問題はこちら No.564 背の順 - yukicoder最初は1位で、高い人が現れるたびに順位は1つ下がる h,n,t,S; main(){ scanf("%d%d",&h,&n); S=1; for(int i=1;i<n;i++){ scanf("%d",&t); if(t>h)S++; } printf("%d",S); if(S%10==1)puts("st"); else if(S%10==2)puts("nd"); else if(S%10==3)puts</n;i++){>…

yukicoder No.549 素材合成システム

問題はこちら No.549 素材合成システム - yukicoder合成素材の側の経験値の最終的な寄与度は高々floor(a/2) 実際に、一番経験値が高い奴をベースにし、残りを素材として順次合成していくことで最大になる。 c(int*a,int*b){return*b-*a;} a[100010],n,S; mai…