AOJ 3053 Phone Number (RUPC 2019 day2-C)

一瞬詰まった。とりあえず 9! できるなと思ったあと、長さ の文字列を処理するのはどうするんだろ...となっていた。前処理が本質な感じがする。

問題へのリンク

問題概要

"31415926535" のような 1 〜 9 からなる長さ の文字列 が与えられる。

今、

137
456
892

のように 3 × 3 の電話盤を最適化して、文字列 を電話盤上でエミュレートしたときに上下左右に動く回数が最小となるようにしたい。それが最小となるような電話盤を求めよ。複数ある場合は辞書順最大のものを求めよ。

制約

• 

考えたこと

一目見て、9! 通りの全探索はできるという気持ちにはなる。それぞれの場合について

• dist[ v ][ w ] := 数字 v から数字 w への最短移動距離

という 9 × 9 の配列はなんらかの方法で高速に求めることができる。

しかし、これをもとに長さ の文字列をエミュレートするには一見、 の計算量を必要とする気がして来て無理な気持ちになってしまう。

でもよく考えると、長さ の文字列について

• num[ v ][ w ] := 数字 v から数字 w へと移動するのが何回あるか

を前処理しておけば、たかだか 程度の計算で求めることができる。

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    int N; string S; cin >> N >> S;
    vector<int> hai(9);

    vector<vector<long long> > num(10, vector<long long>(10, 0));
    for (int i = 0; i + 1 < N; ++i) {
        int a = S[i] - '0';
        int b = S[i+1] - '0';
        num[a][b]++;
    }
    iota(hai.begin(), hai.end(), 1);

    long long mi = 1LL<<60;
    vector<int> mii;
    do {
        // Warshall-Floyd
        long long dp[10][10];
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < 10; ++j) {
                dp[i][j] = 1<<29;
            }
            dp[i][i] = 0;
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                int v = hai[i*3+j];
                for (int dir = 0; dir < 4; ++dir) {
                    int ni = i + dx[dir], nj = j + dy[dir];
                    if (ni < 0 || ni >= 3 || nj < 0 || nj >= 3) continue;
                    int w = hai[ni*3+nj];
                    dp[v][w] = dp[w][v] = 1;
                }
            }
        }
        for (int k = 0; k < 10; ++k)
            for (int i = 0; i < 10; ++i)
                for (int j = 0; j < 10; ++j) 
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

        long long res = 0;
        for (int i = 1; i < 10; ++i) {
            for (int j = 1; j < 10; ++j) {
                res += num[i][j] * dp[i][j];
            }
        }

        if (mi > res) {
            mi = res;
            mii = hai;
        }
                    
    } while (next_permutation(hai.begin(), hai.end()));

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) cout << mii[i*3+j];
        cout << endl;
    }
}