Phone Number [Ritsumeikan University Competitive Programming Camp 2019 Day 2 C]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/C

解説

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp19Day2/3419010

方針としては、答えとしてあり得る盤面を全列挙する。
盤面は全部で9!通りなので、これは列挙できる。
　
次にある盤面で必要な移動回数を高速に求める手段であるが、
B[a][b] := aからbに移動するための移動回数
を予め計算することでO(N)で行える。
しかし、これでは遅いので、Sについて、
cnt[[a][b] := Sの中でaからbへの遷移が何個あるか
を作っておけば、(a,b)の全ての組についてB[a][b] * cnt[a][b]の総和を取ればいいので、O(9*9)でいける。
O(9!*9^2)で間に合う。

int N; string S;
int cnt[10][10];
int A[3][3], B[10][10];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    fore(c, S) c -= '1';

    rep(i, 0, N - 1) {
        int a = S[i];
        int b = S[i + 1];
        cnt[a][b]++;
    }

    int mi = inf; vector<int> ans;
    vector<int> v;
    rep(i, 0, 9) v.push_back(i);
    do {
        rep(i, 0, 9) A[i / 3][i % 3] = v[i];
        rep(x1, 0, 3) rep(y1, 0, 3) rep(x2, 0, 3) rep(y2, 0, 3) {
            int a = A[y1][x1];
            int b = A[y2][x2];
            int c = abs(x1 - x2) + abs(y1 - y2);
            B[a][b] = B[b][a] = c;
        }

        int sm = 0;
        rep(a, 0, 9) rep(b, 0, 9) sm += B[a][b] * cnt[a][b];
        if (sm < mi) {
            mi = sm;
            ans = v;
        }
        
    } while (next_permutation(all(v)));

    rep(i, 0, 9) {
        printf("%d", ans[i] + 1);
        if (i % 3 == 2) printf("\n");
    }
}