*AOJ 1126: The Secret Number

問題

The Secret Number | Aizu Online Judge

タイルの中を右または下に進んで生成できる数字のうち最大のものを求めよ

方針

• 深さ優先探索で数を作っていく
• 普通にやったらTLEするのでC[y][x]からスタートして作れる最大の数字をmemo[y][x]に入れておく
• 最大70桁あるのでlong longでも足りない。string同士のmaxを返す関数を用意しておく

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

char C[71][71];
string memo[71][71];
int W, H;
bool isNum(char c) {
    if(c >= '0' && c <= '9') return true;
    else return false;
}
string max_str(string a, string b) {
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    return max(a, b);
}
string dfs(int y, int x) {
    if(memo[y][x] != "") return memo[y][x];
    if((y+1>=H || !isNum(C[y+1][x])) && (x+1>=W || !isNum(C[y][x+1]))) {
        memo[y][x] = C[y][x];
        return memo[y][x];
    }
    string ans = "";
    if(y+1<H && isNum(C[y+1][x])) ans = max_str(ans, C[y][x]+dfs(y+1, x));
    if(x+1<W && isNum(C[y][x+1])) ans = max_str(ans, C[y][x]+dfs(y, x+1));
    memo[y][x] = ans;
    return memo[y][x];
}

int main(void){
    while(cin >> W >> H && W) {
        rep(i, H) rep(j, W) {
            cin >> C[i][j];
            memo[i][j] = "";
        }
        string ans;
        for(int i=H-1; i>=0; --i) {
            for(int j=W-1; j>=0; --j) {
                if(isNum(C[i][j]) && C[i][j]!='0') {
                    ans = max_str(ans, dfs(i, j));
                }
            }
        }
        cout << ans << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1898703

反省

• メモ化する方針を自分で思いつかなかった（さすがにアホ）
• ttp://kengo92i.hatenablog.jp/entry/2014/08/29/181324 を見てメモ化の方針を知った
• メモ化した後もTLEが取れなかったが、これはmax_strに問題があった
• 001と02みたいな文字列を比較するときのことを考えて0を含まないsubstrを比較する……みたいなことをやっていたら遅すぎたらしい
• dfsを0から始めないようにすれば0であっても桁を1つ増やす効果があるから長い方が強いんですね。賢い。