MuddyRoad.MMMMM.という部分があるとMの個数をmとして、⌊m/2⌋回泥を踏む。それぞれの区間について、.MMMMM.の形になる確率を求めて足し合わせる。 #include <vector> using namespace std; class MuddyRoad{public: double getExpectedValue( vector <int> road ) { int n</int></vector>…

TripleStringsinit[k..n-1] == goal[0..n-k-1] ならば、init[0..k-1]のうちoをBにxをCに振り分けることで、2kでgoalにできる。oxxox → ooxxo のように答えが2nになる場合もある。 #include <string> using namespace std; class TripleStrings{public: int getMinimu</string>…

Easy (250) 0 (Challenge Succeed) Medium (500) 318.72 Hard (1000) 0 Challenge 0 結果 1773 → 1773621位なので、たぶん通過。焦って250を落としたのが勿体ない。

NumberLabyrinthDiv2ある空のセルを２回通る動きが最善になることはないので、高々K回空のセルを通りその時は好きな距離を飛べると考えても答えは同じ。スタート地点からそれぞれの地点にあとk回飛べる状態でたどり着く最短手数を幅優先探索で求める。 #incl…

PalindromizationDiv1文字列を回文にする編集回数は、文字列を２つに分けて左側と右側をひっくり返したものの編集距離を求めれば良い。左側に文字aが、右側にbがあるとき、一致させるためには、aからもbからも変換可能なある文字cがあれば良い。追加も消去も…

PalindromizationDiv2 int rev( int x ) { int r = 0; int t = x; for ( int i=1; t>0; i*=10 ) r = r*10 + t%10, t /= 10; return r; } class PalindromizationDiv2{public: int getMinimumCost( int X ) { for ( int i=0; ; i++ ) if ( X+i == rev(X+i) ||…

LuckyRemainder整数xを9で割った余りは、xの各桁の和を9で割った余りに等しい。Xの桁数をnとすると、全ての桁は2n-1回足される。 #include <string> using namespace std; class LuckyRemainder{public: int getLuckyRemainder( string X ) { int n = (int)X.length(</string>…

Easy (250) 237.68 Medium (500) 0 (Challenge succeed) Hard (1000) 0 Challenge 0 結果 1747 → 1773落ちるかと思ったけど、レーティング上がった。

YetAnotherORProblem2Div1の問題よりサイズが小さいので簡単。各桁でビットが立っているのがA0,A1,……,AN-1のうち高々1個であれば良い。k&=jは(j|k)==jとなるようなjを列挙するため。参照。単純に0≦k≦Rでループすると惜しいところでTLEだった。 class YetAnot…

CandyShop #include <vector> using namespace std; class CandyShop{public: int countProbablePlaces( vector <int> X, vector <int> Y, vector <int> R ) { int n = (int)X.size(); int c = 0; for ( int x=-200; x<=200; x++ ) for ( int y=-200; y<=200; y++ ) { bool f = true</int></int></int></vector>…

YetAnotherORProblem論理和と和が等しくなるのは、2進数でi桁目が1であるAxの個数が高々1個の場合。各桁ごとにAxのどれか1個に1を割り振るか、全てを0にする、場合の数を考える。Aiのj桁目に値を割り振る時、Ai≦R[i]を満たすためには、R[i]のj桁目が1ならば0…

DivideAndShiftシフトはいつ行っても良い。Nの約数wについて幅をwにしてからシフトを行うとすると、幅をwにするためにN/wの素因数の個数の回数分割が必要で、シフトにmin((M+w-1)%w,w-(M+w-1)%w)回かかる。 #include <algorithm> using namespace std; class DivideAndS</algorithm>…

Easy (250) 0 Medium (500) 0 Hard (1000) 0 Challenge -25 結果 1927 → 1747初マイナス点。これは痛いorz