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

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

こんな問題 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"…

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

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

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

大爆発爆弾を置くy座標を決める（同じy座標に複数の爆弾を置くのもあり）と、そのように爆弾を置いて全ての壁を破壊するのに必要な爆弾の個数が求められる。そのy座標に空きが無ければ無理。それ以外の場合は、そのy座標以外にある壁を壊すのに爆弾が何個必…

席が足りない社員の部分集合ごとに何席必要かを覚えておいて、動的計画法。その社員が1席を共有できるなら、1席。そうでないならば、部分集合を2個に分割したそれぞれの席数の和の、最小値。 #include <iostream> #include <cstdio> #include <vector> using namespace std; int countb</vector></cstdio></iostream>…

camel_caseやるだけ。だが、面倒くさい。こういう問題を、正規表現とかを使って、すっきり解けるようになりたい。 import re c = raw_input() if c=="_"*len(c): print c exit(0) pre,suf = 0,0 while c[pre]=="_": pre+=1 while c[-suf-1]=="_": suf+=1 c =…

孫子算経 a,b,c = map(int,raw_input().split()) for i in range(1,128): if i%3==a and i%5==b and i%7==c: print i

FoxPaintingBalls何通りに塗り方があるか、ではなく、何個の三角形が作れるか。N=3kもしくはN=3k+2ならば、それぞれの色は同数。N=3k+1の場合、1個多い1色がある。直接計算できるのかもしれないけど、二分探索した方が簡単だと思う。オーバフローに注意。 #i…

何か忘れている気がすると思ったら、SRMだったか……。

ColorfulCupcakesDivTwo動的計画法。現在の位置、最初の人のケーキの色、前の人のケーキの色、各色のケーキの残数、ごとに配り方の数を覚えておく。 #include <string> #include <vector> #include <algorithm> using namespace std; long long M = 1000000007; vector<vector<vector<int> > > memo[50][3][</vector<vector<int></algorithm></vector></string>…

ColorfulBricks文字が1種類なら1、2種類なら2、それ以上なら0。 #include <string> #include <set> using namespace std; class ColorfulBricks{public: int countLayouts( string bricks ) { switch( set<char>(bricks.begin(),bricks.end()).size() ) { case 1: return 1; cas</char></set></string>…

ColorfulWolves色xから色yに変更可能にするコストは、colormap[x][0..y-1]の'Y'の個数。色0から色N-1への最短経路を求めれば良い。 #include <string> #include <vector> using namespace std; class ColorfulWolves{public: int getmin( vector <string> colormap ) { int INF = 999</string></vector></string>…

ColorfulChocolatesspredを最大にするとき、その色のチョコのうち1個は動かさないことが可能。動かさないチョコを決めて、そのチョコの周りに同色のチョコを何個集められるかを調べる。あるチョコを持ってくるとき、交換回数は、そのチョコとの間にある違う…

Easy (250) 0 Medium (450) 400.84 Hard (1000) 0 Challenge 0 結果 322位 2242→21612人しか解けなかった1000を考える前に、250を見直すべきだったorz

アルファベット探し異なる文字が接することは無いので、接しているoを繋げていくと、文字ごとに分けられる。あとは文字ごとにAかBかCかを調べる。最左のピクセルと最右のピクセルの位置から何倍に拡大されているかがわかる。各文字はピクセル数が異なるので…