ThreeTeleports現在地・家の位置・テレポートの端点をグラフの頂点とし、マンハッタン距離を辺の重みとする。ただしテレポートの間は10とマンハッタン距離の小さい方。とすると、グラフの最短経路問題になる。頂点数が8しかないので、ダイクストラでなくても…

WhichDay #include <string> #include <vector> #include <algorithm> using namespace std; class WhichDay{public: string getDay( vector <string> notOnThisDay ) { string d[7] = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" }; for ( int i=0; i<7; </string></algorithm></vector></string>…

BinaryCardsAとBのビットが異なる最左の位置をkとすると、kビット目より左側を返すことはなく、kビット目と右側は全て表になりうる。 class BinaryCards{public: long long largestNumber( long long A, long long B ) { for ( unsigned long long i=1ull<<6…

ゼミのため不参加。

TwiceString #include <string> using namespace std; class TwiceString{public: string getShortest( string s ) { int n = (int)s.size(); for ( int i=1; i<=n; i++ ) if ( s.substr(i)==s.substr(0,n-i) ) return s + s.substr(n-i); }};</string>

ConvexSequence両隣の数より大きい数があれば小さくしていく。最大値が109だけど、1ずつ小さくなっていくというようなことはないので、TLEはしない。 #include <string> #include <vector> using namespace std; class ConvexSequence{public: long long getMinimum( vector <int></int></vector></string>…

LargestSubsequence最大の文字を加えていく。最大の文字は最左のものを選び、次の文字は最初に選んだ文字より右のものから選ぶ。 #include <string> #include <algorithm> using namespace std; class LargestSubsequence{public: string getLargest( string s ) { int n = (int</algorithm></string>…

Easy (250) 245.15 Medium (600) 317.88 Hard (1000) 0 Challenge 0 結果 196位 2048→2050とても簡単だった。簡単すぎて何か罠があるんだろうと、なかなかサブミットできなかったorz 現実の問題で解く前に難易度が分かるなんてことはないわけで、偶には点数…

CoinReversingコインが表でも裏でも裏返る確率はa[i]/N。現在の表の枚数の期待値に、裏のコインが表になる期待値を足し、表のコインが裏になる期待値を引けば、次の表のコインの枚数の期待値が求まる。 #include <vector> using namespace std; class CoinReversing{</vector>…

CuttingGrass同じ葉を2回切る意味は無い。切る葉を決めれば、growの小さいものから順に切っていくのが最善。葉をglowの値でソートしてから、動的計画法で、i番目までの葉の中からj本を切った時の最小合計長を求めていく。glowの値でソートしたことで、最後に…

MonochromaticBoardBだけの行と列を塗る。ただし、Wが1個も無ければ、幅と高さの小さい方が答え。 #include <string> #include <vector> using namespace std; class MonochromaticBoard{public: int theMin( vector <string> board ) { int h = (int)board.size(); int w = (int)boa</string></vector></string>…

AdjacentSwapsそれぞれのカードの移動前の後の位置から、ウサギが呼ばれる順番の満たす制約が得られる。例えば4番目の例の 1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15, 19, 17だと、3が3番目から1番目に移動していることで、数字をウサ…

CompositeSmash動的計画法。場合分けして解く方法もあるらしいけど、コンテスト中にミス無く書ける自信が無い……。 #include <string> #include <vector> using namespace std; vector<int> memo; int target; bool f( int n ) { if ( n==target ) return true; if ( memo[n]>=0 ) </int></vector></string>…

Easy (250) 213.85 Medium (600) 0 Hard (1000) 0 Challenge 0 結果 214位 2048→2048600が解けなかったけど、レーティングは変わらず。良かった。

NetworkXMessageRecovery先頭から順に元のメッセージを決定していく。いずれかのmessagesの中で2文字目以降に表れる文字は使用できないので、それ以外で辞書順最小の文字を選択する。たとえば、Example 0の場合、{acd,bce} aとbを比較してaの方が小さいのでa…

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以上の適…