Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/12

TopCoder Open 2010 Algorithm Qualification Round 2

| 23:48

250 pt. は少し出遅れたけど正解.500 pt. はアルゴリズムは正しいけど計算量の問題があって TLE なケースをチャレンジされて撃墜.

まぁでも 514 位でなんとか予選通過したみたいだし rating も 1203 になってついに青コーダー!!

Problems

Class NameMethod NameDifficultyCoding TimeStatusPoints
JingleRingleprofitLevel One0:15:09.742Passed System Test199.23
FuzzyLifesurvivingCellsLevel Two0:59:02.978Challenge Succeeded198.62

Defence

DefendantChallengerProblemSucceededChallenge TimePoints
yuyarinBolekFuzzyLifeNo05:33.487-198.62

Statistics

Room 16

Coding PhaseChallenge PhaseSystem TestPoint TotalDivision PlacedAdv.Old RatingRating ChangeNew Rating
397.85-198.620.00199.23514N1177261203

http://www.topcoder.com/stat?c=coder_room_stats&rd=14277&rm=304501&cr=22851423

TopCoder Open 2010 Algorithm Qualification Round 2 JingleRingle

| 23:48

http://www.topcoder.com/stat?c=problem_statement&pm=10896&rd=14277

250 pt. 問題.

buyOffer を大きい方から,sellOffer を小さい方から tax を考慮しながら見ていくだけ.

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

#define sz(a) int((a).size())
#define Sort(c)     sort((c).begin(),(c).end())

int profit(vector <int> b, vector <int> s, int tax)
{
	Sort(b);
	Sort(s);
	
	if(sz(b)<1 || sz(s)<1) return 0;
	
	int bi = sz(b)-1;
	int si = 0;
	int tp = 0;
	
	while(bi>=0 && si<sz(s))
	{
		int p = b[bi] - (b[bi]*tax)/100 - s[si];
		if(p<=0)
			break;
		tp += p;
		bi--;
		si++;
	}
	
	return tp;
}

TopCoder Open 2010 Algorithm Qualification Round 2 FuzzyLife

| 23:48

http://www.topcoder.com/stat?c=problem_statement&pm=10911&rd=14277

500 pt. 問題.

周りのセルも数えることを忘れていたことで時間を取ってしまい,最後 30 秒で Sample を Passed して commit.Challenging Phase で撃墜される.最大のケースで TLE してしまっていたようだ.

再帰によって n 個ある ? のセルを 1 つずつ固定して生存セルが一番多くなるものを選ぶ方法を取っていたのだけど,この方法の計算量は O(2^n) で,最大のケースだと n=272 が可能となり,このスケールになると TLE してしまう.

No cell will have more than one neighboring cell of type '?'

というのがヒントで,これはつまり,ある ? のセルを確定させる時に影響されるセルは他の ? のセルの影響を受けないということである.つまり1つずつ確定(固定ではない)させて行くことができる.これなら O(n) で処理できる.

具体的には ? がでてきたら,その周り 9 マスだけを計算して,多い方を選んで確定していけば十分である.


#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

typedef vector<string> VS;

#define sz(a) int((a).size())

int n;
int m;

class FuzzyLife
{
public:

// grid の特定の範囲だけ計算
int calcRange(VS &g, int mini, int maxi, int minj, int maxj)
{
	int tc = 0;
	for(int i=mini; i<=maxi; i++)
	{
		for(int j=minj; j<=maxj; j++)
		{
			int c = 0;
			if(i>0)
			{
				c += g[i-1][j]-'0';
				if(j>0)
					c += g[i-1][j-1]-'0';
				if(j<m-1)
					c += g[i-1][j+1]-'0';
			}
			if(i<n-1)
			{
				c += g[i+1][j]-'0';
				if(j>0)
					c += g[i+1][j-1]-'0';
				if(j<m-1)
					c += g[i+1][j+1]-'0';
			}
			if(j>0)
				c += g[i][j-1]-'0';
			if(j<m-1)
				c += g[i][j+1]-'0';
			if(g[i][j]=='1')
				if(c==2||c==3) tc++;
			else
				if(c==3) tc++;
		}
	}
	return tc;
}

int survivingCells(vector <string> grid)
{
	n = sz(grid);
	m = (int)grid[0].length();
	
	// 周りに 0 を 1 周分追加
	VS g;
	string s(m+2, '0');
	g.push_back(s);
	for(int i=0; i<n; i++)
		g.push_back("0"+grid[i]+"0");
	g.push_back(s);
	
	n += 2;
	m += 2;
	
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(g[i][j]=='?')
			{
				// ? のセルを固定して,周囲 9 セルだけを計算
				g[i][j] = '0';
				int r0 = calcRange(g, i-1, i+1, j-1, j+1);
				g[i][j] = '1';
				int r1 = calcRange(g, i-1, i+1, j-1, j+1);
				// 確定する
				g[i][j] = (r0>r1) ? '0':'1';
			}
		}
	}
	
	// 全体を計算する
	return calcRange(g, 0, n-1, 0, m-1);
}

AgustinaAgustina2012/07/10 05:30Yo, good loiokn out! Gonna make it work now.

dvmpfhnxpodvmpfhnxpo2012/07/10 16:19M992tq <a href="http://abuptwpwcqym.com/">abuptwpwcqym</a>

pptauxpptaux2012/07/11 20:46FCqabg , [url=http://fihpbpjoyarc.com/]fihpbpjoyarc[/url], [link=http://ciuzxzgiuyqo.com/]ciuzxzgiuyqo[/link], http://lvgsivtbvmij.com/

ktxodmtktxodmt2012/07/12 12:32jofRQ4 <a href="http://kizscxqiqaki.com/">kizscxqiqaki</a>

fncfmwxjlrfncfmwxjlr2012/07/12 18:05oX6byq , [url=http://cgudxnkygdfi.com/]cgudxnkygdfi[/url], [link=http://iuikvqdlnsqu.com/]iuikvqdlnsqu[/link], http://ebjctraukepx.com/