Hatena::Grouptopcoder

TopCoder Memo@kagamiz

01.22.2013 (Tue)SRM 567 Div2

21:10からと平和な時間から開催されたので参加出来ました. 嬉しい.

結果 : oo- +0/-0 675.97pts 11位

久々にやった割にはよく出来たほうだと思います. 次でDiv 1に上がれるかな?

Easy (250 pts.) NinjaTurtles

問題文 :

K, P が与えられる.

[N / 3] + 3 * [N / K] == P となる最小のN を求めよ.

解法 :

P ≦ 10^6 なので, Nを3 * 10^6まで回せば十分である. O(N).

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long lint;

class NinjaTurtles {
public:
  int countOpponents(int P, int K) {
    
    for (int i = 0; i <= 3000000; i++) if (i / 3 + 3 * (i / K) == P) return (i);
    
    return (-1);
  }
};

Medium (500 pts.) TheSquareRootDilemma

問題文 :

SSR(a, b) = (√a + √b)^2 とする. 1≦a≦N, 1≦b≦M のとき, SSR(a, b)が整数となる(a, b)の組の個数を求めよ.

解法 :

1 ≦ N, M ≦ 77777 なので全探索では間に合わない.

そこで, √a = m√n となったときに, √bに当たる数はx√nの形になっていることに注目する.

x√nのxに当たる部分の個数をO(√M)で求めてやれば, aについてO(N)で全探索できるので, 全体としての計算量は O(N√M)となり間に合う.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
static const double EPS = 1e-5;
typedef long long lint;

lint sqMod(int x)
{
	for (int i = 2; i <= 77777; i++){
		if (x < i * i) break;
		while (x % (i * i) == 0) x /= (i * i);
	}
	return (x);
}

class TheSquareRootDilemma {
public:
  int countPairs(int N, int M) {
    int res = 0;
    
    for (int i = 1; i <= N; i++){
    	int k = 0;
    	lint mod = sqMod(i);
    	while ((k + 1) * (k + 1) * mod <= M) k++;
    	res += k;
    }
    
    return (res);
  }
};

Hard (1000 pts.) MountainsEasy

問題文 :

擬似コードに従って N 個の山を描く時, 山を描く順番を考慮して何通りが与えられた最終的な山の形になるか.

解法 :

まず, 擬似コードが難しいのでこれを解析すると, 場所(H - 1 - y, x)を頂点としたきゅうりさんを作ることが分かる.

したがって, "必ず使わないと行けない頂点" と, "作ることが出来る任意の山 (=図中のXの個数)" がO(WH)で求まる.

次に, dp[i][j] = (N個中いくらの山を作ったか, 使わないと行けない頂点をいくつ使ったか) とする.

ここで, このdp列に "使わないと行けない山j を使った後は, 山j を使えない" という制約を課すことで, 問題文で書かれているような順列の総数が求まる.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

static const double EPS = 1e-5;

typedef long long lint;
typedef pair<int, int> P;
bool check[64][64];

vector<P> need, all;

class MountainsEasy {
public:
  int countPlacements(vector<string> pix, int N) {
    int H = pix.size(), W = pix[0].size();
    
    for (int i = 0; i < H; i++){
    	for (int j = 0; j < W; j++){
    		if (pix[i][j] == 'X'){
    			if (!check[i][j]){
	    			need.push_back(P(i, j));
	    		}
	    		all.push_back(P(i, j));
	    		
	    		check[i][j] = true;
	    		if (j - 1 >= 0) check[i + 1][j - 1] = true;
	    		check[i + 1][j] = check[i + 1][j + 1] = true;
    		}
    	}
    }
    
    lint dp[64][64];
    
    memset(dp, 0, sizeof(dp));
    
    dp[0][0] = 1;
    
    for (int i = 0; i < N; i++){
    	for (int j = 0; j <= need.size(); j++){
                /* j 番目の"必要な山"を使ったら, それ以降はj 番目の山を使っては行けない */
    		dp[i + 1][j + 1] += dp[i][j] * (need.size() - j);
    		dp[i + 1][j + 1] %= 1000000009;
    		
    		dp[i + 1][j] += dp[i][j] * (all.size() - j);
    		dp[i + 1][j] %= 1000000009;
    	}
    }
    
    return (dp[N][need.size()]);
  }
};

10.25.2012 (Thu)SRM 491 Div2Hard - BottlesOnShelf

問題文 : BottlesOnShelf

解法 :

kyuridenamidaさんの記事に載っていた, 包除原理を使う問題です.

割れたボトルの数をans, ぶつかった回数をtとし,

下の総和にでてくるそれぞれのiについて

