mayoko’s diary

プロコンとかいろいろ。

SRM 483 div1 med: Bribes

解法

influence の値はたかだか 500 なので, now 番目の人は, now+8 番目までの人にしか影響は及ぼしません。

そこで, dp[now][state] = (now 番目の人で, now-8 番目から now+7 番目の人への賄賂を送ったか送ってないかのフラグが state で表されるような状態における, 残りの人に賄賂を送らなければならない人数の最小数)
とします。

now 番目の人が投票してくれるなら, now+8 番目の人に賄賂を送るかどうかはどちらでも良いですが, now 番目の人が投票してくれない状態の時は, now+8 番目の人に賄賂を送って resistance を下げる必要がある, というように遷移していきます。

now == n-8 の時は, now 〜 n-1 番目の人が投票してくれるかを判定して, 投票してくれないなら INF を, そうでないなら 0 を返します。

const int INF = 1e9;
int dp[55][1<<16];
vector<int> influence, resistance;

int dfs(int now, int state) {
    int& ret = dp[now][state];
    if (ret >= 0) return ret;
    int n = influence.size();
    if (now+8 >= n) {
        for (int i = now; i < n; i++) {
            int tmp = resistance[i];
            for (int j = 0; j < 16; j++) {
                if ((state>>j)&1) {
                    int eff = influence[now+j-8];
                    tmp -= eff>>(abs(i-(now+j-8)));
                }
            }
            if (tmp > 0) return ret = INF;
        }
        return ret = 0;
    }
    int tmp = resistance[now];
    for (int i = 0; i < 16; i++) {
        if ((state>>i)&1) {
            int eff = influence[now+i-8];
            tmp -= eff>>(abs(8-i));
        }
    }
    ret = INF;
    if (tmp <= 0) {
        ret = min(ret, dfs(now+1, state>>1));
        ret = min(ret, 1+dfs(now+1, (state>>1)|(1<<15)));
    } else {
        if (tmp-(influence[now+8]>>8) <= 0) ret = min(ret, 1+dfs(now+1, (state>>1)|(1<<15)));
    }
    return ret;
}

class Bribes {
public:
    int minBribes(vector <int> influence, vector <int> resistance) {
        ::influence = influence;
        ::resistance = resistance;
        int n = influence.size();
        if (n < 8) {
            int ans = INF;
            for (int s = 0; s < (1<<n); s++) {
                vector<int> tmp = resistance;
                for (int i = 0; i < n; i++) {
                    if ((s>>i)&1) {
                        for (int j = 0; j < n; j++) {
                            tmp[j] -= influence[i]>>(abs(i-j));
                        }
                    }
                }
                bool ng = false;
                for (int i = 0; i < n; i++) if (tmp[i] > 0) ng = true;
                if (!ng) ans = min(ans, __builtin_popcount(s));
            }
            if (ans >= INF) ans = -1;
            return ans;
        } else {
            memset(dp, -1, sizeof(dp));
            int ans = INF;
            for (int s = 0; s < (1<<8); s++) {
                ans = min(ans, __builtin_popcount(s) + dfs(0, s<<8));
            }
            if (ans >= INF) ans = -1;
            return ans;
        }
    }
};