過去問している。
250 StrangeComputer
"01010001"とか0と1だけの文字列が与えられる。
初期状態0で、よくわからないけど何回色変える必要があるか。
class StrangeComputer { public: int setMemory(string mem) { mem.erase(unique(all(mem)),mem.end()); return mem.size() - (mem[0] == '0'); } };
500 OrderedNim
先頭の山からニムニムする。むずかしい・・・。Faild出しまくった。
int memo[51] = {0}; int dfs(int n , vector<int> &s){ if(n == s.size())return 0; if(~memo[n])return memo[n]; int get = dfs(n+1,s); return memo[n] = !get || (s[n] != 1 && get) ; } class OrderedNim { public: string winner(vector <int> s) { rep(i,51)memo[i] = -1; return dfs(0,s) ? "Alice" : "Bob"; } };
1000 EnemyTowers
実装重かった。無駄なことをしている気がするけど、とりあえず配分する人数を二分探索。
struct RES{ int round,remain; RES(int a,int b){round = a , remain = b;}; }; bool operator<(const RES &a ,const RES &b){ if(a.round == b.round) return a.remain < b.remain; return a.round < b.round; } RES group(int ppl,int hpT,int numT,int attackT){ long long all = hpT * numT; int ans = 0; while(all > 0){ ans++; if(ppl <= 0) return RES(INT_MAX,0); all -= ppl; if(all > 0) ppl -= ((all+hpT-1) / hpT) * attackT; } return RES(ans,max(0,ppl)); } bool simulate(int &ref,int one,int two,int hpT, int attackT, int numWodT, int numStoT){ RES A = group(one,hpT,numWodT,attackT); RES B = group(two,hpT,numStoT,attackT); ref = min(ref,max(A.round,B.round)); return A < B; } class EnemyTowers { public: int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT) { int l = 1 , r = myUnits-1 , ans = INT_MAX; rep(i,100){ int m = (l+r) / 2; bool t = simulate(ans,myUnits-m,m,hpT,attackT,numWodT,numStoT); if(t){ l = m+1; }else{ r = m-1; } } return (ans==INT_MAX?-1:ans); } };