2016-12-04

yukicoder No.445 得点

定義式に従って実装するだけ……
と思わせて、小数で誤差が発生する場合がある（challengeケースを参照）
そういうわけで、小数を使わないように、式をちょっと変形する
$\left \lfloor \frac{ 50 N }{ 0.8+ 0.2K} \right \rfloor=\left \lfloor \frac{ 250 N }{ 4+K} \right \rfloor$

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	printf("%d",50*n+250*n/(4+k));
	return 0;
}

50*nのところを分数に押し込んでも長さは変わらなかった

n;main(k){scanf("%d%d",&n,&k);n=!printf("%d",50*n+250*n/(4+k));}
n;main(k){scanf("%d%d",&n,&k);n=!printf("%d",50*n*(9+k)/(4+k));}

64B

2016-12-04

yukicoder No.442 和と積

問題はこちら
No.442 和と積 - yukicoder

A*Bが64bitに収まらないので、多倍長を持ち出すか、なんか考えないといけない
D=gcd(A,B)とし、A=Da、B=Dbとする。ここでa,bは互いに素となる。
gcd(A+B,AB)=gcd(D(a+b),DDab)=D*gcd(a+b,Dab)
であり、a,bが互いに素であることからa+bとabは互いに素
（なぜなら、abの任意の素因数pはa,bのちょうど一方のみを割り切るので、a+b mod pは0+非0より非0、すなわちa+bはpを因数に持たない）
よってDabのうち、a+bと1より大きな共通因数を持ちうるのはDの部分のみなので、gcd(a+b,Dab)=gcd(a+b,D)
これにより、64bitの範囲で計算できることがわかった。

あとは実装するだけ

long gcd(long p,long q){return q?gcd(q,p%q):p;}

int main(){
	long a,b,d;
	scanf("%ld%ld",&a,&b);
	d=gcd(a,b);
	printf("%ld",d*gcd(a/d+b/d,d));
	return 0;
}

適当に縮める

long g(long p,long q){return q?g(q,p%q):p;}
long a,b,d;
main(){
	scanf("%ld%ld",&a,&b);
	a=!printf("%ld",d*g(a/d+b/d,d=g(a,b)));
}

123B
いい感じの短縮が思いつかない

2016-12-03

yukicoder No.450 ベー君のシャトルラン

問題はこちら
No.450 ベー君のシャトルラン - yukicoder

２台の電車がすれ違うまでの時間をTとする。
ベー君は速度wで時間Tだけ移動するので総移動距離は明らかにwT。
T=d/(vl+vr)であることから直ちに計算できる。

int main(){
	double vl,vr,d,w;
	scanf("%lf%lf%lf%lf",&vl,&vr,&d,&w);
	printf("%f",w*d/(vl+vr));
	return 0;
}

ぎゅ

a,b,d;main(float c){d=scanf("%d%d%f%d",&a,&b,&c,&d)>printf("%f",c/(a+b)*d);}

76B

余談：
「フォンノイマンの逸話として有名なやつだ」と思ったのだけど、信頼に足る出典にたどり着けず
「フォンノイマン　等比級数」などで検索すると、話題自体は散見される

2016-12-03

yukicoder No.441 和か積

問題はこちら
No.441 和か積 - yukicoder

場合分けをすれば簡単に分かる。
必要ならAとBを入れ替えることでA≦Bと仮定して良い
・Aが0のとき
　Bも0なら'E'、さもなくば'S'
・Aが1のとき
　必ず'S'
・Aが2のとき
　Bも2なら'E'、さもなくば'P'
・Aが3以上のとき
　必ず'P'

Cでは200桁の整数を受け取るのは難しい。
上の場合分けを見ると、AもBも「3以上」はまとめて扱って良いことに気づく。
つまり、値が3以上ならそれを3に置き換えても結果に影響しない。
（上のように厳密に場合分けしなくても、例えば「値が10000以上なら10000に置き換えても和と積の大小関係は変わらなくない？」というのはイメージできると思う）

ということで、次のようにできる

int main(){
	char s[300];
	int a,b;
	scanf("%s",s);
	a=strlen(s)>1?9:atoi(s);//2桁なら9にしてしまう
	scanf("%s",s);
	b=strlen(s)>1?9:atoi(s);//同上
	if(a*b==a+b)putchar('E');
	else if(a*b>a+b)putchar('P');
	else putchar('S');
	return 0;
}

この方針のまま縮めるとこう

char s[999];
a;
main(b){
	scanf("%s ",s);
	a=strlen(s)>1?9:*s-48;
	b=strlen(gets(s))>1?9:*s-48;
	a=!putchar(a*b-a-b?a*b<a+b?83:80:69);
}

でもstrlenは長いし、getcharかreadでいい感じにやりたい
とりあえずぱっと思いつく簡単なやつ

#define f(x)for(;(t=getchar())>32;x=x?9:t-48);
//a,bは最初は0。先頭の桁を保存した後、もし2桁目以降があれば9に書き換える
a,b;
main(t){
	f(a);
	f(b);
	a=!putchar(a*b-a-b?a*b<a+b?83:80:69);
}

