メモ

yukicoderでゆるふわgolf

yukicoder No.700 LOVE

問題はこちら
No.700 LOVE - yukicoder

strstrという便利な関数があるのでそれを使うだけ

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 a[99];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<n;i++)for(int j=1;j<n;j++)if(a[j-1]>a[j])swap(a[j-1],a[j]);
	int s=0;
	for(int i=0;i<n;i++)s+=abs(a[i]-(i+1));
	printf("%d",s);
}

バケツソートを使うかバブルソートを使うかは悩みどころだが、バケツソートの方が短くなりそうな気がしたのでそれで実装
バブルソートの方は試してない

これを

a[99];
n,t,s,i,k;
int main(){
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&t);
		a[t]++;
	}
	for(int i=0;i<n;i++){
		while(a[k]==0)k++;
		s+=abs(k-(i+1));
		--a[k];
	}
	printf("%d",s);
}

こうじゃ

a[99],i,s;
main(k){
	for(;~scanf("%d",a)?++a[*a]:a[k]--?s+=abs(k-++i),1:++k<60;);
	printf("%d",s-1);
}

nもまとめて読み込んで、ループをn回ではなく十分大きな定数回実行している。このため答えが1ずれるので引いている。
入力の読み込みにa[0]を使うことで一時変数を削減している。(+1B-2Bで1B削減)
96B

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

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





追記
全部隣接代数 (順序理論) - Wikipediaに書いてました。ちゃんちゃん
追記終わり





○ゼータ変換・メビウス変換とは
Gを可換順序群、R可換環とする。
このとき、\{f:G^+\to R\}への作用素\zetaを、\displaystyle{(\zeta f)(x)=\sum_{0 \leq y\leq x}f(y)} により定める。
これをゼータ変換という。
もし\zeta\mu= \epsilonとなる\muが存在すれば、ゼータ変換には逆変換が存在し
\displaystyle{(\zeta^{-1} f)(x)=\sum_{0 \leq y\leq x}\mu(y)f(x-y)} となる。これをメビウス変換という。
ただし\
\epsilon(x)=\begin{cases}
    1 & (x=0) \\
    0 & (\text{otherwise})
  \end{cases}
である。


式の形を見れば分かる通り、これらは畳み込み積の計算であり、\zeta f=1*fである。
G=R=\mathbb{R}の場合などをイメージしてみよ)
\epsilonは畳み込みにおける単位元であり、1*\mu=\epsilonであるから、\muは定数関数1の畳み込みにおける逆元である。
このことから\mu*(\zeta f)=\mu*(1*f)=(\mu*1)*f=fにより、逆変換ができることが確かめられる。



は?



○競プロでよく見るやつ
・高速ゼータ変換
集合Xがあり、べき集合上の関数f:P(X)→Rがある。
\displaystyle{g(S)=\sum_{T\subset S}f(T)}を高速に求める
・高速メビウス変換
集合Xがあり、べき集合上の関数f:P(X)→Rがある。
\displaystyle{g(S)=\sum_{T\subset S}(-1)^{|T|}f(S\setminus T)}を高速に求める

「普通にやるとO(3^N)だけどO(N*2^N)でできるよ~」というやつ。
これは、べき集合P(X)を自然にG=\mathbb{Z}^Xへ持っていたと考えているようなもの(ほんとに?)
(もう少し仮定を弱めてGは群でなくてもよいのでは??)
※この例でいうとS\setminus Tのように、ある種の"差"が計算できる必要があると思っていたので、fの定義域を群にしたのだけど、wikipediaを見ると、区間を引数にとる関数だと思えばよかったらしい。なるほど



メビウスの反転公式
正整数上の関数f,gが
\displaystyle{g(n)=\sum_{d|n}f(d)}
を満たすとする。このとき
\displaystyle{f(n)=\sum_{d|n}\mu(d)g(n/d)}
が成り立つ。ただし\muメビウス関数

これはG=\mathbb{Q}^*/\{\pm 1\}\subset \mathbb{Z}^{\omega}に自然な順序x\leq y \iff y/x\in\mathbb{Z}を定めたものと言える



メビウス変換と包除原理
Uを集合とし、N個の集合A_i\subset Uがある。
X={1,...,N}とし、f:P(X)\to\mathbb{Z}
\displaystyle{f(S)=\left|\bigcap_{i\in S}A_i\right|} により定める。
\displaystyle{g(S)=\left|\bigcup_{i\in S}A_i\right|} とおくと、包除原理から
\displaystyle{
 \left|\bigcup_{i\in S}A_i\right|\\
=\sum_{\emptyset \neq T \subset S}(-1)^{|T|+1}\left|\bigcap_{i\in T}A_i\right|\\
=\sum_{\emptyset \neq T \subset S}(-1)^{|T|+1}f(T)\\
=\sum_{T \subset S}(-1)^{|T|+1}f(T)-f(\emptyset)\\
=(-1)^{|S|+1}\sum_{T \subset S}(-1)^{|S\setminus T|}f(T)-f(\emptyset)\\
=(-1)^{|S|+1}\sum_{T \subset S}(-1)^{|T|}f(S\setminus T)-f(\emptyset)\\
=(-1)^{|S|+1}(\zeta^{-1}f)(S)-f(\emptyset)\\
}
となる。
よってあらかじめf(\emptyset)を|U|ではなく|\emptyset|=0と定めておけば、g(S)=(-1)^{|S|+1}(\zeta^{-1}f)(S)となることが確かめられる。

yukicoder No.692 square1001 and Permutation 1

問題はこちら
No.692 square1001 and Permutation 1 - yukicoder

n=1かどうか判定するだけ

値を1つ見ればよいのでgets+atoiやるだけ

a;main(){puts(atoi(gets(&a)-1)?"Petr":"square1001");}

……と思ったら、scanfを使う方が短くなるらしい。
未定義動作だから何が起きてもいいとはいえ、値の評価順序はいったいどうなってるんだ……

main(n){puts(n-scanf("%d",&n)?"Petr":"square1001");}

52B

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;
	scanf("%ld%ld",&x,&y);
	puts(f(x,y)?"Yes":"No");
}

現実的には探索回数は十分小さくなるらしいが、ここでは√N以下になることを示す。
(この証明はwriterに教えていただいた)
(証明)
mod 4で考える。
X,Yがともに4の倍数であるとき以外は、遷移先が一意に決まることが分かる。
また、X,Yがともに4の倍数のときは
(00,00)→(00,11)→(00,10)→(00,01)→(00,00)
(00,00)→(10,11)→(01,10)→(00,01)→(00,00)
のどちらかの遷移をたどったときその時に限り、ともに4の倍数である状態に戻ってくる。
よって、探索の枝は深さ4毎に高々2倍になる。ここで深さ1ごとにXYは1/2より小さくなるので、探索の深さは高々log2(XY)≦2log2(N)。
探索回数は高々2^(2log2(N)/4)=√Nである。
(証明終わり)
なお実際には√N=10^9どころか、せいぜい10^3程度にしかならないようである

フラグの持ち方を少し工夫して

F;
f(long x,long y){
	x&&y?x%2||f(x/2,y-1),y%2||f(x-1,y/2):F++;
}
main(){
	long x,y;
	scanf("%ld%ld",&x,&y);
	f(x,y);
	puts(F?"Yes":"No");
}

126B