Mister雑記

競プロやります。

AGC012-C 「Tautonym Puzzle」 (1000)

方針が明後日の方向へ。

概要

ある空でない文字列 yによって yyと表せるような文字列を「良い文字列」と呼ぶことにする。

このとき正整数 Nが与えられるので、以下を満たす文字列 Sを1つ出力せよ。

  •  |S| \leq 200
  •  Sは1から100で表される100種の文字からなる。
  •  2^{|S|}個ある Sの部分文字列のうち、良い文字列はちょうど N個ある。

制約

  •  1 \leq N \leq 10^{12}

解説

方針その1

まず考えたのが「1を K個並べた文字列の部分文字列で、良い文字列はいくつか」。 K個の中から偶数個を選ぶパターン数なので \sum_{i=1}^{K/2} {}_{K}C_{2i}となるが、これは 2^{K-1}-1に等しい1

それでは同じ数字を並べて Nをどんどん減らしていけばいいかというと、これが制約上上手くいかない。 10^{12} \simeq 2^{40}なので最大40回くらい操作を繰り返す必要があり、最終的な文字列長は最悪800くらいになってしまう。

方針その2

その後も色々と置き方を考えたがどれも上手く行きそうにないので、例によってeditorialを見ることに。

editorialの方針はこう。

 1 \sim Nの順列 (p_1, \dots, p_N)について、 S = (p_1, \dots, p_N, 1, \dots, N)について考える。 このとき、 pの部分列で単調増加なものの個数がそのまま良い部分文字列の個数になる。

ここで「なるほど〜」となって、以下のような解法を作った2

  •  N \lt 100なら S = (N, \dots, 1, 1, \dots, N)が条件を満たすのでこれを出力。
  • そうでない場合、 S = (100, \dots, 1, 1, \dots, 100)の前半部分の一部区間を引っくり返すことを考える。
  • このとき引っくり返した区間の長さを Lとおくと、単調増加部分列の数は 2^L - L - 1個増える。
  • あとはこれにしたがって、区間をひっくり返しつつ Nを減らしていく。

しかしこの解法、最終的にひっくり返す区間が足りなくなってしまうので残念ながらアウト。

方針その3(editorial)

このままではまたしても埒が明かなくなるので、諦めてeditorialを全文読むことにした。

editorialの全体的な方針は以下の通り。

  •  (1, \dots, L, 1, \dots, L)の良い部分文字列の数は 2^L - 1なので、 2^L - 1 \leq Nを満たす最小の Lについてこの文字列を作る。
  • この文字列の i i + 1の間と末尾に L + 1を挿入すると、良い部分文字列の数は 2^i増える。
  • あとはいい感じに後ろから L + 1を挿入かつ Lを更新していって、 Nを減らしていけばOK

2行目の操作が変態すぎる。成り立つことはわかるけど、思いつくのは無理。NP問題。

実装例

editorialに実装例までついていたので、概ねその通りに実装しただけ。

#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

int main() {
    ll N;
    cin >> N;

    ll len = 0;

    for (ll i = 0; i < 50; ++i) {
        if ((1LL << i) - 1 <= N) continue;
        len = i - 1;
        N -= (1LL << len) - 1;
        break;
    }

    // まずは(1, 2, ..., len)を作る
    vector<ll> p(len);
    for (ll i = 0; i < len; ++i) {
        p[i] = i + 1;
    }

    // len+1を適宜追加していく
    for (ll i = len; i >= 0; --i) {
        if ((1LL << i) <= N) {
            // iとi+1の間にlen+1を追加
            p.insert(p.begin() + i, ++len);
            N -= (1LL << i);
        }
    }

    cout << len * 2 << endl;

    // 前半は作った1~lenの順列
    for (ll n : p) {
        cout << n << " ";
    }

    // 後半は1~lenの昇順列
    for (ll i = 1; i <= len; ++i) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

1LL << iLLつけ忘れには気をつけよう( N敗)。

感想

  • さすがは1000点問題。解いてる間は点数は見えなかったが、点数を見て却って安心した。
  • しかしこの問題も結局は 2^iによる構築問題なわけで、その辺は典型と言える。
    • まぁ 2^iの効率的な構築方法が全然浮かばないわけだが。
  • editorialを見るタイミングがやはり難しい。今回は構築ということで粘りすぎた。

追記: rngさんの解法

他の解説記事を見て回ったら、rngさんの解説放送での解法がeditorialと違うとのことで放送を見てきた。 その方針が以下の通り。

  • 方針2,3と同様に、単調増加部分列の数を Nに一致させるよう順列を構築する。
  •  (1, \dots, N)の順列 pについて、単調増加部分列の数が K個であるとき、以下の2つの操作を考える。
    1. 先頭に N + 1を追加する。
    2. 末尾に N + 1を追加する。
  • それぞれの操作によって、単調増加部分列の数は K + 1個、 2K + 1個になる。
  • あとはダブリングの要領で文字を追加していけばいい。

個人的にはこちらの解法の方が発想としてより自然で好き。それでも気づくのは十分難しいけど。

実装は以下の通り。

#include <deque>
#include <iostream>
#include <tuple>

using namespace std;

using ll = long long;

// (追加した文字, 構築された文字列)を返す
pair<ll, deque<ll>> rec(ll N) {
    ll n;
    deque<ll> ret;

    if (N == 1) {
        ret = {1};
        return make_pair(1, ret);
    }

    if (N % 2 == 1) {
        tie(n, ret) = rec(N / 2);
        ret.push_back(++n);
    } else {
        tie(n, ret) = rec(N - 1);
        ret.push_front(++n);
    }

    return make_pair(n, ret);
}

int main() {
    ll N;
    cin >> N;

    deque<ll> ans = rec(N).second;

    cout << ans.size() * 2 << endl;

    // 前半は作った1~lenの順列
    for (ll n : ans) {
        cout << n << " ";
    }

    // 後半は1~lenの昇順列
    for (ll i = 1; i <= ans.size(); ++i) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

実装がとても軽くて良い。

あとなぜか「tie()という関数は存在しません」という普段出ないCEが出たので#include <tuple>をしておいた。なぜ今まで出なかったのだろう。


  1. これは受験数学における一種の典型で、2項定理で証明できる。 (1+1)^K (1+(-1))^Kを足してみよう。

  2. この解法は多分ARC091-E「LISDL」の影響から来ている。まだ解けてないけど。