Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2010-08-04

SRM478 Div2

00:09

oox、撃墜1で605.04pts/23位。

レーティング1170->1298。ねんがんの あおネームを てにいれたぞ!

今回は問題文にどっかで見た感じの名前が色々出てきて面白かった^^

250 KiwiJuiceEasy

きうぃジュースが入ってるグラスがたくさんあって、中身を移し替えるのを繰り返す。最後の状態を求めよ。

グラスからあふれないように注ぐのに注意して書くだけ。


#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <climits>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

struct KiwiJuiceEasy {
    vector <int> thePouring(vector <int> capacities, vector <int> bottles, vector <int> fromId, vector <int> toId) {
        vector<int> v = bottles;
        for(int i = 0; i < fromId.size(); ++i) {
            int from = fromId[i];
            int to = toId[i];
            int cap = capacities[to] - v[to];
            if(cap > v[from]) {
                v[to] += v[from];
                v[from] = 0;
            }
            else {
                v[to] = capacities[to];
                v[from] -= cap;
            }
        }
        return v;
    }
};

500 CarrotJumping

うさぎのHanakoが直線上を動いてニンジンのあるところまで行きたい。ただし、Hanakoが動けるのは今いる座標をxとしたとき4x+3と8x+7の場所だけ。また、ニンジンは1,000,000,007の倍数の座標にしか生えてない。初期位置が与えられたとき、100,000手以内でニンジンの所にたどり着けるなら最小手数を、無理なら-1を返せという問題。

4x+3と8x+7というのがいかにも怪しげ。手計算で何回か適用を繰り返すと、行ける座標は必ず(2**n)x+(n-1)であることが判る。そしてさらに、4x+3はnを2個進めて、8x+7はnを3個進める操作であることが判る。つまり、nが2以上なら必ずたどり着くための手段があるということ。逆に考えるとnから4x+3の回数と8x+7の回数が求められるので、modを取りながらnに関してループしていけばよい。


#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <climits>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

struct CarrotJumping {
    int theJump(int init) {
        unsigned mod = 2*init+1;
        for(int i = 1; i < 100000*3; ++i) {
            int p = i+1;
            mod = (2*mod+1) % 1000000007;
            if(mod == 0) {
                int cnt = 0;
                if(p % 3 == 1) {
                    cnt = p/3 + 1;
                }
                else {
                    cnt = p/3 + p%3/2;
                }
                if(cnt <= 100000) return cnt;
            }
        }
        return -1;
    }
};

1000 RandomAppleEasy

赤りんごと青りんごの入った箱がいくつかある。この中から適当な個数の箱を選んで、空の箱にマージする。この箱から赤りんごを取り出す期待値を求めよ、という問題。ただし、一つの箱に入っている赤りんごと青りんごは高々10個ずつ、箱の数は高々50個。

なんか凄くDP臭がするけどなんのDPすれば良いのかいつも通り判らない。全探索は2**50なので無理。モンテカルロ法とか焼きなましとか思いついたけどあまりにもあんまりなので自重。

終わってから人のコード見た。あー、赤りんごと青りんごの組み合わせが同じなら期待値は当然同じで、りんごがそれぞれ高々10個だから(10*50)**2のDPで収まるのね・・・。

ざっと見て実装。パターン数が2**N-1というのが最初に計算できてしまうのがミソで、これをやらないと途中で答えがオーバーフローして変になるみたい。ここ分かってなくてかなり悩んだ・・・。


#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <climits>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef unsigned long long ULL;

struct RandomAppleEasy {
    double theRed(vector <int> red, vector <int> green) {
		vector<vector<ULL> > pat(501, vector<ULL>(501, 0));
        vector<vector<ULL> > tmp(501, vector<ULL>(501, 0));

        pat[0][0] = 1;
        tmp[0][0] = 1;
        for(int i = 0; i < red.size(); ++i) { //add box [i]
            for(int a = 0; a < 501-red[i]; ++a) {
                for(int b = 0; b < 501-green[i]; ++b) {
                    tmp[a+red[i]][b+green[i]] += pat[a][b];
                }
            }
            pat = tmp;
        }

        double prob = 0;
        double total = pow(2.0, (double)red.size()) - 1.0;
        for(int sum = 1; sum < 1001; ++sum) {
            for(int a = 0; a <= 500 && a <= sum; ++a) {
                int b = sum-a;
                if(b > 500) continue;
                if(pat[a][b] == 0) continue;
                prob += (double)a*pat[a][b] / sum / total;
            }
        }
        return prob;
    }
};

Challenge Phase

1000を750点くらいで出してるこわい人がいたのでソースを見てみると、next_permutationが見えたので50要素のパターンを送って撃墜。もう一人出してたけどTLEではなさそうなので放置。

500も間違っている人はいなさそうなので、まあ落とせないだろうとは思いつつ250を下から見てく。結局落とせず終了。

System Testでも500が一つ落ちただけでした。平和。

 |