Weak Goodstain Sequence

元ネタ

Large となるための条件

実は、$8\le N$ で Large となります。

解法1

愚直に実装します。オーバーフローに気を付けてください。
$A_i$ から $A_{i+1}$ を求めるときの計算量は $O(\log N)$ です。

解法2

全体を通して見ると、わざわざ $n$ 進数に変換することが無駄であるように見えます。
$-1$ の操作以外は全て基数に関する操作なので、数を桁ごとに配列で管理し、基数は別で管理すればよいです。

この解法ではオーバーフロー等を気にする必要はありません。
$A_i$ から $A_{i+1}$ を求めるときの計算量は $O(1)$ です。

解法2の実装例（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin >> N;

  vector<int> num(32, 0);
  int i = 0;
  while (N)
  {
    num[i++] = N & 1;
    N >>= 1;
  }

  for (int ans = 1; ans <= 1'000'000; ans++)
  {
    int j = 0;
    while (num[j] == 0)
    {
      j++;
      if (j == 32)
      {
        cout << ans << endl;
        return 0;
      }
    }
    num[j]--;
    while (j)
      num[--j] = ans + 1;
  }
  cout << "Large" << endl;
}

Bonus：$|A|$ を $998244353$ で割った余りを求めよ。

$A$ の長さが有限になることの証明のお気持ち

この証明では順序数 $\omega$ を用います。
$\omega^\omega$ 未満の順序数 $\alpha=\omega^n\alpha_n+\omega^{n-1}\alpha_{n-1}+\cdots\omega\alpha_1+\alpha_0$ について考えます。（ここで、$\alpha_k<\omega$）

$\alpha$ に対し、$f(\alpha,i)$ を $\alpha$ の $\omega$ を全て $i$ に置き換えた自然数とします。
（つまり、$f(\alpha,i)=\alpha=i^n\alpha_n+i^{n-1}\alpha_{n-1}+\cdots i\alpha_1+\alpha_0$）

$\alpha$ が有限の場合と無限の場合で場合分けすることで、$f(\alpha,i)\le\alpha$ を導くことができます。

次に、$\alpha_0\ne0$ のとき、つまり $\alpha$ が後続順序数であるとき、$i$ に関わらず $\alpha[i]=\omega^n\alpha_n+\omega^{n-1}\alpha_{n-1}+\cdots\omega\alpha_1+(\alpha_0-1)$ とします。
ここから、$\alpha[i]<\alpha$ を得ます。

以上を組み合わせ、以下のように順序数列 $B$ を定めます。

• $B_1$ は $f(\alpha,2)=N$ を満たす順序数のうち、$\alpha_n<2$ を満たす唯一の順序数
• $2\le i$ について、$B_i=g(B_{i-1},i+1)$

すると、$A$ と $B$ の間に、$A_i=f(B_i,i+1)$ という関係式が成り立ちます。
$B_{i+1}=g(B_i)<B_i$ から、$B$ は狭義単調減少列です。
順序数に無限降下列は存在しないので、$B$ は有限の長さで $0$ にたどり着きます。$A_i=f(B_i,i+1)\le B_i$ から、$A$ も有限回で $0$ にたどり着くことが分かりました。