メモ

yukicoderでゆるふわgolf

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座標が偶数/奇数」という4つのグループに分けると、中点が格子点になるよう2点を選ぶことは、同じグループから2点を選ぶことと同値。
各グループに属する点の個数を数えて、全部で何組作れるかを見ればよい

a[2][2],n,x,y;
main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&x,&y);
		a[x%2][y%2]++;
	}
	if(a[0][0]/2+a[0][1]/2+a[1][0]/2+a[1][1]/2)%2==1)puts("Alice");
	else puts("Bob");
}

作ることが出来る組の数(つまりa[0][0]/2+a[0][1]/2+a[1][0]/2+a[1][1]/2)をsとする。
sを最後に計算するのではなく、読み込みながら計算することを考える。
sが増えるのはa[*][*]が奇数から偶数に変化したときなので、s+=a[*][*]++%2とすることが出来る。
さらによく考えると、sは偶奇のみが必要なので、実は%2を省略してs+=a[*][*]としてよい。
また、配列は明らかに1次元4要素にまとめられる

s,x,a[4];
main(y){
	for(gets(&y);~scanf("%d%d",&x,&y);)s+=a[x%2*2+y%2]++;
	puts(s%2?"Alice":"Bob");
}

95B
nの読み飛ばしを頑張るパターンも考えたが96Bにしかならず

s,x,y,a[4];
main(i){
	for(;~scanf("%d",&y);x=y)s^=i--&!!i&&a[x%2*2+y%2]++%2;
	puts(s?"Alice":"Bob");
}

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

問題はこちら
No.64 XORフィボナッチ数列 - yukicoder

xorを表す記号を\oplusとする。
a\oplus b=b\oplus a\\
(a\oplus b)\oplus c=a\oplus(b\oplus c)\\
a \oplus b \oplus b =a
が成立する事に注意すると、
F_2=F_1\oplus F_0\\
F_3=F_2\oplus F_1=(F_1 \oplus F_0)\oplus F_1=F_0\\
F_4=F_3\oplus F_2=F_0\oplus(F_1 \oplus F_0)=F_1
となるから、結局
F_{n+3}=F_n
となることが分かる。つまり、nの3での剰余について場合分けすればよい。

long a,b,n;
main(){
	scanf("%ld%ld%ld",&a,&b,&n);
	if(n%3==0)printf("%ld",a);
	if(n%3==1)printf("%ld",b);
	if(n%3==2)printf("%ld",a^b);
	return 0;
}

n%3で0とそれ以外の区別はつくが、1と2の区別は~n%3でつけることができるので

long a,b,c;
main(){
	scanf("%ld%ld%ld",&a,&b,&n);
	c=!printf("%ld",n%3?~n%3?b:a^b:a);
}

81B

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)/y)なので、単なる整数除算で計算できる

#define min(p,q)(p<q?p:q)
main(){
	int n,x,a,b,s1,s2;
	scanf("%d%d%d%d",&n,&x,&a,&b);
	s1=1+(x-1)/a;
	s2=1+((1L<<(n-1))-x)/b;
	printf("%d",min(s1,s2));
}

ぎゅっとするだけ

main(n,x,a,b){
	scanf("%d%d%d%d",&n,&x,&a,&b);
	printf("%d",a=1+fmin(~-x/a,((1L<<n-1)+~x)/b));
}

91B

Berlekamp–Massey algorithm

この記事ではBerlekamp–Massey algorithmの「気持ち」を形式的べき級数(母関数)を用いて説明します。
(日本語で詳しく説明しているサイトが見つからなかったので)
間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。
連分数を使うという発想はhttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/sentan2005.pdfを参考にしました。
アルゴリズムの説明のみであり、実装については一切説明していません。


○Berlekamp–Massey algorithmとは何か
線形漸化式で与えられる数列の最初の何項かが与えられたとき、その漸化式を求めるアルゴリズム
正確には「線形漸化式で与えられる数列の最初の2N項が与えられた時、その数列を生成するN次以下の最小の線形漸化式を求めるアルゴリズム
(N次の漸化式なら必ず最初の2N項を一致させられることに留意)


