全然解けなかった。朝起きてもう一回やってみたら解けた。おそらく寝てる間に頑張ったのかな。

方針

bitDPを使う。全ビットのOR和がゴール状態なのでdp[ <ゴール状態> ]が答え。例えば

1110
0100
0010

ならdp[ "0b1110" ] が答え。

更新方法はstateから遷移できるすべてのパターンに対して(つまり以下のnextは与えられたインストラクションのすべての中の一つ)

dp[stateをnextした後] = min(dp[stateをnextした後], dp[state] + dist( state, next ))

で更新していく。 stateをnextするのは単にOR和。OR和の中にすでに訪れたstateに関する情報が含まれているので、あるstateに達するための経路を保持する必要はない。すべてのstateを通り抜けないと最終stateに達しないので（これは不正確、だけど雰囲気は伝わるか）、単に経路のことは忘れてすべての取りうるstateに関してdp[goal]を求めればよい。

m(各インストラクション内の最大ビット数)が高々20までなので、forで回せばよい。

Code

public class OrderOfOperations {

    private int popcount(int a) {
        int c = a;
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            ans += (c & 1) > 0 ? 1 : 0;
            c = c >> 1;
        }
        return ans;
    }

    private int dist(int a, int b) {
        int c = (a ^ b) & (~a);
        int ans = popcount(c);
        ans = (ans < 0) ? 0 : ans;
//        System.out.println(Integer.toBinaryString(a) + "->" + Integer.toBinaryString(b) + "=" + ans + " bits");
        return ans * ans;
    }

    public int minTime(String[] s) {
        int ninst = s.length;
        int nmem = s[0].length();
        int[] ss = new int[ninst];
        int goal = 0;
        for (int i = 0; i < ninst; ++i) {
            ss[i] = Integer.parseInt(s[i], 2);
            goal = goal | ss[i];
        }

        int dp[] = new int[(1 << 22)];
        int inf = 99999999;
        for (int j = 0; j < (1 << nmem); ++j) dp[j] = inf;
        dp[0] = 0;

        for (int i = 0; i < (1 << nmem); ++i) {
            for (int e : ss) {
                if(dp[i] == inf) continue;
                int d = dist(i, e);
                dp[i | e] = (dp[i | e] < dp[i] + d) ? dp[i | e] : dp[i] + d;
            }
        }

        return dp[goal];
    }
}