読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.491 10^9+1と回文

問題はこちら
No.491 10^9+1と回文 - yukicoder

s<10^9に対して、s*(10^9+1)は、文字列としては「s,(いくつかの0),sを連結したもの」と一致する
これが回分数であることはsが回分数であることと同値
よって問題は「N/(10^9+1)以下の回分数の個数を求めよ」と読み替えられる。
対象となる数は高々9桁なので、5桁以下の数を元に回分数を構成し、それが求める範囲に入るかチェックすれば良い

#include <stdlib.h>
int main(){
	long n,len,ans=0;
	int i,j;
	char s[10];

	scanf("%ld",&n);
	n/=1000000001;
	for(i=1;i<100000;i++){
		sprintf(s,"%d",i);
		len=strlen(s);
		//1234->12344321
		for(j=len-1;j>=0;j--)s[len*2-1-j]=s[j];
		s[len*2]=0;
		if(strtoll(s,NULL,10)<=n)ans++;
		//1234->1234321
		for(j=len-2;j>=0;j--)s[len*2-2-j]=s[j];
		s[len*2-1]=0;
		if(strtoll(s,NULL,10)<=n)ans++;
	}
	printf("%d",ans);
	return 0;
}

ということで、これをざっくり書き換えてみる

long n,s;
//bを反転してaの後ろにくっつける関数。例えばf(1234,567)=1234765
f(a,b){return b?f(a*10+b%10,b/10):a;}
main(i){
	scanf("%ld",&n);
	//n/=1e9+1とすると、nがdoubleに変換されてしまい精度が足りない
	n/=1000000001;
	for(;i<1e5;i++){
		//iが5桁のとき、f(i,i)は10桁となりオーバーフローの可能性がある
		//nは9桁以下なのでこのケースは予め弾いてよい
		if(i<1e4&&f(i,i)<=n)s++;
		if(f(i,i/10)<=n)s++
	}
	printf("%d",s);
	//c11準拠になったのでreturn文を省略しても勝手に0を返してくれるようになったらしい
}

これをぎゅっとする

long n,x=1e9+1,s;
//sへの加算までfの中でやってしまう
f(a,b){!b?s+=a<=n:f(a*10+b%10,b/10);}
main(i){
	scanf("%ld",&n);
	for(n/=x;i<1e5;f(i++,i/10))i<1e4&&f(i,i);
	printf("%d",s);
}

135B


ちなみに上記プログラムは明らかにO(√N)だが、次のようにしてO(logN)で解くこともできる

//nの上半分を下半分に反転してコピーする。第2引数は次にコピーする桁
//f(1234567,10^6)=1234321、f(123456,10^5)=123321
f(n,t){return t>1?f(n%t/10,t/100)*10+n/t*(t+1):n;}

int main(){
	long n;
	int keta,temp,ans=0;

	scanf("%ld",&n);
	n/=1000000001;
	if(n==0){
		puts("0");
		return 0;
	}
	keta=log10(n)+1;
	ans=n/pow(10,keta/2)+pow(10,keta/2)-1;
	temp=pow(10,keta-1);
	if(f(n,temp)>n)ans--;
	printf("%d\n",ans);
}

次のような方法で計算している
1.N/1000000001をnとする。
2.nの桁数を求めketaとする(実際にはnが10べきのときに1ずれるが多分いい感じになっている)
3.keta桁未満の回分数の個数は
ketaが偶数のとき2*10^{keta/2}-2
ketaが奇数のとき11*10^{(keta-1)/2}-2で与えられる
(ちょうどk桁の回分数の総数が9*10^{\lfloor (keta-1)/2 \rfloor}であることからわかる)
4.簡単のためまずnが回分数である場合について考える
ちょうどketa桁の回分数でn以下のものの個数は、nの上半分の桁を見ればわかり、\frac{n}{10^{\lfloor keta/2 \rfloor}}-10^{\lfloor (keta-1)/2 \rfloor}+1
(例えばn=1234321なら、1234-1000+1=235個、n=12344321なら1234-1000+1=235個)
5.nが回分数でないときに同様に上半分だけを見て確認すると、例えばn=654321のときにはn=654456と同じ計算をすることになるので、余分な回分数が入ってしまわないか確認するためにf(n,*)とnの大小関係を見る

この方針で縮めると156Bとなり全然及ばない

long n,x=1+1e9;
f(n,t){x=t>1?f(n%t/10,t/100)*10-n/t*~t:n;}
main(m){
	scanf("%ld",&n);
	printf("%d",n=~(f(n,x=pow(10,m=log10(n/=x)))>n)+(m=pow(10,-~m/2))+1.*n/m);
}

yukicoder No.487 2017 Calculation(2017の計算)

問題はこちら
No.487 2017 Calculation(2017の計算) - yukicoder

modpow関数があればそれを使うだけ

#define ll long long
ll modpow(ll a,ll n,int m){return n?modpow(a%m*(a%m)%m,n/2,m)*(n&1?a%m:1)%m:1;}

int main(){
	int m;
	scanf("%d",&m);
	printf("%d",(2017+modpow(2017*2017,2017,m))%m);
	return 0;
}

modpowを持ち出さなくても、指数が小さいので、べき乗部分をfor文でやればよい

int main(){
	int m,i,s=1;
	scanf("%d",&m);
	for(i=0;i<2017;i++)s=s*2017*2017%m;
	printf("%d",(2017+s)%m);
	return 0;
}

(2017*2017)^2017を2017^(2017*2)と読み替えて

n=2017,m,i;main(s){
	for(scanf("%d",&m);i++<2*n;s=s*n%m);
	i=!printf("%d",(s+n)%m);
}

