読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AOJ 1175: そして,いくつになった?

AOJ
解法

残っている円盤を状態としてメモ化再帰すればいけそうなんですが, AOJ のメモリ制限的に dp[1<<24] という配列を取るとそれだけで死にます(国内予選で出た問題なので, 本番は答えを出力するだけで良いんですが)。

よく考えると, 毎回の遷移で円盤は 2 つ消えるので, 状態としては bit が偶数個/奇数個 立ったものしかありえないので, 実際には 2^23 個しか状態はありません。
2^23 個分のメモリは取れるのでこれに注目すると, map を使って dp すれば間に合うことがわかります。

と思ったけどこれおかしい気がする…なんで通ったんだ(pair だから結局 2^24 個分消費してる気がしてきた)

ていうか int じゃなくて char とか使えば良かったんや…

const int MAXN = 30;
int x[MAXN], y[MAXN], r[MAXN], c[MAXN];
bool ok[MAXN];
map<int, int> dp;

int square(int x) {return x*x;}

// i, j が重なってるかを調べる
// 重なってたら true
bool check(int i, int j) {
    int d2 = square(x[i]-x[j]) + square(y[i]-y[j]);
    return d2 < square(r[i]+r[j]);
}

int dfs(int state, int n) {
    int ret = 0;
    if (dp.find(state) != dp.end()) return dp[state];
    // まだ存在するやつで一番上にあるのを列挙
    vector<int> already;
    memset(ok, true, sizeof(ok));
    for (int i = 0; i < n; i++) {
        if ((state>>i)&1) continue;
        if (ok[i]) {
            already.push_back(i);
        }
        for (int j = i+1; j < n; j++) {
            if (check(i, j)) ok[j] = false;
        }
    }
    int sz = already.size();
    for (int i = 0; i < sz; i++) {
        for (int j = i+1; j < sz; j++) {
            int ai = already[i], aj = already[j];
            if (c[ai] == c[aj]) {
                int nstate = state;
                nstate |= 1<<ai;
                nstate |= 1<<aj;
                ret = max(2+dfs(nstate, n), ret);
            }
        }
    }
    return dp[state] = ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        if (n==0) break;
        for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> r[i] >> c[i];
        dp.clear();
        cout << dfs(0, n) << endl;
    }
    return 0;
}