Easy (250) 169.87 Medium (500) 0 Hard (1000) 0 Challenge +50 -25 結果 390位 2085→2007( ´ ･ ω ･ ｀ )

SumOfLuckinesslucky(x)を0からxまでのluckinessの合計とすると、答えはlucky(B)-lucky(A-1)。まずは、iとjそれぞれについて、i桁以下で(4の個数)-(7の個数)=jとなる整数の個数T[i][j]を動的計画法で求める。例えば、x=526とすると、0-99, 100-199, 200-299,…

MagicalSquareS[0][0], S[0][1], S[1][0], S[1][1]を決めれば、残りのマスも定まる。事前にrowStrings, columnStringsのそれぞれの位置からの最長一致長を求めて高速化する。 #include <string> #include <vector> using namespace std; class MagicalSquare{public: long lo</vector></string>…

CheatingQuiz #include <string> #include <set> #include <vector> using namespace std; class CheatingQuiz{public: vector <int> howMany( string answers ) { vector<int> ans; for ( int i=0; i<(int)answers.length(); i++ ) ans.push_back(set<char>(answers.begin()+i,answers.end()).siz</char></int></int></vector></set></string>…

PrimeCompositeGameK=1の場合はシミュレートする。K>=2のとき、2個の素数の間にKより大きな隙間があると、そこに追い込まれて私が負ける。それ以外の場合は2を取られて、Dengklekが負ける。勝つ方はなるべく多く、負ける方はなるべく少なく取れば良い。 #inc…

不参加。

RainyRoad #include <string> #include <vector> using namespace std; class RainyRoad{public: string isReachable( vector <string> road ) { for ( int i=0; i<(int)road[0].size(); i++ ) if ( road[0][i]=='W' && road[1][i]=='W' ) return "NO"; return "YES"; }};</string></vector></string>

Rumor聞いた噂はなるべく広めたほうが良いし、１度広めた噂をもう1度広める意味は無いので、噂の広がるスピードを決めるのは、両方の噂を同時に聞いた場合に次のステップでどちらを広めるかということのみ。N≦16なので、それぞれのウサギがどちらの噂を先に…

DropCoins残るのは矩形の中にあるコイン。全ての矩形についてコインがK枚かどうかを調べる。 #include <string> #include <vector> using namespace std; class DropCoins{public: int getMinimum( vector <string> board, int K ) { int H = (int)board.size(); int W = (int)board[</string></vector></string>…

MultiplesWithLimit最初の例だと、1桁目は0で4が繰り上がる。2桁目は0で繰り上がるのは2か7。2が繰り上がっている場合は次に繰り上がるのは1か5……。頂点数Nの有向グラフを考えて、0, 1, ……, N-1を割り当てる。aが繰り上がっているときに制限を満たす数字を出…

