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…