コード量は割と少ない。
http://code-festival-2014-final-open.contest.atcoder.jp/tasks/code_festival_final_j
問題
水がAリットル入るカップとBリットル入るカップがある。
初期状態で両カップは空である。
１回の処理で以下のいずれかを実行できる。
- いずれかのカップを空にする
- いずれかのカップを満タンにする
- 片方のカップからもう片方のカップに水を移す。その際、渡す側のカップが空になるか、渡される側が満タンになるまで移す。
K回の処理で、両カップに残せる水は何通りあるか。
解法
Editorialを見て回答。
まず前提として、K==0の時は答えは1で確定である。
またA,Bは公約数で割って互いに素な状態にしておき、かつA＞Bとする。
詳細はEditorialに記載されているとおり、最初の１手でどちらのカップに水を満タンに入れるかは２択だが、それ以外は未出の状態に移行しようとすると常に処理は一択である。
あとは最初１つ目のカップに水を入れた場合と、２つ目のカップに水を入れた場合、K回の処理で何個新規の数値が登場する状態に入るか求めればよい。
K回の処理から新規の数値の数を直接求めることは難しいが、逆に新規数値の数から処理回数を求めることは(Editorialにあるとおり)可能なので、結局二分探索でK回の処理で登場する新規数値の個数を求められる。
Kが無限に大きければ0～Aの(A+1)通りの水の量を再現できる。
あとは最初の遷移２通りについてそれぞれの遷移可能な新規数値の和を求め、(A+1)と小さい方を答えればよい。
なお、新規数値の数と処理回数についてEditorialでは不十分なので若干補足。
1手目をBリットルのカップに水を入れた場合、N個の数値を出すのに必要な処理数はEditorial通り
- N==1なら1
- [N*B/A]==[(N-1)*B/A]なら2N+2[N*B/A]
- [N*B/A]!=[(N-1)*B/A]なら2N+2[N*B/A]-2
となる。
では逆に１手目をAリットル入れる場合だが、実はこれは以下の通り２手少なくて済む。
- N==1なら1
- [N*B/A]==[(N-1)*B/A]なら2N+2[N*B/A]-2
- [N*B/A]!=[(N-1)*B/A]なら2N+2[N*B/A]-4
基本的に１個数値を増やすのには２手かかるが、こちらのケースは２手目で状態が１個増えるため、全体で前者より２手少なくなる。
なお、N*B/Aの計算過程で64bit値からあふれるので注意。
ll A,B,K;
ll pata,patb;
ll move(__int128_t num) {
if(num==1) return 1;
return 2*(num+num*B/A-(num*B/A!=(num-1)*B/A));
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>A>>B>>K;
ll g=__gcd(A,B);
A/=g; B/=g;
if(A<B) swap(A,B);
if(K==0) return _P("1\n");
for(i=40;i>=0;i--) if(move(pata+(1LL<<i))<=K) pata += 1LL<<i;
for(i=40;i>=0;i--) if(move(patb+(1LL<<i))-2<=K) patb += 1LL<<i;
cout << min(pata+patb,A)+1 << endl;
}
まとめ
終わってみるとかなり回答がシンプルな問題だな…。
