SRM639

TopCoder

すごく久しぶりに出てみた。

  • -

250. AliceGame

問題：{1, 3, ..., 2*n-1} の和がx+yになるようなnを選び、その部分和でxが作れるならそのときの要素数の最小値を求める問題。できなかったら-1を返す。

  • とりあえず Σ(2*i-1) を求めるぜ！って思ってたら n^2 だった。
  • x+y≦2*10^12 だったので、適当にループ回してもnは求まりそう。
  • まぁ、easyだしxから大きい要素を貪欲に引いておけば良いのでは、と思うも自信ない。
  • とりあえず小さいケースで全探索してみる。
  • まず、x=2 や y=2 だとさすがに作れないことが判明。
  • x=9, y=7 みたいなケースだと貪欲に引くと x=2 ができてやばい事が判明。
  • 2に気をつけておけば良さそう、と思って書いたらサンプル通ったので提出した。
class AliceGame {
public:
    long long findMinimumValue(long long x, long long y) {
        if(x+y == 0) return 0;
        for(long long turn=1;turn*turn<=x+y;turn++){
            if(turn*turn != x+y) continue;
            long long res = 0;
            for(int i=turn;i>=1;i--){
                if(x >= 2*i-1 && x-(2*i-1) != 2){
                    x -= 2*i-1;
                    res++;
                }
            }
            return x==0 ? res : -1;
        }
        return -1;
    }
};

500. BoardFolding

問題：白黒に塗られたN×Mのグリッド用紙を、同じ模様のところが重なるように折っていく。出来上がりの図形は何通り？的な問題。

  • ははーん、ゴリゴリ全探索する実装ゲーだな？と思って制約見たら N,M≦250 だった。
  • オワタなぁと思いつつカスパロフvs羽生名人のタイムシフトを見て現実逃避する。
  • easy通るか怖かったので現実に帰ってくる。
  • こういう問題は1次元の問題に分解できる場合があった気がした。
  • 横にこう折ったら新たに縦のここが折れるようになったぜ！とか無いので独立っぽい。
  • ので、各方向について問題を解いて結果を乗算してみたらサンプル通った。
  • 念のため最大ケースを投げてみたら0.6secくらいだったので提出した。
int mem[251][251];
int same[250][250];

int toNumber(char c){
    if(isdigit(c)) return c-'0';
    if(islower(c)) return c-'a'+10;
    if(isupper(c)) return c-'A'+36;
    if(c == '#') return 62;
    return 63;
}

class BoardFolding {
    int solve(const vector< vector<int> >& v){
        int n = v.size(), m = v[0].size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                same[i][j] = 1;
                for(int k=0;k<m;k++){
                    if(v[i][k] != v[j][k]) same[i][j] = 0;
                }
            }
        }
        memset(mem, 0, sizeof(mem));
        mem[0][n] = 1;
        int res = 1;
        queue< pair<int, int> > qu; qu.push(make_pair(0, n));
        while(!qu.empty()){
            pair<int, int> pr = qu.front(); qu.pop();
            int a = pr.first, b = pr.second;
            for(int c=a+1;c<b;c++){
                bool ok = true;
                int d = c-1, e=c;
                while(a <= d && e < b){
                    if(!same[d][e]) ok = false;
                    d--;
                    e++;
                }
                if(!ok) continue;
                if(c-a >= b-c && !mem[a][c]){
                    mem[a][c] = 1;
                    res++;
                    qu.push(make_pair(a, c));
                }
                if(b-c >= c-a && !mem[c][b]){
                    mem[c][b] = 1;
                    res++;
                    qu.push(make_pair(c, b));
                }
            }
        }
        return res;
    }
public:
    int howMany(int N, int M, vector <string> compressedPaper) {
        vector< vector<int> > paper(N, vector<int>(M, 0));
        vector< vector<int> > paper2(M, vector<int>(N, 0));
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                paper[i][j] = (toNumber(compressedPaper[i][j/6])>>(j%6))%2;
                paper2[j][i] = paper[i][j];
            }
        }
        return solve(paper)*solve(paper2);
    }
};

1100. ElectronicPet

  • 観賞用だった。
  • -

結果：AC / AC / -- ，-25, 473.03pt, 24位
レーティング：2442 -> 2484

easyがあんな撃墜祭りになると思ってなくて完全にビッグウェーブに乗り遅れたし、これは貪欲に引いたら落ちるやつだぜ！と思ってチャレンジしたら普通に-1が答えのケースを投げてしまってしょんぼりしてました。うーむ。