| 
(あとで)
class PiecewiseLinearFunction { public: int maximumSolutions(vector <int> Y) { REP(i, Y.size()) Y[i]*=2; int offset[] = {-1, 0, 1}; ll ans = 0; REP(i, Y.size()) { REP(oi, 3) { ll y = Y[i]+offset[oi]; ll cnt = 0; REP(i, Y.size()) if(Y[i]==y) cnt++; REP(i, Y.size()-1) { if(Y[i]==Y[i+1]) return -1; if(min(Y[i], Y[i+1])<y && y<max(Y[i], Y[i+1])) cnt++; } ans = max(ans, cnt); } } return ans; } };
| 
class TrafficCongestion { public: int theMinCars(int TH) { ll ans = 1; REP(i, TH-1) ans = (2 * ans + (i%2==0 ? 1 : -1)) % 1000000007LL; return ans; } };
↓ちなみに modulo の数をコピペしてもコンパイル通る（けど 0 か 1 しか返らない）のでややこしい。。
class TrafficCongestion { public: int theMinCars(int TH) { ll ans = 1; REP(i, TH-1) ans = (2 * ans + (i%2==0 ? 1 : -1)) % 1,000,000,007LL; return ans; } };
| 
#define MOD 1000000007LL #define N_MAX 1300 #define K_MAX 1300 int comb[N_MAX][K_MAX]; ll combf(int n, int k) { if(!(0<=n && n<N_MAX)) return 0; if(!(0<=k && k<K_MAX)) return 0; return comb[n][k]; } class LISNumber { public: int count(vector <int> CS, int K) { REP(n, N_MAX) comb[n][0] = 1; RANGE(n, 1, N_MAX) RANGE(m, 1, K_MAX) comb[n][m] = ((ll)comb[n-1][m-1] + comb[n-1][m]) % MOD; int N=CS.size(); VVI dp(N+1, VI(K+1)); // dp[n][k] ... CS[i], i in [0, n) を使って k 個の LIS を作る方法の個数 % MOD dp[0][0] = 1; ll sum = 1; RANGE(i, 1, N+1) { RANGE(k, 1, K+1) { RANGE(pk, 0, k+1) { int add = k-pk; // in [0, k] int rest = CS[i-1] - add; ll plus = dp[i-1][pk] * combf(sum-(pk-rest)-1+add, add) % MOD * combf(pk, rest) % MOD; dp[i][k] += plus; dp[i][k] %= MOD; } } sum += CS[i-1]; } return dp[N][K]; } };
| 
class Egalitarianism { public: int maxDifference(vector <string> F, int D) { int N=F.size(); ll INF = 1LL<<50; VVI w(N, VI(N, INF)); REP(i, N) w[i][i] = 0; REP(i, N) REP(j, N) if(F[i][j]=='Y') w[i][j] = 1; REP(k, N) REP(i, N) REP(j, N) w[i][j]=min(w[i][j], w[i][k]+w[k][j]); ll d = 0; REP(i, N) REP(j, N) d=max(d, w[i][j]); return d==INF ? -1 : d*D; } };
| 
（あとで）
// 0 is good ll f(ll a, ll g) { return POPCOUNTLL(g)-POPCOUNTLL(a&g); } struct p3 { ll po, no, cost; bool operator<(const p3& b) const { return po<b.po; } }; class TurnOnLamps { public: int minimize(vector <int> R, string S, string G) { int N=R.size()+1; VI w; REP(i, N) REP(j, N) { if(i==j) continue; VI p0, p1; { int nid = i; while(nid) { p0.PB(nid-1); nid = R[nid-1]; } } { int nid = j; while(nid) { p1.PB(nid-1); nid = R[nid-1]; } } reverse(ALL(p0)); reverse(ALL(p1)); int k=0; while(k<p0.size() && k<p1.size() && p0[k]==p1[k]) k++; ll ww=0; RANGE(l, k, p0.size()) ww|=1LL<<p0[l]; RANGE(l, k, p1.size()) ww|=1LL<<p1[l]; w.PB(ww); } //cout<<w<<endl; ll bS = 0; REP(i, S.size()) if(S[i]=='1') bS|=1LL<<i; ll bG = 0; REP(i, G.size()) if(G[i]=='1') bG|=1LL<<i; if((bS & bG)==bG) return 0; // これ!! priority_queue<p3> q; q.push((p3){-f(bS, bG), bS, 0}); while(q.size()) { ll po = -q.top().po; ll no = q.top().no; ll cost = q.top().cost; q.pop(); REP(i, w.size()) { ll nno = no ^ w[i]; if((nno & bG)==bG) return cost+1; ll npo = f(nno, bG); if(npo < po) { q.push((p3){-npo, nno, cost+1}); } } } return -1; } };
| 
X---X-- {2,2} L=3の場合
1コのカメラの置き方の候補は4通り
ooo----
--ooo--
---ooo-
----ooo
1122321
（Naiveなやり方）
実際には{2,2}なので2コのカメラを置く必要がある。
置き方は4C2通り
ooooo--
oooooo-
ooo-ooo
--oooo-
--ooooo
---oooo
結果
????+??
...なんだけど、上記の方法だと40C20通りとかになる場合があって終わらない。
（工夫すると）
1コのカメラの置き方の候補からなんとかする。
ooo----
--ooo--
---ooo-
----ooo
1122321
4通りから異なる2個を選べばいい
→どう選んでも3のとこは1個以上のカメラに使われる＝監視されるので +
→2以下のとこは適切な選び方をすると監視されるようにもされないようにできるので ?
なので
????+??
みたいな
class SurveillanceSystem { public: string getContainerInfo(string C, vector <int> R, int L) { map<int, int> hi; int N=C.size(); string ans(N, '-'); REP(i, R.size()) hi[R[i]]++; FOR(e, hi) { int match=0; VI w(N); REP(i, N-L+1) { if(count(&C[i], &C[i+L], 'X')==e->first) { match++; REP(j, L) w[i+j]++; } } REP(i, N) { if(w[i]>=match-(e->second-1)) ans[i]='+'; else if(w[i]>0 && ans[i]!='+') ans[i]='?'; } } return ans; } };