| 
王の名前とN世が文字列で与えられるので、王の名前とローマ数字の昇順にソートして返す問題。
ローマ数字→intのルーチンで一桁目が 0 の場合に何も返してなくて failed system test. ぬるい。
手元のコンパイルのとき -Wall くらい付けたほうがいいな。
（あとで通したもの）
class KingSort { public: int ord(string s) { //The Roman numerals for 1 through 10 are I, II, III, IV, V, VI, VII, VIII, IX, and X. //The Roman numerals for 20, 30, 40, and 50 are XX, XXX, XL, and L. if(s.substr(0,1)=="L") return 50+ord(s.substr(1)); if(s.substr(0,2)=="XL") return 40+ord(s.substr(2)); if(s.substr(0,3)=="XXX") return 30+ord(s.substr(3)); if(s.substr(0,2)=="XX") return 20+ord(s.substr(2)); if(s.substr(0,1)=="X") return 10+ord(s.substr(1)); if(s.substr(0,2)=="IX") return 9; if(s.substr(0,4)=="VIII") return 8; if(s.substr(0,3)=="VII") return 7; if(s.substr(0,2)=="VI") return 6; if(s.substr(0,1)=="V") return 5; if(s.substr(0,2)=="IV") return 4; if(s.substr(0,3)=="III") return 3; if(s.substr(0,2)=="II") return 2; if(s.substr(0,1)=="I") return 1; return 0; // <- これ! } vector <string> getSortedList(vector <string> kings) { vector<pair<pair<string, int>, string> > w; REP(i, kings.size()) { stringstream ss(kings[i]); string name, o; ss>>name>>o; w.push_back(make_pair(make_pair(name, ord(o)), kings[i])); } sort(ALL(w)); vector<string> ans(w.size()); REP(i, w.size()) ans[i]=w[i].second; return ans; }
| 
与えられた手順があるので、停止するかどうかと停止したときの変数の値を求める問題。
40分くらい紙の上で考えたけど最適化できず。あとから考えるとコードを動かしながら考えれば良かった。。
（あとで）
bag0 bag1の大小で分けると、bag0 < bag1なら停止しない、そうでなければ bag0%bag1==0なら停止して bag1+bag0/bag1 が答え。
割り切れない場合は、bag0=bag2 のとこで実際にいくつか出力してみると bag0 は元々の bag0 と同じになりそうということがわかったので
bag2 関連は無視してよくて（ここがポイントっぽい）、bag1 は 1 ずつ増えて行って bag0==bag1 になったら bag0%bag1==0 になるので停止するので bag0%bag1 != 0 の場合もいずれ停止する。
というわけで N<2 なら -1, そうでなければ N の最初の約数 i に対して i+N/i を返せばよい。
O(sqrt(N)) なので 10^12 でもOK.
（あとで通したもの）
class MinskyMysteryDiv2 { public: long long computeAnswer(long long N) { if(N<2) return -1; if(N%2==0) return 2+N/2; for(ll i=3;i*i<=N;i+=2) { if(N%i==0) return i+N/i; } return N+1; }
| 
展開図が立方体になるかどうかを判定する問題。
dfs しながら立方体の底に１を貼りつけていく。回転させて再帰呼び出しして回転を戻す。
（当初戻すコードを入れてなくて入れてみたら通ったけどほんとは最初にこれで行くって思いついて検証してから書き始めなければいかんなぁ....）
int f(int x, int y, vector<string>& fig, VI& w) { //cout<<x<<" "<<y<<" "<<fig[y][x]<<endl; fig[y][x]='-'; int dx[4]={-1, 1, 0, 0}; int dy[4]={0, 0, -1, 1}; int rot[4][6]={ {2,3,1,0,4,5}, //left {3,2,0,1,4,5}, //right {5,4,2,3,0,1}, //up {4,5,2,3,1,0}, //down }; if(w[0]) return 0; w[0]=1; if(accumulate(ALL(w), 0)==6) return 1; REP(i, 4) { int yy=y+dy[i]; int xx=x+dx[i]; VI nw(6); REP(j, 6) nw[rot[i][j]]=w[j]; if(0<=yy && yy<fig.size() && 0<=xx && xx<fig[0].size() && fig[yy][xx]=='#') if(f(xx, yy, fig, nw)) return 1; REP(j, 6) w[j]=nw[rot[i][j]]; // ←最初入れてなかった } return 0; } class CubeNets { public: string isCubeNet(vector <string> fig) { VI w(6); REP(y, fig.size()) REP(x, fig[0].size()) if(fig[y][x]=='#') return f(x, y, fig, w) ? "YES":"NO"; }
| 
最適に選んだときの期待値は、残っている Red, Black の数が決まると定まる。
（ f(5, 1) の手計算でなかなか数が合わず苦労..）
漸化式は
f(r, b) = 0 (r=0)
= r (b=0)
= max(0, ( r * (1 + f(r-1, b)) + b (-1 + f(r, b-1)) ) / (r+b)) (else)
で、いつもならメモ化再帰を使うところだが、double [5001][5001] は 64MB に収まらないと気づいて、
ループDP＋メモリ使い回しを用いて double [5001] x 2 で済むようにした。
あと前 CatchTheMice で double だと微妙な誤差で通らなくて long double だと通ったトラウマ？があるので、誤差が 1e-9 までとかの場合は念のため long double を使うようになったでござる。
class RedIsGood { public: double getProfit(int R, int B) { vector<long double> dp(R+1); vector<long double> ndp(R+1); REP(r, R+1) dp[r]=r; for(int b=1;b<=B;b++) { ndp[0]=0.0; for(int r=1;r<=R;r++) { long double v = (r*(1+ndp[r-1]) + b*(-1+dp[r]))/(r+b); ndp[r] = max(v, 0.0l); } //cout<<ndp<<endl; dp=ndp; } return dp[R]; }
| 
文字列を回転させたもののうち、元の文字列と一致するものが 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; }
| 
総当りで TLE、その後 editorial 見てヒントをもらって書いた(practice system test pass)
辺の数が頂点数-1で連結なので木になる。
残りが remain 個あったとして、どれかの葉に i 個の子ノードを加える操作を（できるなら）したときの最大 score を返す。
（葉だけに加えてよいのは、葉でないノードに加える選択肢は以前のどこかで葉に加える操作に含まれるので）
その際、ルートノードだったら次数 i のノードが１個増え、次数１の子ノードが i 個増える。
ルートじゃないときは、次数１のノード（親への辺の分）が１個減り、次数 i+1 のノードが１個増え、次数１の子ノードが i 個増える。
で最初にルートが置いてあるとして、remain == 頂点数-1 として再帰関数をよびだす。
それをメモ化。
全然DP脳じゃないけどメモ化再帰脳には少しなってきたような気がするｗ
class P8XGraphBuilder { public: VI dp; int f(vector<int>& scores, int remain) { if(remain==0) return 0; if(dp[remain]!=-1) return dp[remain]; int ans = -100; for(int i=1;i<=remain;i++) { //cout<<"remain "<<remain<<" take "<<i<<" "<<scores[i]<<" "<<endl; int a = f(scores, remain-i); //cout<<"remain "<<remain<<" take "<<i<<" "<<scores[i]<<" "<<a<<" -> "<<-scores[0]+scores[i]+i*scores[0]+a<<endl; ans = max(ans, (remain<scores.size()?-scores[0]+scores[i]:scores[i-1])+i*scores[0]+a); } dp[remain] = ans; return ans; } int solve(vector <int> scores) { dp.assign(54, -1); int ans = f(scores, scores.size()); return ans; }
↓最初に書いた総当たりのコード
ルートだけの状態から出発して、既存ノードの次数ごとにノードを追加してヒストグラムを更新。
結構同じ状態があるんじゃないかと思ったけどそうでもなく爆発。
(↓だめな例)
class P8XGraphBuilder { public: int solve(vector <int> scores) { set<VI > se; VI a; a.push_back(2); se.insert(a); int ans = -100; int co=0; while(se.size()) { co++; const VI& a = *se.begin(); //cout<<"pop "<<a<<endl; if(a.size()==scores.size()) { int lans = 0; REP(i, a.size()) lans+=scores[i]*a[i]; ans=max(ans, lans); } else { REP(i, a.size()) { VI b(a); b.push_back(0); if(b[i]>0) { b[i]-=1; b[i+1]+=1; b[0]++; //cout<<b<<endl; se.insert(b); } } } se.erase(se.begin()); } cout<<co<<endl; return ans;
| 
解説とかいろいろ見てからコードだけ書いた。(practice system test pass)
２部マッチング問題の実装練習ということで。
maximumFlow() は spaghetti sourceさんより拝借。
すべての「?」について、まず０として列と列のマッチングに成功したら次へ、失敗したら１にして次へ。
最後に残ったものが辞書順最小かつヒントに矛盾しない答え。
こういう、いくつかのアルゴリズムを組み合わせる系ってすげぇと思う。
なんとかの最大値を求めるために解を仮定して二分探索するやつとか。
#define INF 1000000 typedef int Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { } }; bool operator < (const Edge &e, const Edge &f) { return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; #define RESIDUE(s,t) (capacity[s][t]-flow[s][t]) Weight maximumFlow(const Graph &g, int s, int t) { int n = g.size(); Matrix flow(n, Array(n)), capacity(n, Array(n)); REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight; Weight total = 0; while (1) { queue<int> Q; Q.push(s); vector<int> prev(n, -1); prev[s] = s; while (!Q.empty() && prev[t] < 0) { int u = Q.front(); Q.pop(); FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) { prev[e->dst] = u; Q.push(e->dst); } } if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side Weight inc = INF; for (int j = t; prev[j] != j; j = prev[j]) inc = min(inc, RESIDUE(prev[j], j)); for (int j = t; prev[j] != j; j = prev[j]) flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc; VI path; for (int j = t; prev[j] != j; j = prev[j]) path.push_back(j); path.push_back(s); reverse(ALL(path)); total += inc; //cout<<"Update "<<path<<" -> total "<<total<<endl; } } void add_edge(Graph& g, int s, int e, int w) { g[s].push_back(Edge(s, e, w)); g[e].push_back(Edge(e, s, 0)); } class P8XMatrixRecovery { public: vector <string> solve(vector <string> rows, vector <string> col) { int R = rows.size(); int C = rows[0].size(); REP(yy, R) { REP(xx, C) { if(rows[yy][xx]!='?') continue; rows[yy][xx] = '0'; int t = C*2+2-1; //cout<<"BEGIN "<<xx<<" "<<yy<<endl; Graph g(C*2+2, Edges()); REP(x, C) add_edge(g, 0, 1+x, 1); REP(x, C) add_edge(g, 1+C+x, t, 1); REP(x, C) REP(x1, C) { int ee = 1; REP(y, R) { if(rows[y][x]=='?' || col[x1][y]=='?' || rows[y][x]==col[x1][y]) { } else ee=0; } if(ee) add_edge(g, 1+x, 1+C+x1, 1); } if(C!=maximumFlow(g, 0, t)) { rows[yy][xx] = '1'; } //cout<<"RESULT "<<rows[yy][xx]<<endl; } } return rows; }
