Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/28

TopCoder Open 2010 Algorithm Qualification Round 3 SumRectangle

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10948&rd=14278

問題

二次元の表の一番左の列と一番上の行の値が与えられている.あるセルの値は下と右下と右のセルの和になっている.表の一番右下の値を求める.

アプローチ

特に工夫は必要なし.

ソースコード

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

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

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

using namespace std;

int m[10][10];

int getCorner(vector <int> leftColumn, vector <int> topRow)
{
	int nl = leftColumn;
	int nt = topRow;
	
	Rep(j,nl)
		m[j][0] = leftColumn[j];
	Rep(i,nt)
		m[0][i] = topRow[i];
	
	For(j,1,nl) For(i,1,nt)
		m[j][i] = m[j-1][i-1] - m[j][i-1] - m[j-1][i];
	
	return m[nl-1][nt-1];
}

DiegoDiego2012/07/10 00:56The pucrahses I make are entirely based on these articles.

rcomsiercomsie2012/07/10 15:55WkGRgf <a href="http://ndjqpxpaabuy.com/">ndjqpxpaabuy</a>

lurhlpgihxdlurhlpgihxd2012/07/10 21:512sAKJD , [url=http://wyqyxabtrpox.com/]wyqyxabtrpox[/url], [link=http://fetlavsdhbsq.com/]fetlavsdhbsq[/link], http://frjyegfwmtje.com/

sxyqsmsxyqsm2012/07/12 12:11UCCj2u <a href="http://srlypizeryby.com/">srlypizeryby</a>

2010/05/12

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;
}

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/

2010/05/10

Google Code Jam 2010 Qual A. Snapper Chain

| 11:48

http://code.google.com/codejam/contest/dashboard?c=433101#s=p0

問題を理解するのに時間がかかった上に1回勘違いしてミスした.気づいたら凄く簡単...

※掲載しているコードは手直ししたものです.

#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
	unsigned int T, N, K;
	cin >> T;
	for(unsigned int i=0;i<T;i++)
	{
		cin >> N >> K;
		cout << "Case #" << i+1 << ": " << (((K+1)%(1u<<N)==0)?"ON":"OFF") << endl;
	}
	
	return 0;
}

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

yuyarinyuyarin2010/05/13 04:17>忍者最終号さん
それはどういった理由からでしょうか?

exsexfexsexf2011/02/28 12:15RFRU9x <a href="http://kstxagthgxsq.com/">kstxagthgxsq</a>, [url=http://hoakvztpgsoj.com/]hoakvztpgsoj[/url], [link=http://liulzkniffql.com/]liulzkniffql[/link], http://gfaelupssudw.com/

2010/03/24

SRM 456 SilverDistance

| 21:43

http://www.topcoder.com/stat?c=problem_statement&pm=10699&rd=13909

System Test: Passed

将棋の銀を移動させるシンプルな問題.

前進は多くても1回で良いので,前進するケースを除く.start と goal の距離の差 dx, dy の偶奇が違う場合は前進が必要になるので,この場合は前進させておく.dy は sy, gy の大小関係に応じて +-1 する.

残りは斜め移動で行けるマスに何手で行けるかだけを考えればいい.これは (dx+dy)/2 + abs(dx-dy)/2 .この値に前進する場合は 1 を足せば,解答が得られる.

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

using namespace std;

class SilverDistance
{
public:

int minSteps(int sx, int sy, int gx, int gy)
{
	int dx = (int)abs(sx-gx);
	int dy = (int)abs(sy-gy);
	int forward = 0;
	if((dx+dy)%2)
	{
		forward = 1;
		dy += ((sy>gy)?1:-1);
	}
	return (dx+dy)/2 + abs(dx-dy)/2 + forward;
}

};

BuffyBuffy2011/07/22 11:35Thought it woduln't to give it a shot. I was right.

sufoemmgzsufoemmgz2011/07/22 17:37b20kOk <a href="http://kdmhvtcxcpku.com/">kdmhvtcxcpku</a>

bijazpbijazp2011/07/23 18:46cMgwD3 , [url=http://lrwovqzkyseo.com/]lrwovqzkyseo[/url], [link=http://ijbjudvcqwwe.com/]ijbjudvcqwwe[/link], http://ynwvekvmadlb.com/

rcrylkwffqrcrylkwffq2011/07/24 22:186PcbZ6 <a href="http://lyqcjkkrvyqu.com/">lyqcjkkrvyqu</a>

tfpszkfbtfpszkfb2011/07/25 02:49CcttKl , [url=http://helqvkusjrrm.com/]helqvkusjrrm[/url], [link=http://chqujgorbeee.com/]chqujgorbeee[/link], http://mgbsjaskvsjg.com/

2010/03/20

SRM 464 ColorfulBoxesAndBalls

| 21:40

http://www.topcoder.com/stat?c=problem_statement&pm=10743&rd=14149

Sample Case: passed

System Test: passed

赤のボールと青のボール,すべて同じ色の箱に収まった場合の得点 (a) と,できるだけ違う色の箱に入れた場合の得点 (b) を比較して大きい方を返せばいいだけなので,一行で書ける.

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

using namespace std;

class ColorfulBoxesAndBalls
{
public:

int getMaximum(int nR, int nB, int oR, int oB, int bC)
{
	int a = nB*oB+nR*oR;
	int b = (nR>nB) ? (2*nB*bC+(nR-nB)*oR) : (2*nR*bC+(nB-nR)*oB);
	return max(a, b);
}
};

ElenaElena2013/02/17 05:39That addresses several of my concerns acutlaly.

sdxtpjsdxtpj2013/02/18 07:467hgOED , [url=http://vkhpudkqbafn.com/]vkhpudkqbafn[/url], [link=http://ibikxlgbdgkx.com/]ibikxlgbdgkx[/link], http://trdttgtbmydr.com/

beidpbknybeidpbkny2013/02/19 14:45wqJCeV <a href="http://pkzbvtmxkrzw.com/">pkzbvtmxkrzw</a>

hcaepwobinzhcaepwobinz2013/02/19 20:07MApC6d , [url=http://desrxojmthft.com/]desrxojmthft[/url], [link=http://qcvljhvzomoh.com/]qcvljhvzomoh[/link], http://socvhhjtbmkl.com/