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

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

問題はこちら 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の「気持ち」を形式的べき級数（母関数）を用いて説明します。 （日本語で詳しく説明しているサイトが見つからなかったので） 間違った説明はしていないつもりですが、（故意に）不正確な記述があるかもしれません。 …

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

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

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

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

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

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

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

問題はこちら No.570 3人兄弟（その１） - 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…

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

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

問題はこちら 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

問題はこちら 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…

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

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

問題はこちら 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…

問題はこちら 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++){>…

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

問題はこちら No.561 東京と京都 - yukicoderDPやるだけ（といいつつ、後ろから見る方法しか思いつかなかったので要反省）(i-1)日目が終了した時点で東京にいるときの最大利益をT、京都にいるときの最大利益をKとおく。 i日目に東京でt、京都でk得られる場合…

問題はこちら No.537 ユーザーID - yukicoder2つの数A,Bを連結するのは、文字列として処理するのでも良いが、Cだと面倒なので計算をする 数Bの桁数はで得られるので、AとBをこの順で連結したものはで求められるNが大きいので1～√Nまでを調べる long n,s[2000…

問題はこちら No.560 ふしぎなナップサック - yukicoder算数やるだけ ナップサックの中にM円入っているとき、1回叩いた後は (2M+(M+1)+0)*1/3=M+1/3 より(M+1/3)円になる。 これはMに依らないのでこの操作をN回行うとM+N/3円になる。 （写像f(M)=M+1/3をN回…

問題はこちら No.559 swapAB列 - yukicoder求めるものは転倒数と同値 先頭から見ていってAが登場する度に、それ以前に登場したBの個数を数えれば良い char s[99]; b,ans,n; main(){ gets(s); n=strlen(s); for(int i=0;i

問題はこちら No.558 575検出するやつ - yukicoderstrstrするだけ char s[110]; main(){ gets(s); puts(strstr(s,"575")?"YES":"NO"); } 100文字をintに読み込んでも幸いREにはならず a;main(){puts(strstr(gets(&a),"575")?"YES":"NO");} 50B aをmain引数に…

問題はこちら No.305 鍵(2) - yukicoderwriter解と同じ発想 ある桁の数字を変えた時、当たり数が大きくなれば新しい方が当たり、小さくなれば古い方が当たり。これを繰り返して上の桁から順に調べていく char s[]="0000000000"; n,k,i; main(){ puts(s); ffl…

問題はこちら No.557 点対称 - yukicoder回文と同様、上半分を決めると下半分は自動的に決まる ・n=1のとき 1,8の2通り ・nが偶数のとき 上位n/2桁を決めると、下位は自動的に決まる 先頭の位に使えるのは1,6,8,9の4通り それ以外は0,1,6,8,9の5通り よって4…

問題はこちら No.554 recurrence formula - yukicoderとする このとき よりとなりの漸化式が得られる でありなので、これにより計算できる long s[100100]; n,ans,m=1e9+7; main(){ scanf("%d",&n); if(n==1)ans=1; else{ s[1]=1; for(int i=2;i<=n;i++)s[i]…

問題はこちら No.552 十分簡単な星1の問題 - yukicoder値が大きいので文字列として読み込む。 0のときはそのまま出力し、それ以外のときは末尾に0をつける char s[99]; main(){ gets(s); if(strcmp(s,"0")==0)puts("0"); else printf("%s0",s); } 20文字くら…