mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #325 (Div. 1) C. Alice, Bob, Oranges and Apples

解法

Stern Brocot 木というのが元にあるようです。

実は, この操作は Stern Brocot 木の操作とそれぞれ対応しています。
まず, Alice がみかんを, Bob がりんごを最初に 1 個ずつ持ってる状態は Stern Brocot 木では (0/1, 1/0)(分数としては 1/1) を表します。また, このあとカード A を引くと, Stern Brocot 木では (1/1, 1/0) (分数としては 2/1) を表します。…というような感じです。

Stern Brocot 木は, 既約分数のみを表す, という性質があるので, まず x と y が互いに素でなかったらアウトです。この場合は Impossible を出力します。それ以外の場合は Stern Brocot 木で x/y を探索することになります。

仮に x > y であったとすると, まず最初は Stern Brocot 木の右側の部分木を選ぶことになります(1 より大きな分数にするにはそうするしかないので)。
この時分数の組は (1/1, 1/0) となります。この組から x/y を目指すのは, 実は (0/1, 1/0) から (x-y)/y を目指すのと同じになります。というのも, 最終的に (1/1, 1/0) の左側成分を a だけ, 右側成分を b だけ使うことによって x/y を得たとすると, a+b/a+0 = x/y となります。これを (0/1, 1/0) に当てはめると 0+b/a+0 = (a+b)-a/a = x-y/y となります。ということで, 右に動いたら今度は (0/1, 1/0) から (x-y)/y を目指せば良いです。

同様に, x < y の時は 左に動いて x/y-x を目指す感じになります。

これは結局 ユークリッドの互除法的に x, y を動かすことになるので, O(log N) 以下で解けます。

ここで示したような議論で, 多分 Stern Brocot 木に現れる分数がすべて既約分数であることが示せるんじゃないかなぁと思います。

int main() {
    ll x, y;
    cin >> x >> y;
    ll g = __gcd(x, y);
    if (g != 1) {
        cout << "Impossible" << endl;
        return 0;
    }
    while (x > 1 || y > 1) {
        if (x < y) {
            ll tmp = max<ll>(1, y%x);
            ll num = (y-tmp)/x;
            y = tmp;
            cout << num << "B";
        } else {
            ll tmp = max<ll>(1, x%y);
            ll num = (x-tmp)/y;
            x = tmp;
            cout << num << "A";
        }
    }
    cout << endl;
    return 0;
}