TimeTravellingSalesman巡回セールスマンだけど単なる最小全域木。 #include <string> #include <vector> #include <numeric> #include <sstream> using namespace std; class TimeTravellingSalesman{public: long long determineCost( int N, vector <string> roads ) { string s = accumulate( roads</string></sstream></numeric></vector></string>…

TimeTravellingCellar真面目に計算するのは面倒くさそうなので、全通り試す。 #include <vector> using namespace std; class TimeTravellingCellar{public: int determineProfit( vector <int> profit, vector <int> decay ) { int n = (int)profit.size(); int ans = 0; for </int></int></vector>…

TimeTravellingGardener答えがN-1未満なら少なくとも2本は元の高さのままなので、2本の木の組み合わせについて木の先端を結んだ線を候補として調べる。一番短い木にあわせて切れば少なくとも1本は切る必要が無い。 #include <vector> using namespace std; class Tim</vector>…

Easy (250) 158.65 Medium (550) 0 Hard (1000) 0 Challenge 0 結果 159位 1849 → 1872250をもうちょっと早く解きたい。Topcoderのレーティング計算は点数ではなく順位が元になっているので、人がひしめき合っているところで少しでも早く解くのは意味がある…

FoxMakingDice6個の目を決めればサイコロは鏡写しの2通りなので、和がkとなる目の組み合わせがr通りあるならば、サイコロは2rC3通り。 #include <algorithm> using namespace std; class FoxMakingDice{public: long long theCount( int N, int K ) { long long ans = 0</algorithm>…

BottlesOnShelf 包除原理。複数のボールのどれかで壊れる瓶の本数を求めるのは難しいが、複数のボールのどれでも壊れる瓶はleftの最大値とrightの最小値の間でdamageの最小公倍数の倍数の瓶。 #include <vector> using namespace std; long long gcd(long long a,lon</vector>…

FoxMakingDiceEasy6個の目を決めればサイコロは鏡写しの2通りなので、和がkとなる目の組み合わせがr通りあるならば、サイコロは2rC3通り。 #include <algorithm> using namespace std; class FoxMakingDiceEasy{public: int theCount( int N, int K ) { int ans = 0; fo</algorithm>…

OneDigitDifference最上位桁を0にすれば良い。ただし、Nが0の場合は1にする。 class OneDigitDifference{public: int getSmallest( int N ) { if ( N == 0 ) return 1; for ( int i=1; ; i*=10 ) if ( N/i < 10 ) return N%i; }};

Choosing Symbol Pairs文字cの出現回数がx回ならばi,jの選び方はx2通り。 S = raw_input() print sum([S.count(c)**2 for c in set(S)])

Domino piling N,M = map(int,raw_input().split()) print N*M/2

不参加。Practiceから消えている。何があったんだろう？

Permutationsxの個数をCxとして、C1≧C2≧C3…が成り立てば良い。順列の個数はC1。答えは-1だけど入力にnより大きい数がくることもあり得る。 n = input() P = map(int,raw_input().split()) N = max(P) C = [0]*(N+1) A = [0]*n for i in range(n): C[P[i]] +=…

The Race1kmごとにガソリンスタンドがあり、ガソリン1リットルで1km進むと考えても答えは同じ。入力のi番目がsだったとすると、残っているガソリンはa*i-sリットル。そこで給油するので0

http://www.codeforces.com/contest/48/problem/B:title=Land Lot] def read(): return map(int,raw_input().split()) n,m = read() G = [read() for i in range(n)] a,b = read() ans = n*m for i in range(n-a+1): for j in range(m-b+1): t = sum([sum(g[…