○形式的べき級数
多項式とは\sum_{i=0}^n a_i x^iという形で書ける式のことだった。
ここで、高次の項は無限に存在してもよいような物を考える。つまり\sum_{i=0}^\infty a_i x^iを考えよう。
例えば1+x+x^2+x^3+\ldotsというようなもの。
このようなもの全体は環をなし、「形式的べき級数環」と呼ばれる。
(環とは、足し算、引き算、掛け算の3つが自由にできるようなもののこと)
これの商体を「形式的べき級数体」という。
(体とは、加減乗除が自由にできるようなもののこと)
証明は省略するが、形式的べき級数体の元は\sum_{i=-k}^\infty a_i x^iというような形で書ける。
(負ベキの項が有限個しかないべき級数として書ける)
さらに、有理関数体は形式的べき級数体に含まれる。
つまり有理式はべき級数体で書ける(収束半径を気にせずに、0を中心としてローラン展開したものだと思えばよい)


○線形漸化式の母関数
特性方程式
g(a_{n+k},a_{n+k-1},\ldots,a_{n+1},a_n)=0という線形漸化式で与えられる数列を考える。
このとき、f(x):=g(x^k,x^{k-1},\ldots,x,1)をこの数列の特性方程式という。
例えばフィボナッチ数列ならa_{n+2}-a_{n+1}-a_n=0なので特性方程式x^2-x-1となる。
・母関数
数列\{a_n\}に対し、形式的べき級数\sum_{i=0}^\infty a_i x^iを母関数という。
例えばフィボナッチ数列の母関数は0+1x+1x^2+2x^3+3x^4+5x^5+\ldotsとなる。
・母関数と特性方程式
線形漸化式で与えられる数列\{a_n\}があり、母関数をF(x)特性方程式f(x)k=\deg f(x)とする。
このとき、x^kf(1/x)F(x)多項式である。
x^kf(1/x)f(x)の「xの冪を逆順にしたもの」であり多項式。例えば、f(x)=x^2-x-1ならx^kf(1/x)=1-x-x^2となる)
x^kf(1/x)F(x)多項式になることはk次以上の項について具体的に係数を計算すると0になることから分かる)
つまりF(x)x^kf(1/x)を分母とする有理式として表すことができる。


○ここまでのまとめ
ここまでをまとめると
「線形漸化式で与えられる数列の最初の何項かが与えられたとき、その漸化式を求めよ」
という問題は
「有理式を形式的べき級数で表したものの低次の項が与えられたとき、元の有理式(特にその分母)を求めよ」
と同じであることが分かる


ユークリッドの互除法と連分数
・連分数
連分数とは、次のような形をした分数のことである。
a+\cfrac{1}{b+\cfrac{1}{c+\cfrac{1}{d+\dots}}}
詳しい説明はwikipediaなどに譲るが「有理数を連分数の形で表すと、有限ステップで止まる」という重要な性質がある。
つまり、任意の有理数\dfrac{p}{q}に対して、ある整数の有限列\{a_i\}_{i=0}^nが存在して
\dfrac{p}{q}=a_0+\cfrac{1}{a_1+\cfrac{1}{\dots+\cfrac{\dots}{a_{n-1}+\cfrac{1}{a_n}}}}
となる。このことは連分数で表すことが本質的にユークリッドの互除法と対応していることから分かる
・連分数とユークリッドの互除法
例えば\dfrac{27}{10}を連分数の形で書くことを考えてみる。

\cfrac{27}{10}\\
=2+\cfrac{7}{10}\\
=2+\cfrac{1}{\cfrac{10}{7}}\\
=2+\cfrac{1}{1+\cfrac{3}{7}}\\
=2+\cfrac{1}{1+\cfrac{1}{\cfrac{7}{3}}}\\
=2+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{3}}}\\
よく見れば分かる通り、これはユークリッドの互除法をしていることにほかならない

27=10*2+7\\
10=7*1+3\\
7=3*2+1\\
3=1*3\\


