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

PastingPaintingDivTwoある程度繰り返せば、ピクセル数の変化は一定になる。 #include <string> #include <vector> using namespace std; class PastingPaintingDivTwo{public: long long countColors( vector <string> clipboard, int T ) { int H = (int)clipboard.size(); int W =</string></vector></string>…

CucumberMarket #include <vector> #include <algorithm> #include <numeric> #include <functional> using namespace std; class CucumberMarket{public: string check( vector <int> price, int budget, int k ) { sort(price.begin(),price.end(),greater<int>()); return accumulate(price.begin(),price.be</int></int></functional></numeric></algorithm></vector>…

CheckerFreenessわかんね(・3・) 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.twi…

FoxAndHandleHの接頭辞を決めたとき条件を満たすかどうかは、SからHの文字をできるだけ左から選んでいき、各文字について選んだ個数と残りの部分の個数を合わせて、総数の半分に達するかどうかを調べればわかる。これを使って、Hを先頭から順に決めていく。 …

Easy (300) 0 Medium (500) 226.22 Hard (950) 0 Challenge 0 結果 191位 2093→2067300はシステムテストで落ちた。きっちり証明できないけどたぶん合っているだろうというアルゴリズムは、たいてい間違えている(´･ω･｀)

PastingPaintingDivOneある程度繰り返せば、ピクセル数の変化は一定になる。 #include <string> #include <vector> using namespace std; class PastingPaintingDivOne{public: vector<long long> countColors( vector <string> clipboard, int T ) { int H = (int)clipboard.size(); int W = (i</string></long></vector></string>…

