SRM579Div2
Easy:PrimalUnlicensedCreatures
クリーチャーが何体か居て、それぞれのレベルがvector
自分の初期レベルが与えられる。
自分より低いレベルのクリーチャーを倒すことができ、倒したクリーチャーのレベル/2(切り捨て)だけ自分のレベルがUPする。
最大何体のクリーチャーを倒すことができるか。
解法:
弱い奴から順番に倒す。
class PrimalUnlicensedCreatures { public: int maxWins(int lv, vector <int> v) { int res = 0; sort(v.begin(),v.end()); rep(i,v.size()){ if( lv > v[i] ){ lv += v[i]/2; res++; } } return res; } };
Medium:UndoHistory
変なテキストエディタを使って与えられた文字列を入力する時の、最小プレス数を求める。
・入力した文字はバッファに格納される。(1文字あたり1プレス)
・Enterキーを押すとバッファに入っている文字列がアウトプットされる。この時別にバッファはクリアされない。(1回1プレス)
・バッファの履歴が残っており、UNDOで以前の状態のバッファに復元出来る。(1UNDOにつき2プレス)
解法:
UNDOは新しい行の行頭でしか使っても意味がないから、改行する度に、バッファの続きから打つ場合・UNDOを使う場合 の2通りに点数をつける。
点数 = 節約出来る文字数 - プレス数
点数が高い方でGreedyに処理していく。
バッファの履歴は全パターン取っておかなくても、そこまでに入力した行を覚えておけば良いらしい。
class UndoHistory { public: int minPresses(vector <string> lines) { int res=0; set<string> undo; string buffer; rep(i,lines.size()){ string line = lines[i]; int score_buffer = -1*(1<<29); int score_undo = -2; int start_pos = 0; if(buffer == "" || line.find(buffer) == 0){ score_buffer = buffer.size(); } rep(j,line.size()){ string s = line.substr(0,j+1); if(undo.find(s) != undo.end()){ if(score_undo < -2+j+1){ score_undo = -2+j+1; start_pos = j+1; } } } string restline; if(score_buffer > score_undo){ restline = line.substr(buffer.size()); }else{ res += 2; restline = line.substr(start_pos); buffer = line.substr(0, start_pos); } res += restline.size(); rep(j, restline.size()){ undo.insert(buffer + restline.substr(0,j+1)); } res++; buffer = line; } return res; } };
Hard:MarblePositioning
マーブルが何個か与えられ、それらを横一列に並べた時の距離の最小値を求める問題。
解法:
最大8個なので全通り試しても40320パターンくらいしかないので全通り試す。
class MarblePositioning { public: double dist(double r1, double r2){ double a = r1+r2; double b = r1-r2; return sqrt(a*a - b*b); } double totalWidth(vector <int> R){ double res=1e20; sort(R.begin(),R.end()); do{ vector<double> P(R.size()); rep(i,R.size()){ rep(j,i){ P[i] = max(P[i], P[j] + dist(R[j], R[i])); } } res = min(res, P.back()); }while(next_permutation(R.begin(),R.end())); return res; } };