Substring長さが異なれば、当然文字列が異なる。部分文字列の長さwと、開始位置の集合が与えられとき、長さwの部分文字列が何種類あるかを求められれば良い。接尾辞配列・LCP・RMQで共通接頭辞の長さが求められるので、それがw未満ならば異なる文字列。 #inc…

ぶんたん本番中は「貪欲でいけるんじゃね？ 間違えたところでペナルティは5分だし、試してみようw」と貪欲で書いた。実はこれが正しくて、貪欲に大きいフィボナッチ数を引いていくだけで、答えが得られる。証明。k番目のフィボナッチ数をFkとする。①Nを最小…

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ﾟ・∀・） + ﾜｸﾃｶ +