Easy (250) 213.67 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 not rated500まで過去最高の出来 → 500再提出(´･ω･｀) → システム500落ちる(´･ω･｀) → 皆500落ちているし250が早かったので良い順位(`･ω･´) → not rated( ´ ･ ω ･ ｀ )

TypingDistance #include <string> #include <cstdlib> using namespace std; class TypingDistance{public: int minDistance( string keyboard, string word ) { int ans = 0; int p = 0; for ( int i=0; i<(int)word.size(); i++ ) { int t = 0; while ( keyboard[t]!=word[</cstdlib></string>…

DrawingPointsDivOne問題文では古い点が幅1の正方形になっていると中央に新しい点を描くと言っているけど、中央ではなく左下の点と考えると、扱いが楽になる。WojtekがSステップ処理を行うことができるかどうかは、Sステップ戻してからSステップ進めて、余計…

TomekPhone出現数の多い文字から順に、キーストロークの少ない位置に割り振っていく。 #include <algorithm> #include <vector> #include <functional> using namespace std; class TomekPhone{public: int minKeystrokes( vector <int> occurences, vector <int> keySizes ) { sort(occurences.begin(</int></int></functional></vector></algorithm>…

Easy (250) 233.55 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 190位 2107→2093

ToyTrain実は線路の引き方は高々1通りしかない。左上から順にカーブを見ていき、例えば、そのカーブに上から線路が繋がっていて左から繋がっていなければ『┗』、上からも左からも線路が繋がっていなければ『┏』。カーブの向きを決めたら、右や下に線路が繋が…

BlockTower偶偶偶奇奇 という積み方になる。 #include <vector> #include <algorithm> using namespace std; class BlockTower{public: int getTallest( vector <int> blockHeights ) { int n = (int)blockHeights.size(); int ans = 0; for ( int i=0; i<=n; i++ ) { int s = 0; for</int></algorithm></vector>…

HatRackある部分木が正しいラックになる条件は、子の個数が2個以下で、両方の子の高さが同じで少なくとも一方が完全二分木であること、もしくは両方の子の高さの差が1で、短い方が完全部分木であること。子が1個しかなければ、もう一方は高さが0の完全二分木…

HyperKnightある場所からk回で移動できる場所の個数を聞かれているのだと勘違いして10分悩んだ(´Д｀； ) k通りの移動ができる場所の個数を答えるのか。盤面が以下のように25個の部分に分けられて、それぞれの移動可能数がセルの数字になる。幅は一番外側がa,…

Easy (250) 182.62 Medium (500) 227.92 Hard (900) 0 Challenge 0 結果 25位 2007→2107過去最高順位(･∀･)

LeftRightDigitsGame動的計画法。digitsのi文字目まで使ったときに、位置pから始まる最小の文字列を覚えておく。 #include <vector> #include <string> using namespace std; class LeftRightDigitsGame{public: string minNumber( string digits ) { int n = (int)digits.si</string></vector>…

ChocolateBar #include <string> #include <set> using namespace std; class ChocolateBar{public: int maxLength( string letters ) { int n = (int)letters.size(); for ( int w=n; w>0; w-- ) for ( int i=0; i<=n-w; i++ ) if ( int(set<char>(letters.begin()+i,letters.b</char></set></string>…

LeftRightDigitsGame2AがBより大きいということと、次の条件を満たす整数cp(0≦cp≦|A|)が存在することは、同値である。 i<cp ⇒ A[i]==B[i] ∧ i==cp ⇒ A[i]>B[i]cpを決めて、動的計画法。digitsのi文字目まで使ったときに、位置pから始まる最小の文字列を覚えておく。 #include <string> #include <vector> usin</vector></string></cp>…

XorTravelingSalesman拡張ダイクストラ。(街,利益)を1個のノードと見なす。街Xに到達できるならば、0→a→b→X→b→a→0と同じ経路を往復することで、街Xの点数だけを得られるので……という解き方もあるとチャットで聞いた。 #include <string> #include <vector> #include <queue> using n</queue></vector></string>…

Easy (250) 0 Medium (500) 306.01 Hard (1000) 0 Challenge 0 結果 81位 2146→2168× if ( roads[c][i] ) ○ if ( roads[c][i]=='Y' ) これはひどいorz

TheBrickTowerHardDivTwo動的計画法。高さ、上面のブロックの色、隣接した同色のブロックの個数ごとに、何通りの塔があるかを覚えておく。 class TheBrickTowerHardDivTwo{public: int find( int C, int K, int H ) { long long M = 1234567891; static long…

TheBrickTowerMediumDivTwo全探索。 #include <vector> #include <algorithm> using namespace std; class TheBrickTowerMediumDivTwo{public: vector <int> find( vector <int> heights ) { int n = (int)heights.size(); int m = 99999999; vector<int> ans; vector<int> v; for ( int i=0; i</int></int></int></int></algorithm></vector>

TheBrickTowerEasyDivTwo赤と青が接しないようにブロックを並べられるのは、個数の差が1個以下の場合。 #include <set> using namespace std; class TheBrickTowerEasyDivTwo{public: int find( int redCount, int redHeight, int blueCount, int blueHeight ) { </set>…

TheBrickTowerMediumDivOne最初の塔と最後の塔の間隔が最小となるならば、最初の塔か最後の塔の少なくともどちらか一方は最長である。なぜならば、そうでなければ、両端の塔と最長の塔を交換することで、より間隔を小さくできてしまうから。最長の塔を最初か…

TheBrickTowerEasyDivOne同じ色が隣接しないという制約から、赤と青を交互に並べるしかない。赤と青の高さと個数が等しいかどうかで場合分けする。高さが等しい場合はブロックの個数。等しくない場合、(赤青)(赤青)(赤青)(␣青)のように、2個ずつのグループに…

Easy (250) 210.43 Medium (500) 293.86 Hard (1000) 0 Challenge 0 結果 113位 2121→2146また赤が見えてきた+（0ﾟ・∀・） + ﾜｸﾃｶ +

Suminator試しに0にしてみて、wantedResultになるなら0。そうでない場合、1個の数字は高々1回しか結果に足されないので、-1の箇所が足されるかどうかを調べる。足されないならば、ここで得られた結果とwantedResultが等しくなければいけない。足される場合、…

Easy (250) 198.29 Medium (500) 0 Hard (1000) 0 Challenge -25 結果 178位 2160→2121チャレンジミスorz