mayoko’s diary

プロコンとかいろいろ。

SRM 667 div1 easy:OrderOfOperations

SRM 667 に参加しました。
見事に貪欲解法にハマって 0 完です。久しぶりのプログラミングコンテストなのでレート下がるだろうとは思っていたんですがなんか悔しいレートの下がり方をした感じですね。

解法

bitDP で解きます。
dp[state] = (メモリを state だけ使った場合の最小コスト)とすると, state の状態になった時点で行った操作はちゃんとわかります(すでに消費したメモリの中に操作したメモリが含まれているので)。

なので, 単純に各 state から n 通りの遷移をすると考えて dp すれば良いです。

得た知見
  • 今回のように bit で状態を管理するタイプの DP はその state 自体で調べる範囲を狭くできることがあることは意識するべき
const int INF = 1000000;
int dp[1<<22];

class OrderOfOperations {
public:
    int minTime(vector <string> s) {
        int n = s.size();
        int m = s[0].size();
        int xx = 0;
        vector<int> d;
        for (int i = 0; i < n; i++) {
            int tmp = 0;
            for (int j = 0; j < m; j++) if (s[i][j] == '1') tmp |= 1<<j;
            d.push_back(tmp);
            xx |= tmp;
        }
        for (int i = 0; i < (1<<m); i++) dp[i] = INF;
        dp[0] = 0;
        for (int i = 0; i < (1<<m); i++) {
            if (dp[i] == INF) continue;
            for (int el : d) {
                int k = 0;
                for (int j = 0; j < m; j++) {
                    if ((el>>j)&1) if (((i>>j)&1)==0) {
                        k++;
                    }
                }
                dp[i|el] = min(dp[i|el], dp[i]+k*k);
            }
        }
        return dp[xx];
    }
};