うほょじご [ Mujin Programming Challenge 2018 D]

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_d

考察過程

1. 制約を見ると割と小さいので、シミュレートできそう
2. 操作を見てみるとかなりやばい操作をしているので、更にシミュレートしながら何かする感じが伝わる
3. メモ化すれば行けそう
4. サイクルが見つかったときに無限ループ判定ができるので、うまくメモ化をしていけば大丈夫

解説

https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947281

メモ化再帰というかdfsというかで解く。
サイクルが発生しうるdfsの場合はメモ化の場合に仮置きしておけば判定できる。
f(x,y) := (x,y)の場合に結果がどうなるか
=1：無限ループ
=2：停止
=3：未確定
revもメモ化再帰で実装しておこう。
stringとreverseあたりを使うと楽に実装できる。
関数fの中身は操作を実装するだけ。

int N, M;
//---------------------------------------------------------------------------------------------------
int rmemo[1010];
int rev(int x) {
    if (x == 0) return 0;
    if (rmemo[x]) return rmemo[x];
 
    string s = to_string(x);
    reverse(all(s));
    int res = 0;
    fore(c, s) res = res * 10 + c - '0';
    return rmemo[x] = res;
}
//---------------------------------------------------------------------------------------------------
int memo[1010][1010];
int f(int x, int y) { // =1:無限ループ =2:停止 =3:未確定
    if (memo[y][x]) return memo[y][x];
    memo[y][x] = 3;
 
    if (x == 0 or y == 0) return memo[y][x] = 2;
 
    int _x = x, _y = y;
 
    if(x < y) x = rev(x);
    else y = rev(y);
 
    if (x < y) y = y - x;
    else x = x - y;
 
    int nxt = f(x, y);
    if (nxt == 1) return memo[_y][_x] = 1;
    else if (nxt == 2) return memo[_y][_x] = 2;
    else if (nxt == 3) return memo[_y][_x] = 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    int ans = 0;
    rep(x, 1, N + 1) rep(y, 1, M + 1) if (f(x, y) == 1) ans++;
    cout << ans << endl;
}