CorrectMultiplicationTwo全部を1にすれば常に正しくなるので、答えは高々a+b+c-3。AとBの値を探索してA*Bがc+(a+b+c-3)より大きくなったら処理を打ち切るようにすれば、制限時間に間に合う。 #include <algorithm> using namespace std; class CorrectMultiplicationTw</algorithm>…

PointErasingTwo #include <vector> using namespace std; class PointErasingTwo{public: int getMaximum( vector <int> y ) { int n = (int)y.size(); int ans = 0; for ( int x1=0; x1</int></vector>

RowAndCoinsどちらかの端がAならばAliceが勝てる。それ以外の場合はBobの勝ち。Aliceがどちらかの端を取るなら、Bobは他方の端１個を残せる。Aliceがどちらかの端を１個だけ残すならば、Bobはその１個を残せる。AliceがB…B○○○B…B、B…B○○○A…B、B…A○○○B……Bの形…

不参加。

不参加。512回を記念して（？）点数が2の冪乗だった。

DoubleRoshambo2点となる手の組み合わせを選ばないほうが点数が高くなるということはないので、点数が高くなる手の組み合わせを貪欲に取っていけばよい。 #include <string> #include <vector> using namespace std; int game( string a, string e ) { bool w[2]; for ( int </vector></string>…

MarbleDecoration #include <algorithm> using namespace std; class MarbleDecoration{public: int maxLength( int R, int G, int B ) { return max( min(R,G+1)+min(R+1,G), max( min(G,B+1)+min(G+1,B), min(B,R+1)+min(B+1,R) )); }};</algorithm>

SubFibonacci整数2個とその整数の間隔を決めれば、フィボナッチ数列が一意に定まる。ある数より大きな数のみのフィボナッチ数列の最長部分列の長さを覚えておけば良い。 #include <vector> #include <set> #include <map> #include <algorithm> using namespace std; vector<int> S; const int </int></algorithm></map></set></vector>…

MysteriousRestaurant何日レストランに行くかを決めれば、それぞれの曜日にどの料理を食べるのが最安かが決まる。 #include <string> #include <vector> #include <algorithm> using namespace std; int c2p( char c ) { if ( '0'<=c && c<='9' ) return c-'0'+0; if ( 'A'<=c && c<='Z'</algorithm></vector></string>…

TheLuckyBasesDivTwoB進数で表したときの桁数ごとに分けて考える。1桁の場合にLuckyとなるのはnが4か7のとき。この場合lucky baseは無数に存在する。2桁の場合は4*B+4=n, 4*B+7=n, 7*B+4=n, 7*B+7=nとなるようなBが存在するかを調べる。3桁以上となる場合、B…

TheLuckyGameDivTwoBrusがある区間を選択したときに、Lucky numberの個数がいくつになるかを覚えておけば、TLEにならない。 #include <algorithm> using namespace std; int jLen, bLen; int memo[4748]; bool lucky( int x ) { for ( ; x>0; x/=10 ) if ( x%10!=4 && x</algorithm>…

