window.twttr = (function(d, s, id) { var js, fjs = d.getElementsByTagName(s)[0], t = window.twttr || {}; if (d.getElementById(id)) return t; js = d.createElement(s); js.id = id; js.src = "https://platform.twitter.com/widgets.js"; fjs.paren…

オーバーフローでSmallを落としたorz MinimumSquare 正方形の位置とサイズを与えられた点から決めて含まれる点の個数を調べる。サイズを二分探索することで高速化。 #include <string> #include <vector> #include <algorithm> #include <climits> using namespace std; class MinimumSquare{publ</climits></algorithm></vector></string>…

Easy (250) 224.36 Medium (500) 194.50 Hard (1000) 0 Challenge 0 結果 79位 1913→1978

TrafficCongestionDivTwo class TrafficCongestionDivTwo: def theMinCars(self, treeHeight): T = [1,1] while len(T)<=treeHeight: T += [(T[-1]+2*T[-2])] return T[treeHeight]

LISNumberDivTwo class LISNumberDivTwo: def calculate(self, seq): return sum(seq[i]>=seq[i+1] for i in range(len(seq)-1))+1

LISNumber動的計画法。小さい順にn枚のカードを選んだとき、a[i]≧a[i+1]となるiがちょうどk個になる並べ方の数を覚えておく。これは同じ数字のカードを区別した場合の数なので、最後に数字ごとにその数字のカードの枚数の階乗で割る。法Mが素数ならば、1/x =…

TrafficCongestionA001045 class TrafficCongestion: def theMinCars(self, treeHeight): T = [1,1] while len(T)<=treeHeight: T += [(T[-1]+2*T[-2])%1000000007] return T[treeHeight]

Easy (250) 219.37 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 227位 1911→1913

Easy (250) 236.65 Medium (600) 0 Hard (900) 0 Challenge 0 結果 113位 1867→1911

Easy (250) 198.76 Medium (500) 0 Hard (950) 0 Challenge 0 結果 412位 1934→1867

SemiPerfectSquare #include <string> using namespace std; class SemiPerfectSquare{public: string check( int N ) { for ( int a=1; a<=N; a++ ) for ( int b=a+1; b<=N; b++ ) if ( a*b*b==N ) return "Yes"; return "No"; }};</string>

SpaceWarDiv1疲労度で二分探索。最大の疲労度が与えられたとき、魔法少女が敵を倒せるかどうかは、弱い魔法少女をなるべく弱い敵に貪欲に割り当てて行けば分かる。 #include <vector> #include <algorithm> #include <utility> using namespace std; bool check( vector<int> girl, vector<int> ene</int></int></utility></algorithm></vector>…

Easy (250) 210.74 Medium (600) 0 Hard (1000) 0 Challenge 0 結果 114位 1885→1933

EelAndRabbitそれぞれの鰻の頭の位置を試せば充分。 #include <vector> using namespace std; class EelAndRabbit{public: int getmax( vector <int> l, vector <int> t ) { int n = (int)l.size(); int ans = 0; for ( int i=0; i</int></int></vector>

Easy (250) 188.92 Medium (600) 0 Hard (1000) 0 Challenge 0 結果 425位 1942→1885orz orz orz

MarblePositioningビー玉の個数が高々8個なので、全ての並び順を試してみれば良い。半径aと半径bのビー玉が接する距離は√((a+b)2-(a-b)2)。 #include <vector> #include <algorithm> #include <cmath> using namespace std; class MarblePositioning{public: double totalWidth( vector <int></int></cmath></algorithm></vector>…

PrimalUnlicensedCreatures #include <vector> using namespace std; class PrimalUnlicensedCreatures{public: int maxWins( int initialLevel, vector <int> grezPower ) { int level = initialLevel; for ( int c=0; ; c++ ) { int p = -1; for ( int i=0; i<(int)grez</int></vector>…

TravellingPurchasingManbitDP。まず、先頭M店の全点対間最短路を求める。Mは高々16なので、行った店と現在いる店ごとに、その状態になる最も早い時刻を覚えておく。 #include <sstream> #include <string> #include <vector> using namespace std; int countbit( int n ) { int c=0; </vector></string></sstream>…

UndoHistory貪欲法。不要な文字をundoに作るくらいなら、必要なときに作れば良い。 #include <string> #include <vector> using namespace std; int pref( string a, string b ) { a += "!"; b += "?"; for ( int i=0; ; i++ ) if ( a[i]!=b[i] ) return i; return -1; } cla</vector></string>…

Easy (250) 0 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 563位 2105→1942orz orz orz

Easy (250) 0 Medium (550) 0 Hard (1000) 0 Challenge +150 結果 332位 2141→2105250で最短距離dを求めた後に、d-1を答えにしている人がいて、チャレンジで150点稼いだ。Round3進出は無理でもTシャツを貰えるかもと思っていたら、自分の250が落ちた。何で最…

Easy (250) 147.98 Medium (500) 253.52 Hard (1000) 0 Challenge 0 結果 91位 2130→2141

Easy (250) 190.71 Medium (500) 271.20 Hard (1000) 0 Challenge 0 結果 113位 2096→2130部屋1位(･∀･)

Easy (250) 197.51 Medium (450) 245.31 Hard (850) 0 Challenge 0 結果 79位 2083→2111

NextOrPrevae→{0,1}, acb→{0,2,1}のように、各文字の文字列中での順位を表す配列を考える。startとgoalでの配列が一致していれば変換可能、一致していなければ途中で同じ文字になってしまうので不可能。変換可能なら貪欲に変換すれば良い。 #include <string> #inclu</string>…

EasyHomework #include <vector> #include <string> using namespace std; class EasyHomework{public: string determineSign( vector <int> A ) { int ans = 1; for ( int i=0; i<(int)A.size(); i++ ) ans *= A[i]>0 ? 1 : A[i]<0 ? -1 : 0; return ans>0 ? "POSITIVE" : ans<0 </int></string></vector>…

EllysBulls半分全列挙。左半分の数字を全て生成して、guessごとに何個正解しているかを数える。次に、右半分を全て生成して、何個正解しているかを数え、足し合わせるとbullsになるような左半分があるかを調べる。mapの引数にvectorはとても重いというイメー…

NewArenaPassword文字列の接頭辞でも接尾辞でもある文字列をborderという。長さnの文字列wが長さbのborderを持つ⇔wが周期n-bを持つ。一番多い文字以外を書き換える。 #include <string> #include <vector> #include <algorithm> using namespace std; class NewArenaPassword{public: in</algorithm></vector></string>…

Easy (250) 224.27 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 139位 2083→2083Mediumは探索解がTLE。卒業までにレッドコーダーに返り咲くという目標が絶望的になってきた。

EllysFigurines少なくともこの列は消すという列を決めれば、貪欲に左から消すことで最小回数が求められる。行も同様。また、消す列を決めれば、残った像がいる行を消さなければいけない。消す列を全探索する。 #include <string> #include <vector> using namespace std; int</vector></string>…