NetworkXZeroOneInteresting propertyを持つメッセージは、oxoxox……と、xoxoxo……。 #include <string> using namespace std; class NetworkXZeroOne{public: string reconstruct( string message ) { int n = (int)message.size(); string cand[2]; for ( int i=0; i</string>

RowsOrderingExample 0の{"bb", "cb", "ca"}は、1番目cb、2番目bb、51番目caと並べるのが最善。これを、1列目によってcbの順位が+0、bbの順位が+1、caの順位が+0され、2列目によってcbの順位が+0, bbの順位が+0、caの順位が+50されると考える。そうすると、…

NetworkXOneTimePad鍵の候補は、cipher[0]^plain[0], cipher[0]^plain[1], cipher[0]^plain[2], ……。平文が全て異なるという問題の制約から、この鍵の候補も全て異なる。このなかで全ての暗号文に平文が存在するものを数える。 #include <string> #include <vector> #include <algorithm></algorithm></vector></string>…

Easy (250) 200.40 Medium (500) 303.14 Hard (1000) 0 Challenge 0 結果 51位 1949→2048テストケース弱すぎw そのおかげかシステムテストで一気に順位が上がって自己ベスト更新。善哉善哉。

FortunateNumbers #include <vector> #include <set> using namespace std; class FortunateNumbers{public: int getFortunate( vector <int> a, vector <int> b, vector <int> c ) { set<int> F; for ( int i=0; i<(int)a.size(); i++ ) for ( int j=0; j<(int)b.size(); j++ ) for ( int k=0</int></int></int></int></set></vector>…

NewItemShop動的計画法。時刻、残りの剣数、それぞれの客が来たかどうかごとに最大期待値を覚えておく。客数は最大で24人だけど、1度しか来ない客が来たかどうかの情報は必要ない。1度に1人しか客が来ないという制約から、2回以上来る客は高々12人。 #includ…

NewItemShopTwo動的計画法。時刻ごと、それぞれの客が来たかどうかごとに最大期待値を覚えておく。 #include <string> #include <vector> #include <sstream> using namespace std; class NewItemShopTwo{public: double getMaximum( vector <string> customers ) { double C[24][2] = {{0}}; </string></sstream></vector></string>…

RotatedClock時間が12通り、分が60通り、時計の回転が12通り。全て試してみる。時針の角度が整数ではなくなってしまうので、分は偶数。 #include <string> #include <cstdio> using namespace std; class RotatedClock{public: string getEarliest( int hourHand, int minute</cstdio></string>…

Easy (250) 215.39 Medium (550) 0 Hard (1000) 0 Challenge 0 結果 1890 → 1949

MagicalGirlLevelTwoDivTwo(n,1), (-n,1)と跳ぶことで、上下左右に2マス移動することができるので、(偶,偶), (偶,奇), (奇,偶), (奇,奇)のマスに行くことが可能か考えれば良い。初期位置なので、(偶,偶)は可能。nが偶数ならば(1,n)→(1,n)、nが奇数ならば(1,n…

MagicalGirlLevelOneDivTwo #include <cmath> #include <algorithm> using namespace std; class MagicalGirlLevelOneDivTwo{public: double theMinDistance( int d, int x, int y ) { return sqrt( pow( max(abs((double)x)-d,0.0), 2 ) + pow( max(abs((double)y)-d,0.0), 2 </algorithm></cmath>…

MagicalGirlLevelTwoDivOne石版の数字の偶奇に着目すると、高さn幅mの長方形の繰り返しになっている。0≦i＜nと0≦j＜2mについて、y=i+kn行の偶奇がjになるような数字の置き方の数を求めておく。これを使って、全ての列が奇数個の奇数を含む数字の置き方を動的…

MagicalGirlLevelOneDivOne(n,1), (-n,1)と跳ぶことで、上下左右に2マス移動することができるので、(偶,偶), (偶,奇), (奇,偶), (奇,奇)のマスに行くことが可能か考えれば良い。初期位置なので、(偶,偶)は可能。nが偶数ならば(1,n)→(1,n)、nが奇数ならば(1,n…

Easy (250) 0 (Failed System Test) Medium (600) 268.08 Hard (900) 0 Challenge 0 結果 1792 → 1890奇数の判定をn%2==1と書いてしまい、nが負の場合があって、落ちた。n%2!=0か、(n&2)==1と書きましょうorz

MagicalGirlLevelThreeDivTwohi-lo≦1000という制約があるので、1ビットごとに0か1かを調べる。事前に各要素の長さを求めておけば、O(n2)で辿ることができる。文字列長はlong longで表現できる長さを超えうるけど、hi≦1015という制約があるので、1015以上の適…