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