AOJ 2554 : encode/decode

解法

固有値が2の時の固有ベクトルを求めて、適当にグラフを作ると、後ろから辿ることで状態を復元できる

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<char, int> State;
 
map<pair<State, int>, State> f;
map<pair<State, char>, pair<State, int> > g;
#define M 9
int deg[M] = {3, 6, 4, 2, 5, 4, 3, 2, 1};
 
void next(State &s, int a){
    char &c = s.first;
    int &p = s.second;
    if(c == 'A'){
        c = 'B';
        p = 2 * p + a;
    } else if(c == 'B'){
        if(p < 2){
            c = 'C';
            p = 2 * p + a;
        } else {
            p = 2 * (p-2) + a;
            if(p < 3) c = 'A';
            else {
                c = 'E';
                p -= 3;
            }
        }
    } else if(c == 'C'){
        if(p == 3){
            c = 'D';
            p = a;
        } else {
            c = 'B';
            p = 2 * p + a;
        }
    } else if(c == 'D'){
        c = 'C';
        p = 2 * p + a;
    } else if(c == 'E'){
        if(p < 4){
            c = !a?'B':'F';
        } else {
            c = 'B';
            p = p + a;
        }
    } else if(c == 'F'){
        if(p < 3){
            c = !a?'E':'G';
        } else {
            c = 'E';
            p = p + a;
        }
    } else if(c == 'G'){
        if(p < 2){
            c = !a?'F':'H';
        } else {
            c = 'F';
            p = p + a;
        }
    } else if(c == 'H'){
        if(p < 1){
            c = !a?'G':'I';
        } else {
            c = 'G';
            p = p + a;
        }
    } else {
        c = 'H';
        p = a;
    }
}
 
int main(){
    for(int i = 0; i < M; i++){
        for(int j = 0; j < deg[i]; j++){
            State a = State('A'+i, j);
            for(int k = 0; k < 2; k++){
                State b(a);
                next(b, k);
                f[make_pair(a, k)] = b;
                g[make_pair(b, 'A'+i)] = make_pair(a, k);
                //cerr<<"f("<<a.first<<","<<a.second<<","<<k<<") = "<<b.first<<","<<b.second<<endl;
            }
        }
    }
    string query, s, t;
    int n;
    cin>>query>>n>>s;
    if(query == "encode"){
        t = s[0]=='0'?"A":"B";
        State a('A'+s[0]-'0', 0);
        //cerr<<a.first<<" "<<a.second<<endl;
        for(int i = 1; i < n; i++){
            a = f[make_pair(a, s[i]-'0')];
            //cerr<<a.first<<" "<<a.second<<endl;
            t += a.first;
        }
        //cerr<<endl;
        for(int i = 0; i < 10; i++){
            a = f[make_pair(a, 1)];
            t += a.first;
            //cerr<<a.first<<" "<<a.second<<endl;
        }
        cout<<t<<endl;
    } else {
        State a;
        for(int j = deg[s[n-1]-'A']-1; j >= 0; j--){
            a = State(s[n-1], j);
            //cerr<<a.first<<" "<<a.second<<endl;
            for(int i = 1; i <= 10; i++){
                pair<State, char> q(make_pair(a, s[n-i-1]));
                if(g.count(q) == 0) break;
                a = g[q].first;
            //cerr<<a.first<<" "<<a.second<<endl;
                if(g[q].second == 0) break;
                if(i==10){
                    j = 0;
                }
            }
        }
        //cerr<<a.first<<" "<<a.second<<endl;
        for(int i = 11; i < n; i++){
            pair<State, char> q(make_pair(a, s[n-i-1]));
            pair<State, int> o = g[q];
            a = o.first;
            t += '0'+o.second;
            //cerr<<a.first<<" "<<a.second<<endl;
        }
        t += s[0]=='A'?'0':'1';
        reverse(t.begin(), t.end());
        cout<<t<<endl;
    }
    return 0;
}