80B

yukicoder No.486 3 Straight Win(3連勝)

問題はこちら
No.486 3 Straight Win(3連勝) - yukicoder


strstr関数を使うのが一番素直だと思う

#include <string.h>
int main(){
	char s[110],*x,*o;
	gets(s);
	x=strstr(s,"XXX");
	o=strstr(s,"OOO");
	if(x==NULL&&o==NULL)puts("NA");//どっちも見つからない
	else if(x==NULL&&o!=NULL)puts("East");//OOOだけ見つかる
	else if(x!=NULL&&o==NULL)puts("West");//XXXだけ見つかる
	else if(x<o)puts("West");//両方見つかったがXXXの方が先
	else puts("East");//両方見つかったがOOOの方が先
	return 0;
}

この方針で縮めるとこう

char s[110];x,o;main(){
	gets(s);
	x=strstr(s,"XXX");
	o=strstr(s,"OOO");
	x=!puts(x|o?x<o^x*o?"East":"West":"NA");
}

ただし、x,oが32bit整数として大小比較をしてうまくいくかは怪しい(実際には提出していない)

まあstrstrなんて使わなくても、前からreadしていけばいいよね

f,s,b;main(c){
	for(;read(0,&c,1);){
		if(!f){//まだ勝者が決まっていなければ
			if(b==c){//今の勝者が前回の勝者と同じなら
				s++;//連勝数を1増やして
				if(s==3)f=c;//3になった勝ち
			}else{//違うなら
				s=1;//連勝数は1になる
				b=c;
			}
		}
	}
	s=!puts(f?b&1?"East":"West":"NA");
}

ぐっと睨むと、sが3以上かどうかを見ればfがいらないことがわかる

s,b;main(c){
	for(;read(0,&c,1);)s<3&&b-c?b=c,s=1:++s;
	s=!puts(s>2?b&1?"East":"West":"NA");
}

89B

yukicoder No.485 方程式のお勉強

問題はこちら
No.485 方程式のお勉強 - yukicoder

やるだけ
B%A==0のときかつそのときに限り整数解がある

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	if(b%a!=0)puts("NO");
	else printf("%d",b/a);
	return 0;
}

ぎゅ

a;main(b){scanf("%d%d",&a,&b);a=!printf(b%a?"NO":"%d",b/a);}

60B

yukicoder No.482 あなたの名は

問題はこちら
No.482 あなたの名は - yukicoder

「1~Nの置換が与えられたとき、その逆置換がちょうどK個の互換の積で書けるか判定せよ」という問題
まずは与えられた置換を最も少ない個数の互換の積で書くときの個数を考える
これは先頭から順に貪欲に交換していくことでわかる(互いに素な巡回置換の積に分解していることと本質的に同じ)
この個数をxとすれば、「x≦K かつ x≡K mod 2」がYESであるための必要十分条件であることが置換の偶奇性からわかる

int main(){
	long a[200010],k,x=0;
	int i,t,n;
	scanf("%d%ld",&n,&k);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	for(i=1;i<=n;i++)while(a[i]!=i){
		//a[i]とa[a[i]]をswap。後述
		t=a[i];
		a[i]=a[t];
		a[t]=t;
		x++;
	}
	puts(x<=k&&x%2==k%2?"YES":"NO");
	return 0;
}

上のプログラムでは次のような手順によってswapが行われていく

2 5 6 7 1 3 4
↓1番目に2があるので、これを正しい位置に置くために2番目とswapする
5 2 6 7 1 3 4
↓1番目に5があるので、これを正しい位置に置くために5番目とswapする
1 2 6 7 5 3 4
↓1番目に1があり、これは正しい位置
↓2番目に2があり、これは正しい位置
↓3番目に6があるので、これを正しい位置に置くために6番目とswapする
1 2 3 7 5 6 4
↓3番目に3があり、これは正しい位置
↓4番目に7があるので、これを正しい位置に置くために7番目とswapする
1 2 3 4 5 6 7
4,5,6,7番目が正しい位置にあることがそれぞれ確かめられるのでこれで完成


明らかにkを直接減らしていけばxはいらない。
また、kが-1になった時点でループを抜けることにすれば、「kが0以上かつ偶数か?」を「kが偶数か?」にまとめられるのでそのようにしようと考えながら縮めて

for(i=1;i<=n&&k>=0;i++)while(a[i]!=i)t=a[i],a[i]=a[t],a[t]=t,k--;
for(i=1;a[i]&&k>=0;)a[i]-i?t=a[i],a[i]=a[t],a[t]=t,k--:++i;
for(i=1;a[i]-i?t=a[i],a[i]=a[t],a[t]=t,~--k:a[++i];);

読み込みをいつも通り工夫して

long a[1<<18];j=1;
main(i){
	for(;~scanf("%ld",a-i--););
	for(;a[j]-j?i=a[j],a[j]=a[i],a[i]=i,~--*a?a[++j];);
	j=!puts(*a&1?"NO":"YES");
}

ループ圧縮

long a[1<<18],j=1;
main(i){
	for(;~scanf("%ld",a-i--)?:j-a[j]?i=a[j],a[j]=a[i],a[i]=i,~--*a:a[++j];);
	j=!puts(*a&1?"NO":"YES");
}

ポインタ

long a[1<<18],*p=a+1;
main(i){
	for(;~scanf("%ld",a-i--)?:p-a-*p?i=*p,*p=a[i],a[i]=i,~--*a:*++p;);
	*a=!puts(*a&1?"NO":"YES");
}

122B