EllysPairs 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"…

Easy (250) 246.02 Medium (500) 405.27 Hard (1000) 789.10 Challenge 0 結果 44位 2032→2083通過。全問を解けると気分が良い(･∀･)

TheFrogXは最小なので、少なくとも1個のR[i]を通る。kを整数として、X=R[i]/kとなる。またXが1未満になることはない。そのようなXを列挙してpitに落ちないかを調べる。 #include <vector> using namespace std; class TheFrog{public: double getMinimum( int D, vec</vector>…

HouseBuilding揃える高さを色々試してみれば良い。 #include <string> #include <vector> using namespace std; class HouseBuilding{public: int getMinimum( vector <string> area ) { int h = (int)area.size(); int w = (int)area[0].size(); int ans = w*h*10; for ( int i=0; i</string></vector></string>…

EllysReversals許されている操作で何ができるかを考える。文字列の長さが奇数ならば最後の1文字を動かすことはできない。先頭から2文字1組に分けたときに、その2文字をバラすことはできない。先頭を経由すると、この組は自由な場所に動かすことはできるし、2…

Easy (250) 225.76 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 186位 2032→2032

ShuffleSort数字が最小のカードがa枚、それ以外のカードがb枚ある場合に、カードを1枚減らすのに必要なシャッフルの期待回数をcとすると、c=1+cb/(a+b)。よって、c=(a+b)/a。step 2を何回も繰り返すルールは、カードが減ったときにはstep 1を省略できると考…

TheSimilarNumbers class TheSimilarNumbers{public: int find( int lower, int upper ) { int ans = 0; for ( int i=lower; i<=upper; i=i*10+1 ) ans++; return ans; }};

BallsSeparatingそれぞれの色のボールを集める箱を決めれば良い。問題の制約から各色1個以上はあるので、箱が3個未満なら-1。 #include <vector> using namespace std; class BallsSeparating{public: int minOperations( vector <int> red, vector <int> green, vector <int> blue </int></int></int></vector>…

Easy (250) 237.24 Medium (500) 0 Hard (1000) 0 Challenge -25 結果 99位 1981→2030

Easy (250) 195.87 Medium (500) 0 Hard (1000) 0 Challenge -25 結果 314位 2040→1981(´；ω；`)

PenguinTiles #include <string> #include <vector> using namespace std; class PenguinTiles{public: int minMoves( vector <string> tiles ) { int h = (int)tiles.size(); int w = (int)tiles[0].size(); for ( int y=0; y</string></vector></string>

PenguinEmperor対称性より、街iから街jに到達する旅程の数と、街i+kから街j+kに到達する旅程の数は等しい。街の数をnとする。i日目とi+n日目は同じ動きをするので、街0から出発してn日後にそれぞれの街へ到達する旅程の数を覚えておけば、それを使って、n日…

PenguinPals最適なペンギンの組合わせがあったとすると、ペンギンの並びをどこか1箇所で切って直線にできる。ペンギンが直線に並んでいたとすると、最多の組数は動的計画法で求められる。各区間内のペンギンでの最多の組数を覚えておけばよい。 #include <string> #i</string>…

PenguinSledding道が交差する可能性が無いのは、 道が0本の場合 道が1本の場合 全ての道があるチェックポイントに繋がっている場合 3本の道が三角形になっている場合 #include <vector> using namespace std; class PenguinSledding{public: long long countDesigns(</vector>…

Easy (250) 167.50 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 202位 2047→2040(´･ω･｀)

MonstersValley2全探索。 #include <vector> using namespace std; class MonstersValley2{public: int minimumPrice( vector <int> dread, vector <int> price ) { int n = (int)dread.size(); int ans = 2*n; for ( int i=0; i<1<</int></int></vector>

ValueHistogram #include <string> #include <vector> #include <algorithm> using namespace std; class ValueHistogram{public: vector <string> build( vector <int> values ) { int hist[10] = {0}; for ( int i=0; i<(int)values.size(); i++ ) hist[values[i]]++; int H = *max_element(hist,hi</int></string></algorithm></vector></string>…

TheDivisionGame重複を許した素因数の個数がGrundy数となる。よって、P[i]をiの重複を許した素因数の個数として、Pの連続した部分列でxorした結果が0ではないものを数えれば良い。各iについてP[i]を求めると間に合わないが、各素数pについてpの整数倍のP[i]…

MonstersValley動的計画法。必要なコストごとに、最高のdreadを覚えておく。 #include <vector> #include <algorithm> using namespace std; class MonstersValley{public: int minimumPrice( vector<long long> dread, vector <int> price ) { int n = (int)dread.size(); vector<long long> T(2*n+1,-1); </long></int></long></algorithm></vector>…

Easy (250) 218.80 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 237位 2065→2047(´･ω･｀)

KnightCircuit本番中には誰も解けなかった問題。要は、あるマスから到達可能な最大のマス数を返せば良い。盤面が小さいときと大きいときに分けて考える。盤面が小さいときは、実際に探索する。(0,0)から到達可能なマスに0を書き込み、0が書かれなかったマス…

AlternateColors1ステップずつ処理していては間に合わないので、まとめる。残りのボールの色数で関数を分けると、簡潔に書ける気がする。 #include <string> using namespace std; string solve2( long long c0, long long c1, long long k, string n0, string n1 ) </string>…

FauxPalindromesV.erase(unique(V.begin(),V.end()),V.end()) で連続している重複を削除できる。 #include <string> #include <algorithm> using namespace std; class FauxPalindromes{public: string classifyIt( string word ) { string r = word; reverse(r.begin(),r.end()</algorithm></string>…

AlternateColors2素朴に求めるプログラムを書いて、その結果から一般項を推測した。n=kの場合はn個のボールを赤が最多となるように塗り分ける場合の数。kを固定した場合の答えは、階差数列が等差数列になっている。 long long naive( int n, int k ) { long …

KnightCircuit2要は、あるマスから到達可能な最大のマス数を返せば良い。 class KnightCircuit2{public: int maxSize( int w, int h ) { if ( w==1 ) return 1; if ( w==2 ) return (h+1)/2; if ( h==1 ) return 1; if ( h==2 ) return (w+1)/2; if ( w==3 &…

Easy (250) 197.02 Medium (500) 205.80 Hard (850) 0 Challenge 0 結果 182位 2067→2065

SpellCardsEasy動的計画法。位置pからl枚のカードを使いr枚のカードを残す場合の最高ダメージを覚えてく。O(n5)だけど、for(x=0;x #include <vector> using namespace std; class SpellCardsEasy{public: int maxDamage( vector <int> level, vector <int> damage ) { int n = </int></int></vector>…

CoinsGameEasy全探索。 #include <string> #include <vector> using namespace std; vector<string> B; int w, h; int BT( int d, int cx1, int cy1, int cx2, int cy2 ) { bool in1 = 0<=cx1 && cx1</string></vector></string>

FoxAndHandleEasy #include <string> using namespace std; class FoxAndHandleEasy{public: string isPossible( string S, string T ) { for ( int i=0; i<=(int)S.size(); i++ ) if ( S.substr(0,i)+S+S.substr(i)==T ) return "Yes"; return "No"; }};</string>