・ビットが立っている中のleftの最大値をlmax[i]

・ビットが立っている中のrightの最小値をrmin[i],

・ビットが立っている物すべてのdamageのlcmをdl[i]とすると,

ans = Σ[i=1..2^t-1](rmin[i] / dl[i] - (lmax[i] - 1) / dl[i]) * (-1) ^ (bitcount(i) - 1)

となります.

これを求めれば, 答えはN - ansとなります.

得点 :

932.8 pts / 1000 pts.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;

typedef long long lint;

lint gcd(lint a, lint b)
{
	return (b ? gcd(b, a % b) : a);
}

lint lcm(lint a, lint b)
{
	if (a < b) swap(a, b);
	return (a / gcd(a, b) * b);
}

class BottlesOnShelf {
public:
  int getNumBroken(int N, vector <int> left, vector <int> right, vector <int> damage) {
    
    lint ans = N;
    int sz = left.size();
	for (int i = 1; i < 1 << sz; i++){
		lint l = -1, r = N + 1, d = 1;
		int bc = 0;
		for (int j = 0; j < sz; j++){
			if ((i >> j) & 1){
				l = max(l, (lint)left[j]);
				r = min(r, (lint)right[j]);
				d = lcm(d, (lint)damage[j]);
				bc++;
			}
		}
		if (l > r) continue;
		ans += (r / d - (l - 1) / d) * (bc & 1 ? -1 : 1);
	}
    
    return N - ans;
  }
};

09.09.2012 (Sun)SRM 399 div2

asi1024さん, aroshさん, Respect2Dさん, Lepton_sさん, capythmさんと一緒に参加しました.

結果 : oo-

250 CircularLine (230.74pts)

問題概要 : 環状線になっている駅のうち, a -> b に行く方と b -> aに行く方のうち, 大きい方をすべての駅対について求め, その最小値を求める問題. 入力では隣合う駅同士の距離が与えられる.

解法 : 素直に距離を求めて実装する. 累積和を前もって求めておくと楽.

感想 : ちょっと読解に時間がかかった. 全体で3人目くらいにsubmitした(はず). 良い方.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class CircularLine {
public:
  int longestTravel(vector <int> t) {
    int ans;
    int sum[64];
    
    sum[0] = 0;
    for (int i = 1; i <= t.size(); i++){
    	sum[i] = sum[i - 1] + t[i - 1];
    }
    
    ans = 0;
    for (int i = 0; i < t.size(); i++){
    	for (int j = i + 1; j < t.size(); j++){
    		ans = max(ans, min(sum[j] - sum[i], sum[t.size()] - sum[j] + sum[i]));
    	}
    }
    
    return ans;
  }
}

500 MaximalProduct (491.15pts)

問題概要 : a1 + a2 + ... + ak = s となるように a1, a2, ..., akを定める時, 積a1 * a2 * ... * akの最大値を答えよ.

解法 : 相加・相乗平均の関係より, a1 + a2 + ... ak ≧ k・(a1 * a2 * ... * ak) ^ (1 / k) が成立して, 等号はa1 = a2 = ... = akのときに成立します. このことから, 積を最大化するにはa1, a2, ..., akたちを近い数にしてやったほうがよさそうです.

そこで, s / kをaiたちに分配してやり, 余りをs % k個の項に1ずつ加えてやることで, 最大値を達成できることがわかります.

感想 : わりと「こうしたらよさそうだなー」というのがパッと出てきて, そのとおりに実装できて, 晴れて490点台を取ることが出来ました. これは嬉しい!

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class MaximalProduct {
public:
  long long maximalProduct(int s, int k) {
    long long result;
    ll a[20];
    
    for (int i = 0; i < k; i++){
    	a[i] = (ll)(s / k);
    }
    
    for (int i = 0; i < s % k; i++){
    	a[i] += 1;
    }
    
    result = 1;
    for (int i = 0; i < k; i++){
    	result *= a[i];
    }
    
    return result;
  }
}

1000 AvoidingProduct (--.--pts)

問題概要 : 配列aの中に含まれる数を使わずに, |n - x * y * z|を最小化する x, y, zを求めよ. 複数ある場合はx, y, zがそれぞれ最小となるものをもとめよ.

解法 : 解けてませんが, n ≦ 1000程度で, x, y, zはそれぞれ掛け合わせるので, 全探索で余裕で間に合うそうです.ぐぬぬ.

感想 : 因数分解とかしてTLEしてました...くやしいなあ. 1000^3じゃダメそうだな, ではなく, ちゃんと状態が減ることも意識しないといけないと思いました.

最近は250, 500は安定して解けているので, 1000を出来るだけ解けるようにしていきたいです.