JOI2012-sp-Day1 JOI旗

問題文

https://atcoder.jp/contests/joisc2012/tasks/joisc2012_joi_flag

解説から問題文に飛べます

問題概要

(2^k)*(2^k)サイズのマス目があり、これをJOI旗に塗る。

N点の文字は既に決まっていて、この文字を変えるためには1か所につきコスト1がかかる。

全てのマスを塗るための最小コストは何？

考察

素直に考えると、それぞれのマス目において4!通りの色の塗り方を試して、小さいマス目のほうに再帰をするという風な解法になるだろう。

ただ、これをしていると計算量が爆発してしまう。

ここで、再帰をしていった先で一文字も決定していない(=どういう風においてもよい）場合を考えると、これは枝狩りをしてよい。

計算の必要のある(=枝狩りをしてはいけない)マスを考えると、それぞれの文字について、K通りの場面にしか現れないので、計算しなくてはならない場面はN*K以下になり、これは十分計算可能である。

よって、再帰の時に、各範囲について、その中に何個のJ,O,Iで決定しているマスがあるか、が判別できればよいことになる。

これは、それぞれの文字が含まれる(2^t)*(2^t)の範囲を列挙して記録すればよく、mapなどを使えばできる。

注意するべきこととして、毎回愚直に再帰するとTLEするので、メモ化をしないといけない。

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define H pair<int, int>
#define P pair<int, H>
#define Q(a,b,c) make_pair(a,H{b,c})
#define vec vector
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
const int inf=1e9;

int k, n;
H a[2000];
char b[2000];
map<P, vec<int>>mp2;
map<P, vec<int>>mp;
map<P, int>dp;

signed main() {
    cin >> k >> n;
    rep(i, n) {
        cin >> a[i].fs >> a[i].sc >> b[i];
        a[i].fs--; a[i].sc--;
        int g = 1;
        rep(t, k + 1) {
            int x = a[i].fs / g * g, y = a[i].sc / g * g;
            mp2[Q(x, y, t)].pb(i);
            g *= 2;
        }
    }

    for (auto g : mp2) {
        mp[g.fs] = vec<int>(3, 0);
 
        for (auto f : g.sc) {
            int t = 0;
            if (b[f] == 'O') t = 1;
            else if (b[f] == 'I') t = 2;
            mp[g.fs][t]++;
        }
        vec<int>b(3, 0);
        rep(i, 3)rep(j, 3) {
            if (i != j) b[i] += mp[g.fs][j];
        }
        mp[g.fs] = b;
    }
 
    auto G = [&](int x, int y, int z, int rank)->int {
        if (mp.find(Q(x, y, rank)) == mp.end()) return 0;
        return mp[Q(x, y, rank)][z];
    };

    function<int(int, int, int)>F = [&](int x, int y, int rank)->int {
        if (dp.find(Q(x, y, rank)) != dp.end()) return dp[Q(x, y, rank)];
 
        if (rank == 0) return 0;
 
        if (mp.find(Q(x, y, rank)) == mp.end()) return 0;
 
        int ret = inf;
        vec<int>c; rep(i, 4) c.pb(i);
        vec<H>d = { {0,0},{0,1},{1,0},{1,1} };
        do {
            int sum = 0;
            rep(i, 4) {
                if (c[i] == 0) {
                    sum += F(x + d[i].fs * (1ll << (rank - 1)), y + d[i].sc * (1ll << (rank - 1)), rank - 1);
                }
                else {
                    sum += G(x + d[i].fs * (1ll << (rank - 1)), y + d[i].sc * (1ll << (rank - 1)), c[i] - 1, rank - 1);
                }
            }
            ret=min(ret, sum);
        } while (next_permutation(c.begin(),c.end()));
 
        return  dp[Q(x, y, rank)] = ret;
    };
    cout << F(0, 0, k) << endl;
}