○線形漸化式の母関数と連分数
・形式的べき級数における割り算のあまり
形式的べき級数体においても「あまりのある割り算」を適切に定める事ができるので、ユークリッドの互除法が適用できる。
形式的べき級数の世界においては「次数」とは「最低次」の事を指す。
(x=0でのローラン展開だったので、低次の項ほど影響力が強い……という「気持ち」)
例えばx+x^2+2x^3+\ldotsの次数は1であり、x^{-2}+x^{-1}+1+x+x^2+\ldotsの次数は-2である。
割り算をする際の余りは、「割る数」よりも「余り」の次数の方が大きくなるように求める。
(次数が大きい方が影響力が弱い……という「気持ち」だったので)
例えば、(1-x) \div (1+x) は商が1で余りが-2xとなるし、
 1 \div (x+x^2)は商がx^{-1}-1で余りがx^2となる。
・形式的べき級数表示での連分数展開
フィボナッチ数列の場合を例とする。
まずは有理式の形の場合についてやってみる。
母関数は\dfrac{x}{1-x-x^2}だったので

\cfrac{x}{1-x-x^2}\\
=\cfrac{1}{\cfrac{1-x-x^2}{x}}\\
=\cfrac{1}{(x^{-1}-1)+\cfrac{-x^2}{x}}\\
=\cfrac{1}{(x^{-1}-1)+\cfrac{1}{-x^{-1}}}\\
となる。ではこれをべき級数の形のままやってみよう

\cfrac{x+x^2+2x^3+3x^4+5x^5+\ldots}{1}\\
=\cfrac{1}{\cfrac{1}{x+x^2+2x^3+3x^4+5x^5+\ldots}}\\
=\cfrac{1}{(x^{-1}-1)+\cfrac{-x^2-x^3-2x^4-3x^5-\ldots}{x+x^2+2x^3+3x^4+5x^5+\ldots}}\\
=\cfrac{1}{(x^{-1}-1)+\cfrac{1}{\cfrac{x+x^2+2x^3+3x^4+5x^5+\ldots}{-x^2-x^3-2x^4-3x^5-\ldots}}}\\
=\cfrac{1}{(x^{-1}-1)+\cfrac{1}{-x^{-1}}}\\
ということで同じ結果が得られた。
つまり、「べき級数の世界で連分数の形にする」→「連分数を有理式の世界で戻す」という操作によって、有理式が得られる。


○実装について
互除法の部分を非再帰で上手く実装したものがBerlekamp–Massey algorithmである。(と理解しているが、間違っていれば指摘してください)
具体的な実装はwikipedia英語版か、ドイツ語版を参考にするとよい。
微妙に異なる実装がなされており、自分には後者の方が理解しやすかった。
いずれにせよ、「一個前の値を保存しておいて、それを定数倍して足す」という操作が、互除法を戻す操作と対応していると理解すると分かりやすいかと思います。

きたまさ法

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


○きたまさ法とは何か
線形漸化式で与えられる数列の第K項を高速に求めるアルゴリズム
より正確に言えば「N項線形漸化式により与えられる数列の第K項をO(N^2 \log K)で求めるアルゴリズム
さらに、これを高速化した「高速きたまさ法」というアルゴリズムによりO(N \log N \log K)で求めることも可能
以下ではNの数え方として、
例えばフィボナッチ数列F_{n+2}=F_{n+1}+F_{n}ならN=2
a_{n+100}=a_{n+1}+a_{n}ならN=100とする。
(それぞれN=3, N=101として本質的には何も変わらない)


○線形漸化式と多項式剰余
・次数下げ
まずは次のような問題を考える
問題:\phi=\frac{1+\sqrt{5}}{2}とするとき、\phi^5を求めよ
この問題は、大学受験界隈などでは「次数下げ」という名前で知られる次のテクニックにより、計算の手間を少し減らすことができる
答案:
\phi^2=\phi+1を満たすので
\phi^5\\
=\phi^3(\phi+1)\\
=\phi^4+\phi^3\\
=\phi^2(\phi+1)+\phi^3\\
=2\phi^3+\phi^2\\
=2\phi(\phi+1)+\phi^2\\
=3\phi^2+2\phi\\
=3(\phi+1)+2\phi\\
=5\phi+3\\
=\frac{11+5\sqrt{5}}{2}