Rock-paper-scissorsじゃんけん。 def win(a,b,c): return ( a=="rock" and b==c=="scissors" or a=="paper" and b==c=="rock" or a=="scissors" and b==c=="paper" ) F,M,S = raw_input(),raw_input(),raw_input() if win(F,M,S): print "F" elif win(M,S,F…

A + 00:25 B + 00:35 C + 01:52 D +1 00:49 結果 110位 1849 → 1787 Eが解けなくて悔しい。

Hieroglyphsx,yの範囲が狭いので全探索。そのままでは間に合わないので線分を座標別に分けておくことで計算量を減らす。 #include <string> #include <vector> #include <sstream> using namespace std; struct SEGMENT { int x1, y1, x2, y2; }; vector<SEGMENT> read( vector<string> s ) { vector<SEGMENT> v;</segment></string></segment></sstream></vector></string>…

QuickT9Dが空文字列になったときで区切って考える。それぞれの文字列は数字を1回以上、その後Rightを1回かCを1回以上入力して得られる文字列。各文字列について最小タイプ数を求めて、動的計画法。 #include <vector> #include <string> #include <map> #include <set> #include <sstream> using</sstream></set></map></string></vector>…

LuckyCounter #include <string> #include <vector> using namespace std; class LuckyCounter{public: int countLuckyMoments( vector <string> moments ) { int ans = 0; for ( vector<string>::iterator m=moments.begin(); m!=moments.end(); m++ ) if ( (*m)[0] == (*m)[3] && (*m)[1] =</string></string></vector></string>…

StarportN*Mの周期で繰り返すので、答えはΣi=0N-1i*M%N。NとMが互いに素ならば剰余は0〜N-1の全ての値になるので、=N(N-1)/2。 g=gcd(N,M)として、N'=N/g, M'=M/gと置くと答えは、gΣi=0N'-1i*M'%N'=gN'(N'-1)/2=N(N-g)/2。 int gcd( int a, int b ) { if ( a…

Easy (250) 120.65 Medium (550) 0 Hard (1000) 0 Challenge -25 +50 結果 1896 → 1849250に時間掛かりすぎた(´･ω･｀)

Hercule Poirot Problem動的計画法。i番目の列のj番目まで石を置いたときに得られる最大コイン数を覚えてく。O(nm)じゃないとTLE。cinを使うとTLE。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; scanf("%d%d",&n,&m); vector<long long></long></algorithm></vector></iostream>…

Parking LotLに対してnが小さいので、駐車場の状態ではなく止まっている車を記憶しておく。あらかじめ１台車を停めておくと楽。 L,b,f = map(int,raw_input().split()) n = input() P = [(-b,0,-1)] # position,length,id for i in range(n): t,l = map(int,…

Hamsters and Tigers条件を満たす動物の並びはn通りしかないので、n通りの並びについて交換の回数を数える。 n = input() A = raw_input() B = "".join(sorted(A)) ans = n for i in range(n): c = 0 for j in range(n): if A[j]!=B[j]: c += 1 ans = min(an…

T-shirts from Sponsor size = ["S","M","L","XL","XXL"] N = map(int,raw_input().split()) K = input() for i in range(K): c = raw_input() for d in [0,+1,-1,+2,-2,+3,-3,+4,-4]: t = size.index(c)+d if 0<=t<5 and N[t]>0: print size[t] N[t] -= 1 b…

Ball Game c = 0 n = input() for i in range(n-1): c = (c+i+1)%n print c+1, print

A + 00:11 B + 00:26 C + 00:34 D + 01:36 E +2 02:02 結果 81位 1745 → 1849 良い感じ。EはTLE。入力のサイズが大きい場合にcinは禁物....〆(･ω･｀ )

BallsConverterボールが３個の場合について試せば良い。(a+b)+c=a+(b+c)が成り立つならばa+b+……+zが一意になるのと同じことで数学的帰納法で証明できる、らしい。わかるようなわからないような……。 #include <string> #include <vector> using namespace std; class BallsCon</vector></string>…

BuyingFlowersrosesの要素数が小さいので全ての組み合わせを試すことが可能。バラとユリの個数の違いはR*Cが偶数ならば0、奇数ならば1。それぞれの面積に対して|R-C|の最小値を事前に求めておく。 #include <vector> #include <numeric> using namespace std; class BuyingFlo</numeric></vector>…

BadVocabulary #include <string> #include <vector> using namespace std; class BadVocabulary{public: int count( string badPrefix, string badSuffix, string badSubstring, vector <string> vocabulary ) { int ans = 0; for ( vector<string>::iterator v=vocabulary.begin(); v!=voca</string></string></vector></string>…