これをぐっと睨んでdefineをどうにかすると

t,a,b;
main(i){
	for(;read(0,&t,1);t>32?b=b?9:t-48:i--?a=b,b=0:0);
	a=!putchar(a*b-a-b?a*b<a+b?83:80:69);
}

このようになる。
ところで最後の条件式はa*b-a-b=(a-1)*(b-1)-1であることから、a,bに実際の数より1小さな値が入るように予め調整しておけば次のように短くできる

putchar(a*b-a-b?a*b<a+b?83:80:69);
putchar(a*b-1?a*b<1?83:80:69);

さらに、readをfor文の終了条件にしていると、returnがいい感じになるような気がしたので、最後の代入も省略して

t,a,b;main(i){for(;read(0,&t,1);t>32?b=b?9:t-49:i--?a=b,b=0:putchar(a*b-1?a*b<1?83:80:69));}

92B

2018/01/24追記
よくみるとこれは嘘解法。
例えば「12 2」などで落ちる。
修正してもよいが、じつは愚直解のほうがよほど短くなる。

double a,b;
main(){
	scanf("%lf%lf",&a,&b);
	putchar(a-b||(a&&a-2)?a*b>a+b?80:83:69);
}

81B
これが上手く動作することの証明には、丸め誤差の取扱などに熟知している必要がある。面倒くさいのでここでは省略するが、このプログラムは常に正しい値を返す。
しかし、一見同じ動作をするようにみえる次のコードはそうではない。

double a,b;
main(){
	scanf("%lf%lf",&a,&b);
	putchar(a-b||(a&&a-2)?a*b<a+b?83:80:69);
}

aが十分大きな値であり、b=1のとき、a+bは情報落ちによりaとなってしまう。

2016-11-07

yukicoder No.437 cwwゲーム

No.437 cwwゲーム - yukicoder

dfsするだけ
Nの桁数は高々13なので、適当にやってもどうにかなる

#define max(p,q)p<q?p=q:0
char s[99];

//今まで使った数を引数とし、残りの数で作れる最大の値を返す関数
int f(used){
	int i,j,k,t,m=0;
	for(i=0;s[i];i++)for(j=i+1;s[j];j++)for(k=j+1;s[k];k++){
		if(used>>i&1||used>>j&1||used>>k&1||s[i]=='0'||s[i]==s[j]||s[j]!=s[k])continue;
		//選んだ3つの数字が使用済みだったり、cww数にならないときはダメ
		t=(s[i]-'0')*100+(s[j]-'0')*10+s[k]-'0'+f(used^1<<i^1<<j^1<<k);
		//そうでないなら、こうしてできたcww数と残りで作れる最大値の和を調べる
		max(m,t);
	}
	return m;
}

int main(){
	gets(s);
	printf("%d",f(0));
	return 0;
}

縮める
fの引数を「使った数」ではなく「残った数」にすると少し短くなる

char s[99];
f(u,i,j,k,m){
	for(i=m=0;s[j=i];++i)for(;s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&s[i]!=48&s[i]!=s[j]&s[j]==s[k]?m=fmax(m,(s[i]-48)*100+(s[j]-48)*10+s[k]-48+f(u^1<<i^1<<j^1<<k)):0;
	//s[j]==s[k]などの真偽値を返す項があるので、u>>i&1の&1を省略することが出来る
	return m;
}
x;main(){gets(s);x=!printf("%d",f(-1));}

s[i],s[j]が何度も登場するのでこれは適当な記号で置くことにする
(s[i]-48)*100+(s[j]-48)*10+s[k]-48の計算部分では、s[j]==s[k]になっていることを利用しつつ短くまとめる

char s[99];
f(u,i,j,k,m,p,q){
	for(i=m=0;p=s[j=i];++i)for(;q=s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&p!=48&p!=q&q==s[k]?m=fmax(m,p*100+q*11-5328+f(u^1<<i^1<<j^1<<k)):0;
	return m;
}
x;main(){gets(s);x=!printf("%d",f(-1));}

mainの部分は、getsをfの引数に押し込める
またp!=48の部分は、pの値が48～57のいずれかであることから、p>48と書ける

char s[99];
f(u,i,j,k,m,p,q){
	for(i=m=0;p=s[j=i];++i)for(;q=s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&p>48&p!=q&q==s[k]?m=fmax(m,p*100+q*11-5328+f(u^1<<i^1<<j^1<<k)):0;
	return m;
}
x;main(){x=!printf("%d",f(~!gets(s)));}

最後に配列サイズをごまかして完成

char s[99];
f(u,i,j,k,m,p,q){
	for(i=m=0;p=s[j=i];++i)for(;q=s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&p>48&p!=q&q==s[k]?m=fmax(m,p*100+q*11-5328+f(u^1<<i^1<<j^1<<k)):0;
	return m;
}
x;main(){x=!printf("%d",f(~!gets(s)));}

210B

メモ

yukicoderでゆるふわgolf

yukicoder No.445 得点

yukicoder No.442 和と積

yukicoder No.450 ベー君のシャトルラン

yukicoder No.441 和か積

yukicoder No.437 cwwゲーム