yukicoder No.141 魔法少女コバ

問題はこちら
No.141 魔法少女コバ - yukicoder

逆から考える
a/b<1を作るためには最後の操作は逆数を取るしかない
a/b>1を作るための最後の操作が逆数を取るものだとしたら上のパターンに戻るだけなのでだめで、結局+1しかない
前者の操作をの直後には必ず後者の操作が行われ、後者の操作ではa+bの値は真に小さくなっていくので、これらの操作によりa/bはいずれ1になる
つまり任意のM/Nを作ることができる

ということでこれを愚直に実装すれば間に合う

int main(){
	int s=0,a,b,t;
	scanf("%d%d",&a,&b);
	while(a!=b){
		if(a<b){t=a;a=b;b=t;}
		else a-=b;
		s++;
	}
	printf("%d",s);
	return 0;
}

while文の中で、a>bの時は結局a<=bになるまで減算が行われるので、その回数を除算で求めることで複数回をまとめることができる
また、終了条件が面倒なのでちょっといじる

s,a,b;
main(t){
	scanf("%d%d",&a,&b);
	while(b){
		s+=a/b+1;
		t=a%b;a=b;b=t;
		//a<bになるまで(1)を使い、その後は必ず(2)を使うのでa/b+1回
	}
	s=!printf("%d",s-2);
}

これにより本来は(a,b)=(1,1)で終わるところが、(1,1)→(0,1)→(1,0)と余分な操作を2回しているので出力時に引く

この方針で縮めると

s,a,b;
main(t){
	for(scanf("%d%d",&a,&t);b=t;a=b)s+=a/b+1,t=a%b;
	s=!printf("%d",s-2);
}

82B
やってることは互除法なんだから、main再帰でも書けるのでは
そうすれば、scanfも1つにまとめられる？

s;
main(a,b){
	scanf("%d",&b);
	s=b?s+=a/b+1,main(b,a%b):!printf("%d",s-3);
	//入力時に(1,M)→(M,N)でsが+1されるので、上の2と合わせて計-3
}

サンプルは通るよしよし……と思ったら、M=1の時には最初の(1,M)→(M,N)で+2されてしまうので1ずれる
これは2Byte増やして解決

s;
main(a,b){
	scanf("%d",&b);
	s=b?s+=~-a/b+1,main(b,a%b):!printf("%d",s-2);
}

~-a/bは、a/b-!(a%b)に等しい（a,b>0のとき）
これにより、先程問題になっていた最初の部分はかならず+1に抑える事ができる
また最後にsに加算される値が1減るので、また出力が1ずれて-2となった

73B