この記事では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…