| 
文字列を回転させたもののうち、元の文字列と一致するものが K 個になるようなのを magic word ということにして、
いくつかの文字列をいろんな順序でつなげたもののうち magic word になるようなやつの個数を求める。
class MagicWords { public: int count(vector <string> S, int K) { int N=S.size(); VI p(N); REP(i, N) p[i]=i; int L = 0; REP(i, N) L+=S[i].size(); if(L%K==0) { int ans = 0; do { string s = ""; REP(i, N) s+=S[p[i]]; for(int l=1;l<=L;l++) { if(L%l!=0) continue; int k=L/l; int ok=1; REP(i, L/k) REP(j, k) if(s[i]!=s[j*L/k+i]) ok=0; if(ok) { if(k==K) ans++; break; } } //cout<<s<<" "<<ok<<endl; } while(next_permutation(ALL(p))); return ans; } return 0; }
| 
社畜ビジネスマンが N 人円卓に座って、腕が交差しないように全員が握手する方法は何通りあるか。
ll memo[60]; ll f(int n) { ll ans = 0; if(n==0) return 1; if(memo[n]) return memo[n]; for(int i=0;i<=n-2;i+=2) { int j=n-2-i; ans+=f(i)*f(j); } return memo[n]=ans; } class HandsShaking { public: long long countPerfect(int n) { memset(memo, 0, sizeof(memo)); return f(n); }
成功体験++
| 
class MinCostPalindrome { public: int getMinimum(string s, int oCost, int xCost) { int ans = 0; REP(i, s.size()/2) { if(s[i]=='?'&&s[s.size()-i-1]=='?') ans += min(oCost, xCost)*2; else if(s[i]=='?') ans += s[s.size()-i-1]=='o'?oCost:xCost; else if(s[s.size()-i-1]=='?') ans += s[i]=='o'?oCost:xCost; else if(s[i]!=s[s.size()-i-1]) return -1; } if(s.size()&1) if(s[s.size()/2]=='?') ans += min(oCost, xCost); return ans; }
| 
↓あとで通したもの
class Cut { public: int getMaximum(vector <int> es, int mc) { int ans = 0; sort(ALL(es)); REP(jj, 2) FOR(v, es) { if(!(jj==0&&*v%10==0 || jj==1&&*v%10>0)) continue; while(*v>10 && mc>0) { *v-=10; ans++; if(*v>0) mc--; } if(*v==10) ans++; } return ans; }
| 
数直線上で蚊がそれぞれの位置から等速直線運動をする。時刻と円の中心を適切に決めて半径R以内に入る蚊の最大数を求める。
↓最初に書いただめなやつ
class Mosquitoes { public: int getMaximum(vector <int> xInit, vector <int> v, int R) { int ans = -1; //int K=2; int KT=100; REP(idx, v.size()) for(int side=-1;side<=1;side+=2) { for(int t=0;t<300*KT;t++) { double x = (xInit[idx]+(double)t/KT*v[idx])+side*R; int lans = 0; REP(i, v.size()) lans += fabs(x - (xInit[i]+(double)t/KT*v[i]))<=R; ans = max(ans, lans); } } return ans; }
↓後で通したやつ
class Mosquitoes { public: int getMaximum(vector <int> xInit, vector <int> v, int R) { int ans = -1; vector<double> ts; int N = v.size(); REP(i, N) REP(j, N) { if(i==j || v[i]==v[j]) continue; double t0 = (xInit[i]-xInit[j]-2.0*R)/(v[j]-v[i]); if(t0>=0.0) ts.push_back(t0); double t1 = (xInit[i]-xInit[j]+2.0*R)/(v[j]-v[i]); if(t1>=0.0) ts.push_back(t1); } ts.push_back(0.0); //cout<<ts<<endl; vector<double> pos(N); FOR(t, ts) { REP(i, N) pos[i] = xInit[i]+*t*v[i]; sort(ALL(pos)); REP(i, N) { for(int j=i;j<N;j++) { if(pos[j] - pos[i] <= 2.0*R+0.00000001) ans = max(ans, j-i+1); } } } return ans; }
