Topcoder SRM 593 div1

本番中は250のみを通した。

250

四色定理より、明らかに4以下であることはわかる。 しかし、すこし考えると、3色で塗り分け可能であることがわかる。

なので、0,1,2で塗れるかどうかを考えるだけで良い。 2色で塗れるかは再帰的にDFSをすればよい。(蟻本参照)

#include <vector>
#include <string>

using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)


const int dy[] = {-1,-1, 0, 0, 1, 1};
const int dx[] = { 0, 1, -1,1,-1, 0};

const char emp = '-';
const char col = 'X';

class HexagonalBoard{
public:
    bool solve2(int y,int x,int c,const vector<string> &board,vector<vector<char> > &color){
        int N = board.size();
        color[y][x] = c;
        rep(i,6){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny >= N or ny < 0 or nx >= N or nx < 0 or board[ny][nx] == emp) continue;
            if(color[ny][nx] == c) return false;
            if(color[ny][nx] == 0 and not solve2(ny,nx,-c,board,color)) return false;
        }
        return true;
    }
    int minColors(vector <string> board){
        int N = board.size();
        {
            bool allemp = true;
            rep(i,N){
                rep(j,N){
                    allemp = allemp and board[i][j]==emp;
                }
            }
            if(allemp) return 0;
        }
        // one?
        {
            bool norel = true;
            rep(y,N){
                rep(x,N){
                    bool one = true;
                    if(board[y][x] == emp) continue;
                    for(int i=0;i<6;i++){
                        int ny=y+dy[i],nx=x+dx[i];
                        if(ny >= N or ny < 0 or nx >= N or nx < 0) continue;
                        if(board[ny][nx] != emp){
                            one = false;
                        }
                    }
                    norel = norel and one;
                }
            }
            if(norel) return 1;
        }
        {
            bool two = true;
            vector<vector<char> > color(N,vector<char>(N));
            for(int y=0;y<N;y++){
                for(int x=0;x<N;x++){
                    if(board[y][x] == emp) continue;
                    if(color[y][x] == 0){
                        if(!solve2(y,x,1,board,color)){
                            two = false;
                        }
                    }
                }
            }
            if(two) return 2;
        }
        return 3;
    }
};

450

二つの集合S,Tに分けることを考える。 そのとき、S,Tの最大の差は、(Sが最速,Tが最遅)もしくは(Sが最遅,Tが最速)の場合である。

ここで、S={0,1,2},T={3,4,5}と仮にしたとき、以下で(Sが最速,Tが最遅)が計算できる。

D = abs((A0+A1+A2)-(B3+B4+B5)) 
  = abs((A0+A1+A2+A3+A4+A5-A3-A4-A5)-(B3+B4+B5)) 
  = abs((A0+A1+A2+A3+A4+A5) - ((A3+B3)+(A4+B4)+(A5+B5))

(Sが最遅,Tが最速)のときは同様に

E = abs((B0+B1+B2+B3+B4+B5) - ((A3+B3)+(A4+B4)+(A5+B5))

よってありえる(A3+B3)+(A4+B4)+(A5+B5)の部分を列挙して、max(D,E)の最小値を計算すればよい。 これはナップサック問題のDPのようにとける。

#include <vector>
#include <algorithm>

using namespace std;

#define all(c) c.begin(),c.end()
#define rep(i,n) for(int i=0;i<(int)n;i++)

class MayTheBestPetWin{
public:
    int calc(vector <int> A, vector <int> B){
        int N = A.size();
        vector<int> S(N);
        rep(i,N) S[i] = A[i] + B[i];
        int SA = accumulate(all(A),0);
        int SB = accumulate(all(B),0);

        const int CS = accumulate(all(S),1);
        vector<char> C(CS,false);
        C[0] = true;
        rep(i,N){
            vector<char> tmp(CS,false);
            rep(j,CS){
                if(not C[j]) continue;
                tmp[j] = tmp[S[i]+j] = true;
            }
            C = tmp;
        }
        int mini = 1 << 30;
        rep(i,CS){
            if(not C[i]) continue;
            mini = min(mini,max(abs(SA-i),abs(SB-i)));
        }
        return mini;
    }
};