Mujin Contest D - うほょじご

問題文

D - うほょじご

解く前に考えていたこと

・絶対これ考察するだけでしょｗと思ってたら違った。
・規則性を見出すことが全くできなかった。シュミレーションの選択肢を除外した。

正解

・解答を見ると閉路を探し出すような解答になっていたが、わからなかったのでメモ化再起で解いた。
・なので、2次元配列で状態を持てる。
・無限ループに突入する部分の判定が勉強になった。

if(visit[x][y] > 0) return true;
        if(visit[x][y] < 0) return false;
        int tx = x,ty = y;
        visit[x][y] = true;
        x < y ? x = rev(x) : y = rev(y);
        x < y ? y = y - x  : x = x - y;
        if(x <= 0 or y <= 0){
            visit[tx][ty] = -1;
            return false;
        }
        visit[tx][ty] = (dfs(x,y) ? 1 : -1);
        return visit[tx][ty] == 1;

まず、に対し、に1を一時的に格納する。
に対して操作を行った後、閉路に突入する（つまり、に戻ってくる）と、格納されている1が帰る。
そうでない場合は途中で-1に更新され、その組は解になりえない事がわかる。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll

using namespace std;
int rev(int num){
    auto s = to_string(num);
    reverse(begin(s),end(s));
    return stol(s);
}
signed main(){
    int n,m;
    cin >> n >> m;
    int ans = 0;
    vector<vector<int>>visit(1000,vector<int>(1000,0));
    function<bool(int,int)> dfs = [&](int x, int y) -> bool{
        if(visit[x][y] > 0) return true;
        if(visit[x][y] < 0) return false;
        int tx = x,ty = y;
        visit[x][y] = true;
        x < y ? x = rev(x) : y = rev(y);
        x < y ? y = y - x  : x = x - y;
        if(x <= 0 or y <= 0){
            visit[tx][ty] = -1;
            return false;
        }
        visit[tx][ty] = (dfs(x,y) ? 1 : -1);
        return visit[tx][ty] == 1;
    };
    for(int i = n; i >= 1; --i){
        for(int j = m; j >=1;--j){
            ans += dfs(i,j);
        }
    }
    cout << ans << endl;
}