Checkout Assistantコンテスト中はk番目までの商品でm秒の余裕を作るのに必要な最小のお金を求めるDPでプログラムを書いていた。配列の添字が負値にもなって面倒だなと思っていたら、mにレジを通過した商品数も加えれば負にはならないと教わった。たしかに。…

World Football Cup各段階での評価項目を求めて、ソート。 import re n = input() for i in range(n): raw_input() team = {} for i in xrange(n*(n-1)/2): name1,name2,num1,num2 = re.compile("[: -]").split(raw_input()) num1,num2 = int(num1),int(num2…

#8以来の２回目。 Ａノーミス、Ｂ２ミスで、1622→1672。ギリギリ黄色。

RightTriangle赤点を描く場所は描く順番に依存しないので、先に各場所が何回選ばれるかを求め、重複の処理は後でまとめて行う。 直角三角形の斜辺は外接円の直径となるので、向かい合っていて両方に赤点が描かれている場所を数える。 #include <vector> using namesp</vector>…

ChildlessNumberskを整数として、X=kYとなるXのみ調べる。 Y = kY/D(kY) ⇔ k = D(kY) ≦ 9 log10kY = 9 log10k + 9 log10Y なので、k<200 程度で充分。 class ChildlessNumbers { int D( long long n ); public: int howMany( int A, int B ); }; int Childle…

SequenceOfCommandsコマンドを実行して、向きを変えているか移動していなければ良い。 #include <string> #include <vector> #include <numeric> using namespace std; class SequenceOfCommands { public: string whatHappens( vector <string> commands ); }; string SequenceOfCommands::wh</string></numeric></vector></string>…

OnTheFarmDivTwo #include <vector> using namespace std; class OnTheFarmDivTwo { public: vector <int> animals( int heads, int legs ); }; vector <int> OnTheFarmDivTwo::animals( int heads, int legs ) { vector<int> ans; ans.push_back( 2*heads - legs/2 ); ans.push_bac</int></int></int></vector>…

起きたら既に始まってた。

Flag 2条件から旗は２列ごとの繰り返しになるので、偶数列と奇数列の色を用いて動的計画法。色数をcとして、O(nc2(m+c2))。C++ならば充分だけど、Pythonでは間に合わない。 id:pes_magic さんにオーダーを下げる方法を教えてもらいPythonでも通った。 Python…

Seller Bob動的計画法。i日目に2xMBを手に入れて、j日目に2xMBのメモリスティックを買いに来る客がいるならば、j日目の収入はj-1日目の収入（この客にメモリスティックを売らない）とi日目の収入+2xberllar（この客にメモリスティックを売る）のどちらか大き…

Stripe切れ目の位置ごとに合計を求めると間に合わないので、動的に計算する。 n = input() s = [int(x) for x in raw_input().split()] c = 0 l,r = 0,sum(s) for i in xrange(n-1): l += s[i] r -= s[i] if l == r: c += 1 print c

Platforms着地点について考えると（たぶん）間に合わないので、それぞれの穴について考える。 n,d,m,l = [int(x) for x in raw_input().split()] for k in xrange(n): t = ((k*m+l)/d+1)*d if ( k < n-1 and t < (k+1)*m or k == n-1 ): print t break

Triangle def rightsub(x1,y1,x2,y2,x3,y3): dx1,dy1 = x2-x1,y2-y1 dx2,dy2 = x3-x1,y3-y1 return ( ( dx1 != 0 or dy1 != 0 ) and ( dx2 != 0 or dy2 != 0 ) and dx1*dx2+dy1*dy2 == 0 ) def right(x1,y1,x2,y2,x3,y3): return ( rightsub(x1,y1,x2,y2,x3,…

TwoSidedCardsこのレベルの問題をコンテスト中に通せれば、赤狙えるんだろうなと思うけど、難しい。どの数字が同じカードに書かれているかが重要で、カードの順番に意味は無い。カードをサイクルで分ける。Example 3を例にすると、 {1,3,5}, {2,4,6,7,8} {3,…

Pythonゲーｷﾀ━━━(ﾟ∀ﾟ)━( ﾟ∀)━( ﾟ)━( )━( )━(ﾟ )━(∀ﾟ )━(ﾟ∀ﾟ)━━━!!!!! b,n,c = [int(x) for x in raw_input().split()] print ((b-1)*pow(b,n-1,c)+c-1)%c+1 →Time limit exceeded orz２行目は問題無いのだけど、１行目の読み込みに時間がかかる。10進数のま…

Hierarchyそれぞれの社員についてコストが最小となる直属の上司を探す。2人以上直属の上司が居ない社員が居たら階層を作れない。1人直属の上司が居ない社員が居ればコストの和が答え。全員に直属の上司が居ればコストが最大の社員以外のコストの和。applicat…

Noldbach problem n,k = [int(x) for x in raw_input().split()] prime = [] for i in xrange(2,n+1): if all((i%p!=0 for p in prime)): prime += [i] c = 0 for i in xrange(len(prime)-1): if prime[i]+prime[i+1]+1 in prime: c += 1 if c >= k: print "…

スルー。

ColorfulTilesEasy #include <string> using namespace std; class ColorfulTilesEasy { public: int theMin( string room ); }; int ColorfulTilesEasy::theMin( string room ) { int c = 0; for ( int i=1; i<(int)room.length(); i++ ) if ( room[i] == room[i-1]</string>…

RectangularIsland問題サイズが小さければDPで簡単に求められるが、この問題だと時間が足りない。横方向と縦方向の移動を分けて考える。sステップ横方向に動いたあと島に居る確率をph(s)、縦方向をpv(s)とする。steps回の移動のうち、ちょうどi回横方向に動…

PotatoGame bool PotatoGame::win( int n ) { for ( int i=1; i<=n; i*=4 ) if ( ! win( n - i ) ) return true; return false; } こんな感じで探索すると、ジャガイモの個数をnとしてn%5が1, 3, 4なら手番を持っている側が勝ち、0, 2なら相手が勝つことがわ…

Easy (250) 229.07 Medium (600) 0 Hard (900) 0 Challenge -25 Easyで長いコードがあったので、最大ケース突っ込んでみたけどチャレンジ失敗。ちゃんとコードを読まねば。結果 1827 → 1852

Round 2で敗退。Topcoderと違って解く速さで点数が変わったりしないので、来年はもっと問題の点数に気を配ろう。