ABC 031 D - 語呂合わせ

問題

問題概要

省略

解法

この問題のポイントは、数字に対して、割り当てられる文字の長さが3文字までであるから、1~9の数字を何文字にするかきめれば、その長さが矛盾しないものか確かめられる。
実装で困った点は、kが決まっていないので、単純にループで何文字にするかを全探索で書くことはできない。そこで、3bit全探索を書くことになるみたい。2bit全探索はやったことあるので、実装ができるが、3bit全探索はやったことがない。やりかたは、以下の通り。

//3進数bit全探索
for (int mask = 0; mask < pow(3, k); ++mask){
    int tmp = mask;
    for (int pos = 1; pos <= k; ++pos){//数字1~kが何文字分か仮定する
        len[pos] = tmp % 3 + 1;//1 ~ 3文字
        tmp /= 3;
    }
}

2bitの時は、シフトなどを使い、bitが立っているかを調べられるが今回は、3進数に自分で変換していく感じ。
長さが決まったら、あとは、それが矛盾しないものかを確かめる。まず、その長さを仮定したときに、長さに矛盾ででないか、それをクリアできたなら、そのとき、文字と数字が一対一対応しているかを確かめた。

2bit全探索 mmxsrup.hatenablog.com

ミス

3bitでの全探索をやることができたので、ほかの場合の時でも行けそう。

コード

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
const int INF = 1e9;

int k, n;
string v[55];
string w[55];
int len[12];//len[i] := 数字　i が何文字分の長さか

bool check_len(){//仮定した長さで矛盾が生じないかを調べる
    rep(i, n){
        int nagasa = 0;
        rep(j, v[i].size()){
            nagasa += len[v[i][j] - '0'];
        }
        if(nagasa != w[i].size()) return false;
    }
    return true;
}

bool check_mozi(){//仮定した長さで文字を切り抜くと、文字列と数字が一対一で対応するか
    string memo[12];
    rep(i, n){
        int p = 0;
        rep(j, v[i].size()){
            int num = v[i][j] - '0';//数字
            string tmp = w[i].substr(p, len[num]);
            if(!memo[num].empty()){//すでに、数字numと対応する文字列が決まっているので、それと比較
                if(memo[num] != tmp) return false;//すでに登録されているものと異なっていた
            }else{//数字と対応する文字を初めて見つけた
                memo[num] = tmp;//登録
            }
            p += len[num];
        }
    }
    //print
    for (int i = 1; i <= k; ++i){
        cout << memo[i] << endl;
    }
    return true;
}



int main(void){
    cin >> k >> n;
    rep(i, n) cin >> v[i] >> w[i];
    
    //3進数bit全探索
    for (int mask = 0; mask < pow(3, k); ++mask){
        int tmp = mask;
        for (int pos = 1; pos <= k; ++pos){//数字1~kが何文字分か仮定する
            len[pos] = tmp % 3 + 1;//1 ~ 3文字
            tmp /= 3;
        }
        if(!check_len()) continue;
        if(!check_mozi()) continue;
        return 0;
    }
}