CorrectMultiplication |A-a|+|B-b|+|AB-c|A,B≧1であることから、Aを固定してBを動かしたとき、BよりABのほうが大きく動くので、AB=cとすると値が最小になる。整数なので、その近辺の値を調べる。AとBのうち小さい方を動かすと、A, Bの最大値をnとして、O(√n…

P8XCoinChangeAnotherans[]を辞書順最小の解、ans[i]≧2とすると、j≧i+2についてans[j]=0。なぜならば、ans[j]>0となるjが存在したとすると、ans[i]-=2, ans[i+1]+=1, ans[j-1]+=2, ans[j]-=1として、より辞書順の小さい解が作れてしまう。すなわち、ansの中…

P8XMatrixTransformation1種類の操作しかできないと言いながら、任意の配置にすることが可能なので、1の個数が等しいかどうかだけ見れば良い。 #include <string> #include <vector> using namespace std; class P8XMatrixTransformation{public: string solve( vector <string> orig</string></vector></string>…

P8XMatrixRecovery頂点数が2Cの二部グラフを考える。rowsのi番目の列と、columnsのj番目の要素に、矛盾が無ければ、左側のi番目の点と右側のj番目の間に辺があるとする。この二部グラフに完全マッチが存在する時かつその時に限り、マトリックスが存在する。…

P8XGraphBuilder動的計画法。点数がiで木の数がjの森の最大コスコアを覚えておけば良い。それぞれの木に片方だけが繋がった辺（？）が１本ずつあるとして計算しておくと楽。点数が２以上ならば次数１の頂点が少なくとも１個あるはずなので、そこを最後にする…

Easy (275) 127.51 Medium (450) 301.90 Hard (1050) 0 Challenge 0 結果 143位 2057→2085

DucksAlignmentカモの並べ方について全探索。カモのxとy座標をそれぞれソートしておけば、順番に並べるのが最適。問題の１列にカモは高々１匹という制約から、カモの移動中に他のカモが邪魔になることはない。 #include <string> #include <vector> #include <algorithm> using namespac</algorithm></vector></string>…

Easy (250) 207.70 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 137位 2064→2056

ShippingCubes #include <algorithm> using namespace std; class ShippingCubes{public: int minimalCost( int N ) { int ans = N+2; for ( int x=1; x<=N; x++ ) for ( int y=1; y<=N; y++ ) for ( int z=1; z<=N; z++ ) if ( x*y*z==N ) ans = min( ans, x+y+z ); re</algorithm>…

LongestSequenceCの要素数が2の場合が↓に載っていた。数列の長さが絶対値の和を超えることは無いらしい。Solution for October 2008 - Math Central長さnの数列vを考える。Si = Σj=0i-1v[i]とすると、長さkの全ての連続した部分列の和が正であることと、Si<Si+kが全てのiについて成り立つことは同値。Sの大小関係が決まるので、それをグラフの有向辺として、グラフが閉路を持たなければそのような数列Sが作れる。閉路があればSは作れない。順番に調べていっても間に合ったけど、二分探索の方が安全。 #include <vector> u</si+kが全てのiについて成り立つことは同値。sの大小関係が決まるので、それをグラフの有向辺として、グラフが閉路を持たなければそのような数列sが作れる。閉路があればsは作れない。順番に調べていっても間に合ったけど、二分探索の方が安全。>…

MagicDiamondsn=1ならば1回、n=2ならば2回、n=3ならば3回。nが4以上の素数ならばn-1は必ず合成数になるので、2回。 class MagicDiamonds{public: long long minimalTransfer( long long n ) { if ( n<=3 ) return n; for ( long long i=2; i*i<=n; i++ ) if …

Easy (250) 238.90 Medium (500) 190.54 Hard (900) 0 Challenge 0 結果 48位 1962→20642000点台復帰＆自己ベスト更新(`･ω･´)

SmallBricks31動的計画法。下から順にブロックを積んでいき、現在のx,y座標と上に出ているブロックの配置ごとにパターン数を覚えておく。 #include <vector> using namespace std; int M = 1000000007; int w, h; vector<int> B; vector<vector<vector<int> > > memo; int BT( int x, int y )</vector<vector<int></int></vector>…

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

BricksN動的計画法。幅iのブロックの上に高さが高々jになるようにブロックを積む場合の数を覚えておく。全くブロックを積まない場合が１通り。あとは最左のブロックの固まりを置く場所ごとに、ブロックの固まりの作り方×上の積み上げ方×１つ隙間を空けて右の…

CountingSeries等比数列は数が少ないので、等差数列の個数をまず求め、等差数列に含まれない等比数列の要素の個数を加える。 d==1は別扱いしないと処理が終わらないとか、upperBound

Easy (250) 224.93 Medium (500) 270.51 Hard (900) 0 Challenge 0 結果 109位 1898→1962また2000点台が見えてきた(`･ω･´)

CorrectMultiplicationTwo全部を1にすれば常に正しくなるので、答えは高々a+b+c-3。AとBの値を探索してA*Bがc+(a+b+c-3)より大きくなったら処理を打ち切るようにすれば、制限時間に間に合う。 #include <algorithm> using namespace std; class CorrectMultiplicationTw</algorithm>…

PointErasingTwo #include <vector> using namespace std; class PointErasingTwo{public: int getMaximum( vector <int> y ) { int n = (int)y.size(); int ans = 0; for ( int x1=0; x1</int></vector>

RowAndCoinsどちらかの端がAならばAliceが勝てる。それ以外の場合はBobの勝ち。Aliceがどちらかの端を取るなら、Bobは他方の端１個を残せる。Aliceがどちらかの端を１個だけ残すならば、Bobはその１個を残せる。AliceがB…B○○○B…B、B…B○○○A…B、B…A○○○B……Bの形…