ではこのことを念頭において次の問題を考えてみよう
問題:a_{n+2}=a_{n+1}+a_nという漸化式で与えられる数列がある。a_5a_0a_1を用いて表せ
答案:
a_5\\
=a_4+a_3\\
=(a_3+a_2)+a_3\\
=2a_3+a_2\\
=2(a_2+a_1)+a_2\\
=3a_2+2a_1\\
=3(a_1+a_0)+2a_1\\
=5a_1+3a_0

上でやった問題とほとんど同様にして解けることがわかった。
これがきたまさ法を(多項式剰余で)理解するうえで大切な発想となる。

・次数下げと多項式剰余
さて、最初の問題に立ち返って、答案を次のように書き換える。
答案:
x^5x^2-x-1で割った商と余りを考えると
x^5=(x^3+x^2+2x+3)*(x^2-x-1)+(5x+3)となる。
この式にx=\phiを代入することで
\phi^5=(\phi^3+\phi^2+2\phi+3)*(\phi^2-\phi-1)+(5\phi+3)となる。
\phi^2-\phi-1=0をなので第1項は消えて
\phi^5=5\phi+3となる。

ということで、最初の問題の方は多項式剰余を求める問題に帰着できることがわかる。
では数列の問題の方はどうだろうか。
本質的な部分だけ比較しよう。

多項式

x^5=\\
x^3*(x^2-x-1)\\
 +x^2*(x^2-x-1)\\
 +2x*(x^2-x-1)\\
 +3*(x^2-x-1)\\
 +(5x+3)

数列

a_5=\\
(a_5-a_4-a_3)\\
 +(a_4-a_3-a_2)\\
 +2(a_3-a_2-a_1)\\
 +3(a_2-a_1-a_0)\\
 +(5a_1+3a_0)

というわけで、なんと多項式の次数と添え字の部分がちょうど対応していることがわかる。
説明は省略するが、これはいつでも成り立つことがわかり、結局数列の場合も多項式剰余を求める問題に帰着できることになる。
これが最も本質的な部分。


多項式剰余と繰り返し二乗法
繰り返し二乗法というテクニックを既知とする。
問題:f(x)多項式とし、その次数をNとしておく。x^K \mod f(x)を求めよ
(今までの例では、f(x)=x^2-x-1であり、N=2
多項式乗算を普通にやってO(N^2)
掛け算により2N次くらいの多項式となるが、x^N以上の次数の項については高次の項から順に次数下げを適用していくことでO(N^2)で適切な次数まで落とせる。
これをO(\log K)回やるので、全体ではO(N^2 \log K)


ウィニングラン
ここまでの説明で次の問題が解けたことになる。
問題:かくかくしかじかの線形漸化式で与えられる数列がある。a_Ka_0,\ldots,a_{N-1}を用いて表せ
ということで、後は初期値として与えられているa_0,\ldots,a_{N-1}の値を代入するとめでたくa_Kを得ることができる。


○例題
問題:a_0=1,\ a_1=3,\ a_{n+2}=a_{n+1}+2a_nという漸化式で与えられる数列がある。a_{12}を求めよ
回答:
 f(x)=x^2-x-2とおく。 x^{12} \mod f(x)を求める。

x^2 \equiv x+2\\
x^4 \equiv (x+2)^2=x^2+4x+4\equiv 5x+6\\
x^8 \equiv (5x+6)^2=25x^2+60x+36\equiv 85x+86\\
x^{12} \equiv (85x+86)(5x+6)=425x^2+940x+516 \equiv 1365x+1366
よって
a_{12}=1365a_1+1366a_0=1365*3+1366*1=5461


○高速きたまさ法
(この部分は筆者が正確な理解をしていないため、間違いがあれば指摘してください)
O(N^2)かかっている2つの部分について、次のテクニックを導入することで高速化できる。
FFT多項式の積をO(N \log N)で求める
モンゴメリ乗算:2N次の多項式の剰余をO(N \log N)で求める
これにより全体でO(N \log N \log K)となる。