通常の正方形のパズルと異なり任意の配置が可能なので、並びを気にせずにinitをgoalに塗り替えるのに必要な回数を求めれば良い。 #include <string> #include <algorithm> using namespace std; class NinePuzzle{public: int getMinimumCost( string init, string goal ) { ret</algorithm></string>…

AdditionGame class AdditionGame{public: int getMaximumPoints( int A, int B, int C, int N ) { int ans = 0; for ( int i=0; i<N; i++ ) { if ( A>=B && A>=C && A>=1 ) ans+=A, A--; else if ( B>=C && B>=A && B>=1 ) ans+=B, B--; else if ( C>=A && C>=B && C>=1 ) ans+</n;>…

Easy (250) 207.96 Medium (450) 314.32 Hard (1000) 0 Challenge +100 結果 1897 → 2012Mediumで必要になる階乗が200!までと勘違いしていたけど、なんとなく多めに計算していて助かった。同じミスをしている2人を撃墜。 教訓：無駄な高速化は止めよう。制限…

FoxStones位置を交換できる石は、全てのマークからの距離が等しい石だけなので、マークからの距離でグループ分けをする。例えばそれぞれのグループの石の個数が4,2,3,1,2だったとしたら、答えは4!2!3!1!2!。 #include <map> #include <vector> using namespace std; class</vector></map>…

FoxSequenceO(N)で書けるんだろうけど、どうせ間に合うならa,b,c,dを全探索した方が、コーディングが楽だしエンバグの可能性が減ると思う。 #include <string> #include <vector> using namespace std; class FoxSequence{public: string isValid( vector <int> seq ) { int N = (</int></vector></string>…

PermutationSignature例えば、 DIIDIDD先頭にIを付加してIで分割 ID I ID IDDそれぞれのセグメント内は降順になっていて、セグメント間は昇順になっている。このときそれぞれのIを最も小さくすることを考えると、 2 1 3 5 4 8 7 6#include <string> #include <vector> using </vector></string>…

Easy (250) 144.46 Medium (550) 0 254.61 Hard (1000) 0 Challenge 0 結果 1777 → 1897最近Mediumが全然解けないorz リジャッジで550が正解になってた。1点だけど自己ベスト更新(`･ω･´)

PalindromfulString AABAACBDのように、これまでに出ていない文字が出現するときは今までに出てきた文字の辞書順次の文字、という制約を加えると候補となる文字列の数は少ない。Palindromfullな文字列にk種類の文字が出てきているなら文字を置き換えてnPk個…

MakeSquaremin{編集距離(S[0..i],S[i+1..n-1])} #include <string> #include <vector> using namespace std; // 編集距離 int editdistance( string a, string b ) { int n=(int)a.length(); int m=(int)b.length(); vector<vector<int> >T(n+1,vector<int>(m+1)); for(int i=0;i<=n;i++)T[i][</int></vector<int></vector></string>…

Filtering #include <string> #include <vector> using namespace std; class Filtering{public: vector <int> designFilter( vector <int> sizes, string outcome ) { int n = (int)sizes.size(); vector<int> ans(2); ans[0] = 100; ans[1] = 1; for ( int i=0; i</int></int></int></vector></string>

CssRules動的計画法。あるタグの子孫を正しく塗るために必要なCSS規則の個数は、そのタグの祖先によって定められたb,u,iタグの色のみに依存するので、それを覚えておく。 #include <string> #include <vector> #include <numeric> #include <algorithm> using namespace std; struct TAG { char t</algorithm></numeric></vector></string>…

AnagramFree #include <string> #include <vector> #include <algorithm> #include <set> using namespace std; class AnagramFree{public: int getMaximumSubset( vector <string> S ) { for ( vector<string>::iterator it=S.begin(); it!=S.end(); it++ ) sort(it->begin(),it->end()); return (int)set<string>(S.</string></string></string></set></algorithm></vector></string>…

OneDimensionalBalls速さは高々secondPicture.size()通り。速さを決めたとき、firstPictureとsecondPictureをソートして上下に並べ同一のボールになりうる組み合わせに線を引くと、 ／＼／＼……＼／ こんな感じの折れ線に分解できる。 ／＼／＼……／＼ ならばf…

ColoredStrokes #include <string> #include <vector> using namespace std; class ColoredStrokes{public: int getLeast( vector <string> picture ) { int h = (int)picture.size(); int w = (int)picture[0].size(); int ans = 0; for ( int y=0; y</string></vector></string>

Easy (250) 232.75 Medium (500) 0 Hard (950) 0 Challenge 0 結果 1782 → 1777500を解きたい。