ICPC 2017 Domestic : F リボンたたみ

問題文

https://storage.googleapis.com/icpcsec/icpc2017-domestic/contest/all_ja.html#section_F

概要

細長いリボンを  N 回畳む操作を行う.この時畳む方向を選択することができる(左から右を L,右から左を R とする).  N 回畳むと  2^{N} 個マスができる.ある特定のマスにマークを付けるとする. 初期状態のマークの場所と最終状態のマークの場所が与えられるので,それらから畳んだ方向の系列を求めるというもの.

解法

各マスを  (x, y) で表す.また,次のような座標系で話を進める.

 k 回目の畳む操作の時は, 2^{n-k} \times 2^{k} のマスとなる.

f:id:t-tatsukawa:20170718102419p:plain

題意より,最終状態の  (x_n, y_n) = (0, y) が与えられる.ここから L と R の操作を戻すことによって得られる  n-1 回目の畳む操作の状態を考える. このとき,L と R の y 座標の値は等しくなる.これは, k 回目の状態に関しても同じことが言える.感覚としては以下の図のような感じになる.

f:id:t-tatsukawa:20170718102428p:plain

さて, k 回目の畳む操作によるマーク座標の遷移について考える. 畳んだ後は一番左下のマスが  (0, 0) となるように移動させる.

これは以下のような場合分けで考えることができる. 操作前のマークの位置を  (x_k, y_k) とする.

  1.  2^{n-k-1} > x_k のとき
    • 操作 L:
      • x_{k+1} = 2^{n-k-1} - x_k - 1
      • y_{k+1} = 2^{k} + (2^{k}-y_k)
    • 操作 R:
      • x_{k+1} = x_k
      • y_{k+1} = y_k
  2.  2^{n-k-1} \leq x_k のとき
    • 操作 L:
      • x_{k+1} = x_k-2^{n-k-1}
      • y_{k+1} = y_k
    • 操作 R:
      • x_{k+1} = 2^{n-k}-x_k-1
      • y_{k+1} = 2^{k}+(2^{k}-y_k)

先程述べた y 座標の場所が変わらないということが遷移式からも分かる.

現時点でのマークの x 座標, y 座標の値と次の y 座標の値が分かれば LR の選択が決定する.

よって,最初に y座標の値を後ろから求め,初期状態  (x_0, y_0) = (x, 0) から順番に  (x_k, y_k) を更新しながら LR を求めれば良い.

ソースコード

実際に提出してないので間違っている可能性はあることに注意.

入手力データが更新されたので検証して正しい解が得られることを確認した.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    int64_t x, y;

    while (cin >> n >> y >> x)
    {
        if(x == 0 and y == 0) {
            break;
        }

        x--, y--;

        int64_t x_l = 1LL;
        int64_t y_l = 1LL;

        for (int i = 0; i < n; i++)
        {
            y_l *= 2LL;
            x_l *= 2LL;
        }

        vector<int64_t> Y(n + 1);
        Y[n] = y_l - y - 1LL;

        for (int i = n - 1; i >= 0; i--, y_l /= 2LL)
        {
            if (y_l / 2LL > Y[i + 1])
            {
                Y[i] = Y[i + 1];
            }
            else
            {
                Y[i] = y_l - Y[i + 1] - 1LL;
            }
        }

        for (int i = 0; i < n; i++, x_l /= 2LL)
        {
            if ((x_l / 2LL) > x)
            {
                if (Y[i + 1] == Y[i])
                {
                    cout << "R";
                }
                else
                {
                    cout << "L";
                    x = x_l / 2LL - x - 1LL;
                }
            }
            else
            {
                if (Y[i + 1] == Y[i])
                {
                    cout << "L";
                    x = x - x_l / 2LL;
                }
                else
                {
                    cout << "R";
                    x = x_l - x - 1LL;
                }
            }
        }

        cout << endl;
    }
}

所感

こういう考察系が苦手なので解いた.

とりあえず一番弱いサンプルの遷移図を書いて考えるが,  O(2^{N}) の解法ばかり浮かんできてそこから進まなかった. そもそもリボンを折った時の各マスの状態すら間違えるし酷すぎる.

規則性もいくつか見つけたが上手く使うことができず.

初期状態 → 終了状態 から制約を付けることが難しいなぁと思う.y の偶奇によって x の値が変わるのでそれを使うのかな?というところまで分かったがそこから進まず.

考察系問題集とかが欲しい.