PillarsDivTwo動的計画法。それぞれの塔のそれぞれの位置にロープを付ける場合の、そこまでのロープの最大の長さを覚えておく。 #include <vector> #include <cmath> #include <algorithm> using namespace std; class PillarsDivTwo{public: double maximalLength( vector <int> height, in</int></algorithm></cmath></vector>…

Pillars各dについて、x-y=dとなるロープの張り方を数えれば良い。 #include <algorithm> #include <cmath> using namespace std; class Pillars{public: double getExpectedLength( int w, int x, int y ) { double s = 0; long long c = 0; for ( int d=-x+1; d<=y-1; d++ ) {</cmath></algorithm>…

Easy (250) 235.52 Medium (500) 0 Hard (1000) 0 Challenge +50 結果 64位 2120→2148500は提出したけど、TLE(´･ω･｀)

MinimalTriangle問題の意味が分からなくて悩んだ。最小の三角形がなるべく大きくなるように対角線を引いたら、どうなりますか？ということだろうか。最小の三角形の形は常に同じ。 class MinimalTriangle{public: double maximalArea( int length ) { return…

RectangularSumSubtableの左上の数字をs、幅をw、高さをhとすると、合計はS = (1/2)wh( (w-1)+2s+width(h-1) )。よって、2Sはwhを約数に持つ。2Sの約数の個数は最悪ケース（S=963761198400）でも、7680個なので、wとhの全ての組合わせについて、sを求め、sub…

平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )(N(N+1)/2-M)/N = X/Yを変形して、N = 2(X/Y+M/N)-1Nが整数であることと、0＜M/N≦1であることから、Nはfloor(2*X/Y)とfloor(2*X/Y)+1。それぞれについてMを求めて、正しいかチェック。 from fractions…

2点間距離の最大と最小 ( Maximum and Minimum )最大は辺の長さの総和。最小は、(最長の辺の長さ)-(それ以外の辺の長さの和）。最小が0以下になるなら、2点を重ねられる。 N = input() d = [input()for x in range(N)] print sum(d) print max(0,2*max(d)-su…

2点間距離の最大値 ( The longest distance )問題サイズが小さいので全ての組合わせを試せば良い。 import math N = input() P = [map(float,raw_input().split())for x in range(N)] print "%.10f"%max(math.hypot(p[0]-q[0],p[1]-q[1]) for p in P for q in…

TwoRectanglesX軸とY軸で分けるとわかりやすい。 #include <string> #include <vector> using namespace std; int intersect( int a1, int a2, int b1, int b2 ) { if ( a2<b1 || b2<a1 ) return 0; if ( a2==b1 || b2==a1 ) return 1; return 2; } class TwoRectangles{public: string describeIntersection( vector <int> A, vector </b1></vector></string>

ContestWinner #include <vector> using namespace std; class ContestWinner{public: int getWinner( vector <int> events ) { const int N = 1000001; vector<int> num(N), last(N); for ( int i=0; i<(int)events.size(); i++ ) num[events[i]]++, last[events[i]]=i; int a</int></int></vector>…

FavouriteDigitsMがNより大きいとき、ある桁pについて、pより上位の桁ではNとMが等しく、p桁ではMの数字がNの数字より大きく、pより下位の桁は何でも良い。pより下位の桁は、digit1(d1)＜digit2(d2)ならば、0 0 … 0 d1 d1 … d1 d2 d2 … d2と並べるのが最も小…

KleofasTail2進数で考えると、最下位ビットが0なら右シフト、1なら最下位ビットを0にする。なので、Kを尻尾に含むのは、最上位ビットにKがある数。Kが偶数なら、K+1も。 #include <algorithm> using namespace std; long long f( long long K, long long A) { if ( A<0 </algorithm>…

Easy (250) 100.75 Medium (500) 0 Hard (1000) 0 Challenge +50 結果 264位 2165→2120変動幅いっぱいまで下がりそうだったから、一か八かコードにbfsという関数が見えた500に特攻したら、成功した(´･ω･｀)v 久しぶりにチャレンジした。

SpacetskE(x,0)を出発して、最後に(tx,ty)で信号を発するとすると、途中で通る格子点は出発点を含めて、gcd(tx-x,ty)個。その中から、K-1点を選ぶ。これを、出発点と最後に信号を発する点の各組合わせに対して、足し合わせる。 #include <algorithm> using namespace st</algorithm>…

ANDEquation #include <vector> using namespace std; class ANDEquation{public: int restoreY( vector <int> A ) { int N = (int)A.size()-1; for ( int i=0; i</int></vector>

SpacetskK=1ならば、格子点の個数なので、(L+1)(H+1)。垂直に発射する場合は、C(a,b)をa個の中からb個取る場合の数として、(L+1)C(H+1,K)。斜めに発射する場合、発射地点から(+dx,+dy)の格子点で最後に信号を発するとすると、途中に通過する格子点の個数は発…

StrIIRei文字目までを決めて反転数が最大になるのは、残りの文字が降順の場合。辞書順でminStr以降という条件を満たすように先頭から文字を決めていく。…dcbaは辞書順最後で反転数がn(n-1)/2なので、答えは常に存在する。 #include <string> #include <vector> using namespa</vector></string>…

Easy (275) 165.53 Medium (500) 269.83 Hard (950) 0 Challenge 0 結果 81位 2124→2165最近500のほうが簡単な気がする。

GreedyTravelingSalesman街iから街jへの道の工事後の長さで意味があるのは、街iから他の街への距離と±1、および9999のみ。全部試せば良い。 #include <string> #include <vector> #include <set> using namespace std; int n; vector<vector<int> > D; vector<bool> V; int BT( int p ) { V[p] = tru</bool></vector<int></set></vector></string>…

Easy (300) 125.90 Medium (500) 0 Hard (900) 0 Challenge 0 結果 407位 2177→2124TopCoder Open終了〜(´；ω；`)