TheAlmostLuckyNumbersDivTwo bool lucky( int x ) { int c = 0; for ( ; x>0; x/=10 ) if ( x%10!=4 && x%10!=7 ) c++; return c<=1; } class TheAlmostLuckyNumbersDivTwo{public: int find( int a, int b ) { int ans = 0; for ( int i=a; i<=b; i++ ) if…

TheLuckyGameDivOne選択する範囲を左から右に移動させていったときに、Johnの場合は個数が増える、Brusの場合は個数が減る場所だけ調べる。そのような場所は、BrusはLucky numberの右隣からの範囲、Johnはx+bLen-1がLucky numberとなるようなxからの範囲。 #…

SquaredSubsets戻り値がlong longだけど、答えがそんなに大きくなることはない。点集合から、その集合のみを含む正方形を求めるのではなく、正方形の位置を変えて、その正方形が含む点集合を求める。n-squaredな点集合それぞれに対して、その点集合のみを含…

RedAndGreen #include <string> #include <vector> #include <algorithm> using namespace std; class RedAndGreen{public: int minPaints( string row ) { int n = (int)row.size(); int ans = n; for ( int i=0; i<=n; i++ ) ans = min( ans, count(row.begin(),row.begin()+i,'G')+co</algorithm></vector></string>…

RangeSquaredSubsets戻り値がlong longだけど、答えがそんなに大きくなることはない。点集合から、その集合のみを含む正方形を求めるのではなく、正方形の位置や大きさを変えて、その正方形が含む点集合を求める。n-squaredな点集合それぞれに対して、その点…

MissingParentheses開いていないのに閉じている括弧の個数を足していき、最後に開いたままの括弧の分を足す。 #include <string> #include <vector> using namespace std; class MissingParentheses{public: int countCorrections( string par ) { int ans = 0; int c = 0; f</vector></string>…

Easy (250) 247.06 Medium (500) 0 (System Test Failed) Hard (1000) 0 Challenge -25 結果 511位 2017→1898500まで解けたし-25点でも順位に大差はないし、チャレンジしてみるかと思ったら失敗。そして500が落ちた。-25点のせいで300位くらい順位が落ちた………

無限庭園0,0から10,10に行くために、1000,1000を経由するような大きな遠回りが無いと仮定して、迷路を実際に作って、最短路探索。一旦、通路の中央を通る経路で最短路を求め、同じ向きに2回曲がっているごとに、最短距離から2を引く。最短経路が2種類あった…

クローゼットルームSmallならばクローゼットの置き方を全て試せる。 # coding: utf-8 import copy # 全てのクローゼットに到達可能かチェック def check(M,C): T = copy.deepcopy(M) # 入り口から到達可能なマスをDにする while True: up = False for y in r…

ワイルドカード答えは、Aのいくつかの部分文字列で*を挟んだ形になっている。全て生成して、Bにマッチしないかどうか調べる。 import re def solve(A,B): n = len(A) ans = A for i in xrange(1<<n): p = "".join(A[i] if i>>j&1 else "*" for j in range(n)) p = re.sub("\*+","*",p) i</n):>…

バクテリアの増殖SmallではBは2以下、1回目は普通に計算するとバクテリアの個数は10進数で高々3000桁。AA mod CはO(log A)で計算できる。参考。Pythonならpow関数に任せれば良い。 def solve(A,B,C): if B==1: return A**A%C else: A = A**A return pow(A,A,…

アンテナ修復並べ終わった後のエレメントの長さを、E1, E2, ……, EKとすると、面積は、 なるべく大きい数同士が隣の方が得だろうと、1 3 5 8 9 7 6 4 2という風に並べたら、正解した。 import math def solve(K,E): E = sorted(E)[::-1] T = [E[i] for i in r…

問題を一通り読んでLargeが全く分からなかったので、Small狙いで解いていったら、7位ｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!

SRMIntermissionPhase動的計画法。まずは、問題の正解状況および合計点数ごとに、各問題の点数が何通りかを求める。例えば、W[6][i]をEasyとMediumを解いてi点になる場合の数、W[7][j]をEasyとMediumとHardを解いてj点になる場合の数とすると、が成り立つ。…

SRMSystemTestPhase解いた問題の数をp、チャレンジされた問題の数をcとして、score=3p-c+3とすると、scoreの降順に並ぶのは何通りかという問題になる。i番目のコーダーのscoreがjになるようなi番目までのコーダーの結果は何通りかを覚えておいて動的計画法。…

SRMRoomAssignmentPhase #include <vector> #include <algorithm> #include <functional> using namespace std; class SRMRoomAssignmentPhase{public: int countCompetitors( vector <int> ratings, int K ) { return (int)count_if( ratings.begin()+1, ratings.end(), bind2nd(greater<int>(),ratin</int></int></functional></algorithm></vector>…

SRMCodingPhase解く問題を決めれば、できるだけ難しい問題にluckを使うのが最善。 #include <vector> using namespace std; class SRMCodingPhase{public: int countScore( vector <int> points, vector <int> skills, int luck ) { int ans = 0; for ( int s=0; s<8; s++ ) { </int></int></vector>…

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

RequiredSubstrings動的計画法。それぞれの位置で各文字列の一致長ごとに条件を満たす文字列の個数を覚えておく。計算量が507くらいになりそうだけど、実際はそんなに大きくならないらしい。 #include <string> #include <vector> #include <map> using namespace std; vector<string> wor</string></map></vector></string>…