AtCoder ARC #122 (東京海上日動 プログラミングコンテスト2021) : C - Calculator

賞金対象外だったけど、1ページ目にはどうにか入れたので良かった。
https://atcoder.jp/contests/arc122/tasks/arc122_c

問題

2つの変数x,yがあり、初期値はいずれも0である。

• 片方をインクリメントする
• 片方を片方に足しこむ

を繰り返し、130手以内で入力Nに対しx=Nの状態にせよ。

解法

以下のコードでは、Nを黄金比前後でx,yに分け、後者の手順を巻き戻す(大きい方から小さい方を引く)ことを繰り返し、片方が0になったら、残りはインクリメントを巻き戻すということを行った。
黄金比は何となくフィボナッチ数列を意識したのだが、乱数でも通るらしい？

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	double phi=(1+sqrt(5))/2;
	ll A=N/(1+phi),B=N-A;
	
	for(i=-3000;i<=3000;i++) {
		ll X=A+i;
		ll Y=B-i;
		if(X<0||Y<0) continue;
		vector<int> V;
		V.push_back(3);
		while(X && V.size()<=130) {
			if(X>=Y) {
				V.push_back(3);
				X-=Y;
			}
			else if(X<Y) {
				V.push_back(4);
				Y-=X;
			}
		}
		if(Y+V.size()>130) continue;
		FOR(i,Y) V.push_back(2);
		reverse(ALL(V));
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v<<endl;
		return;
	}
	assert(0);
}

まとめ

通りはしたけど、余りいいアプローチじゃなかったな。