AOJ : 1161 - 覆面算 (Verbal Arithmetic)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1161&lang=jp
問題文が日本語なので省略です

アルゴリズム

ACM-ICPC本番ならば、全探索すれば普通に通る問題です。
が、AOJの場合は、8秒の制約があるので、解法を工夫しなければいけません。
ここでは、両側探索という手法を用いてコーディングしています。
今回は、次の方の解法を参考にしたため、僕からのアルゴリズムの解説はありません。

kkishiさんの解法

ちなみに、この2日間、全探索の形をなるべく変えずに、TLEを防ぐ方法を永遠考えていましたが、あと0.5秒ほどのところまで達して、それ以上タイムを縮めることができずにあきらめました。
もし、全探索に近い方法で解ける！という方は、がんばってみてください。
でも、無駄な時間を浪費するだけになるかもしれないので、おすすめしませんｗ

プログラム

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        while(true){
            int n = sc.nextInt();
            if(n == 0) break;

            int[] count = new int[26]; //各アルファベットの重みを求める
            boolean[] flg = new boolean[26]; //各アルファベットが単語の先頭にあるかのフラグ
            boolean[] ap = new boolean[26]; //各アルファベットが単語中に現れたかどうかのフラグ
            int m = 0; //入力に出現したアルファベットの種類数

            for(int i=0;i<n;i++){
                char[] s = sc.next().toCharArray();
                int len = s.length;

                if(len != 1) flg[s[0]-'A'] = true; //1文字でない限り,0にしてはいけないアルファベット
                for(int j=0;j<len;j++){
                    if(!ap[s[j]-'A']){
                        m++;
                        ap[s[j]-'A'] = true;
                    }

                    if(i == n-1)
                        count[s[j]-'A'] -= Math.pow(10,len-j-1);
                    else
                        count[s[j]-'A'] += Math.pow(10,len-j-1);
                }
            }

            w = new int[m]; //count配列の必要な要素だけ取り出した配列
            initFlg = new boolean[m]; //flg配列の必要な要素だけ取り出した配列
            int j = 0;

            for(int i=0;j<m;i++){
                if(ap[i]){
                    w[j] = count[i];
                    initFlg[j++] = flg[i];
                }
            }

            //「合計数->使用した数字(ビット管理)->出現回数」のマップ
            map = new HashMap<Integer,HashMap<Integer,Integer>>();

            //w配列の先頭m/2個分の全探索を行い,mapに列挙
            topDown(m/2,0,0,0);
            //w配列の後ろ半分を全探索し,topDownとの重なりがないか探す
            System.out.println(bottomUp(m%2==0?m/2:m/2+1,m-1,0,0));
        }
    }

    private static int[] w;
    private static boolean[] initFlg;
    private static HashMap<Integer,HashMap<Integer,Integer>> map;

    private static void topDown(int rem,int idx,int sum,int used){
        if(rem == 0){
            if(map.containsKey(sum)){
                if(map.get(sum).containsKey(used)){
                    //すでに出たことのあるパターンならば,カウントにプラス１
                    map.get(sum).put(used,map.get(sum).get(used)+1);
                }
                else{
                    //まだ出たことのないパターンならば,カウントは１
                    map.get(sum).put(used,1);
                }
            }
            else{
                map.put(sum,new HashMap<Integer,Integer>());
                map.get(sum).put(used,1);
            }

            return;
        }

        for(int i=initFlg[idx]?1:0;i<10;i++){
            if((used&(1<<i)) == 0){
                topDown(rem-1,idx+1,sum+w[idx]*i,(used|(1<<i)));
            }
        }
    }

    private static int bottomUp(int rem,int idx,int sum,int used){
        int res = 0;

        if(rem == 0){
            //キーとして(-合計)がなければカウント=0
            if(!map.containsKey(-sum)) return 0;
            for(int tmp : map.get(-sum).keySet()){
                //topDownで使用した数字とかぶってなければカウントする
                if((tmp & used) == 0){
                    res += map.get(-sum).get(tmp);
                }
            }
            return res;
        }

        for(int i=initFlg[idx]?1:0;i<10;i++){
            if((used&(1<<i)) == 0){
                res += bottomUp(rem-1,idx-1,sum+w[idx]*i,(used|(1<<i)));
            }
        }
        return res;
    }
}