JAG 夏合宿 Day3 G - Share the Ruins Preservation
問題
jag2016autumn.contest.atcoder.jp
二次元平面上に点が N 個与えられる。ある X 座標を境に二つの頂点を分割し, それぞれで凸包を作る。この二つの凸包の面積の和を最小化せよ。
解法
蟻本に載っている凸包は, 凸包の下側と上側に分けて凸包を構成します。上側の凸包を構成するのは, y 座標の上下を逆転させて下側の凸包を構成するのと同じようにできます。よって, 下側凸包を構成しながらそれぞれの凸包の面積を更新していく, というように計算すれば, O(N log N) で
- X 座標の左から見ていった下側凸包
- X 座標の左から見ていった上側凸包(Y 座標を -1 倍すれば良い)
- X 座標の右から見ていった下側凸包(X 座標を -1 倍すれば良い)
- X 座標の右から見ていった上側凸包(X, Y 座標を -1 倍すれば良い)
の面積をそれぞれ計算できます。これを適当に組み合わせて最小値を求めましょう。
すこし注意なのは, 点をソートすべきタイミングです。X 座標の左側から凸包を考えている際, Y 座標を -1 倍した後にソートしてしまうと, 点の位置関係がずれる可能性があるのでソートしてはいけません。
typedef long long Real; struct P { Real x, y; P() {} P(Real x, Real y) : x(x), y(y) {} P operator-(P p) const {return P(x-p.x, y-p.y);} Real det(P p) const {return x*p.y-y*p.x;} // 外積 bool operator<(const P& rhs) const { if (x != rhs.x) return x < rhs.x; return y < rhs.y; } }; ll triArea(const P& x, const P& y, const P& z) { return abs((y-x).det(z-x)); } // 下側凸包の面積を求める vector<ll> convex_hull(vector<P> ps) { int n = ps.size(); int k = 0; // 凸包の頂点数 vector<P> qs(n); // 構築中の凸包 vector<ll> area(n+1); // 下側凸包の作成 for (int i = 0; i < n; i++) { area[i+1] = area[i]; while (k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) < 0) { if (k >= 3) area[i+1] -= triArea(qs[0], qs[k-2], qs[k-1]); k--; } if (k >= 2) area[i+1] += triArea(qs[0], qs[k-1], ps[i]); qs[k++] = ps[i]; } return area; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<P> ps(N); for (int i = 0; i < N; i++) { cin >> ps[i].x >> ps[i].y; } sort(ps.begin(), ps.end()); auto lb = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].y *= -1; auto lu = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].x *= -1; sort(ps.begin(), ps.end()); auto ru = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].y *= -1; auto rb = convex_hull(ps); for (int i = 0; i < N; i++) ps[i].x *= -1; sort(ps.begin(), ps.end()); ll ans = lb[N] + lu[N] + ru[0] + rb[0]; for (int i = 1; i < N; i++) { if (ps[i-1].x == ps[i].x) continue; // cout << i << endl; // cout << lb[i] << " " << lu[i] << " " << rb[N-i] << " " << ru[N-i] << endl; ll tmp = lb[i] + lu[i] + ru[N-i] + rb[N-i]; ans = min(ans, tmp); } cout << (ans+1)/2 << endl; return 0; }
JAG 夏合宿 Day3 F - Escape from the Hell
問題文は面白かったんですが実装はつらかったです。
解法
最後に A[i] 登るところ以外は, 明らかに D[j] = A[j] - B[j] が大きい順に使うのが最適です。この j をどこまで使うかで場合分けします。
j の最大値も j < i を満たす場合
あらかじめ sumD[i] = D[0] + D[1] + ... + D[i-1], sumC[i] = C[0] + ... + C[i-1] を計算して, sumD[ok] > sumC[ok] を満たす ok の最大値を覚えておきます。
A[i] + sumD[j] >= L を満たす j の最小値のうち, j <= ok となるものがあれば j+1 は解の候補です。
j の最大値が j > i を満たす場合
こっちが少しめんどくさいです。
この場合の上り方を見ると, 以下のようになっています。
D[0] D[1] D[2] ... D[i-1] D[i+1] ... D[j]
C[0] C[1] C[2] ... C[i-1] C[i] ... C[j-1]
よって, seg[i] = sumD[i] - sumC[i-1] というものを覚えておいて, min(seg[i+1], seg[i+2], ..., seg[j]) - D[i] > 0 でありかつ i-1 <= ok であれば良いです。
// セグメント木(RMQ 対応) // update: k 番目の値を a に変更 // query: [l, r) の区間の最大値を求める template<typename T> struct ST { vector<T> seg; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(2*size-1, numeric_limits<T>::max()); } inline T merge(T x, T y) { return min(x, y); } void update(int k, T a) { k += size-1; seg[k] = a; while (k > 0) { k = (k-1)/2; seg[k] = merge(seg[k*2+1], seg[k*2+2]); } } T query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return numeric_limits<T>::max(); if (a <= l && r <= b) return seg[k]; T vl = query(a, b, k*2+1, l, (l+r)/2); T vr = query(a, b, k*2+2, (l+r)/2, r); return merge(vl, vr); } T query(int a, int b) { return query(a, b, 0, 0, size); } }; const int INF = 1e9; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, L; cin >> N >> L; vector<pii> P(N); for (int i = 0; i < N; i++) { cin >> P[i].first >> P[i].second; } sort(P.begin(), P.end(), [](const pii& lhs, const pii& rhs){ if (lhs.first-lhs.second == rhs.first-rhs.second) return lhs.first < rhs.first; return lhs.first-lhs.second > rhs.first-rhs.second; }); vector<int> A(N), B(N), D(N); for (int i = 0; i < N; i++) { A[i] = P[i].first; B[i] = P[i].second; D[i] = A[i] - B[i]; } vector<int> C(N); for (int i = 0; i < N; i++) cin >> C[i]; vector<ll> sumD(N+1), sumC(N+1); for (int i = 0; i < N; i++) { sumD[i+1] = sumD[i] + D[i]; sumC[i+1] = sumC[i] + C[i]; } int ok = -1; for (int i = 1; i <= N; i++) { if (sumD[i] - sumC[i] > 0) { ok = i-1; } else break; } // cout << "A B" << endl; // for (int i = 0; i < N; i++) { // cout << A[i] << " " << B[i] << endl; // } // cout << endl; // cout << "ok" << endl; // cout << ok << endl << endl; int ans = INF; { int maxi = 0; for (int i = N-1; i >= 0; i--) { maxi = max(maxi, A[i]); if (i-1 <= ok && maxi + sumD[i] >= L) ans = min(ans, i+1); } } ST<ll> seg(N+1); for (int i = 1; i <= N; i++) { seg.update(i, sumD[i] - sumC[i-1]); } for (int i = 0; i <= min(ok+1, N-2); i++) { // (low, high] int high = N-1, low = i; while (high - low > 1) { const int med = (high+low) / 2; if (sumD[med+1] + B[i] >= L) high = med; else low = med; } if (sumD[high+1] + B[i] < L) continue; //cout << i << " " << high << endl; //cout << seg.query(i+1, high+2) << endl; if (seg.query(i+1, high+2) > D[i]) ans = min(ans, high+1); } //cout << endl; if (ans == INF) ans = -1; cout << ans << endl; return 0; }
SRM 566 div1 med: PenguinEmperor
解法
入力の名前が長いので, n, m とします。
見た目からして行列累乗っぽい感じがします。
具体的には, まず dp[i][j] = (i 日目に場所 j にいるような場合の数) というのを i <= n についてやります。任意の i について, i 日目の移動の仕方は, i%n 日目のものと一致するので, これだけ調べれば十分です。
で, それを調べ終わったら m/n 回分の行列の掛け算, それと m%n 回分の移動を合わせて答えに組み込めば OK という感じです。
ただ, 今回は n の制約が大きいので行列累乗して O(n^3 log m) にすると危なそうです。ですが, 今回の問題では i -> i+k に移動するような場合の数は, i の値にかかわらず一定になるので, わざわざ行列を作らなくても良く, O(n^2) で計算できます。具体的には,
vector<ll> mul(vector<ll> a, vector<ll> b) {
int n = a.size();
vector<ll> ret(n);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
(ret[(i+j)%n] += a[i] * b[j] % MOD) %= MOD;
}
return ret;
}
このようにすれば良いです。
const int MAXN = 355; const int MOD = 1e9+7; ll dp[MAXN][MAXN]; vector<ll> mul(vector<ll> a, vector<ll> b) { int n = a.size(); vector<ll> ret(n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { (ret[(i+j)%n] += a[i] * b[j] % MOD) %= MOD; } return ret; } class PenguinEmperor { public: int countJourneys(int n, long long m) { memset(dp, 0, sizeof(dp)); // numCities 後 0 から i に行く場合の数を数える dp[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int cw = (j+i+1)%n; int ccw = (j-i-1+n)%n; (dp[i+1][cw] += dp[i][j]) %= MOD; if (cw != ccw) { (dp[i+1][ccw] += dp[i][j]) %= MOD; } } } ll r = m/n, q = m%n; // r 回は累乗っぽいことをやる vector<ll> t(n), tn(n); for (int i = 0; i < n; i++) { t[i] = dp[q][i]; tn[i] = dp[n][i]; } for (int i = 0; i <= 60; i++) { if ((r>>i)&1) { t = mul(t, tn); } tn = mul(tn, tn); } return t[0]; } };
SRM 566 div1 easy: PenguinSledding
問題
TopCoder Statistics - Problem Statement
n 頂点の無向グラフが与えられる。このグラフから辺をいくつか選ぶとき, 以下の条件を満たす選び方の場合の数を求めよ。
条件: 選んだ辺上の頂点を 2 次元平面上でどのように配置しても(ただし 3 頂点が同一直線上に来るようにはしない), 選んだ辺同士で交差しない。
解法
あり得る状況としては,
- 単なる辺
- ある頂点にのみたくさん辺がついた感じ(star graph とか言われる)
- 三角形
の三通りがあります(多分三角形が一番気付きにくい)。
star graph に関しては, ある頂点 v に接続する頂点の数を num として, 2^num - 1 - num を計算すれば良いです。
class PenguinSledding { public: long long countDesigns(int n, vector <int> checkpoint1, vector <int> checkpoint2) { ll cnt = 0; int m = checkpoint2.size(); for (int i = 1; i <= n; i++) { ll S = 0; for (int j = 0; j < m; j++) { if (checkpoint2[j] == i || checkpoint1[j] == i) { int v = (checkpoint1[j] == i ? checkpoint2[j] : checkpoint1[j]); S |= 1ll<<v; } } int num = __builtin_popcountll(S); // 次数が 2 以上になるやつ if (num >= 2) { cnt += 1ll<<num; cnt -= 1 + num; } } ll ret = cnt+m+1; for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) for (int k = j+1; k < m; k++) { set<int> S; S.insert(checkpoint1[i]); S.insert(checkpoint2[i]); S.insert(checkpoint1[j]); S.insert(checkpoint2[j]); S.insert(checkpoint1[k]); S.insert(checkpoint2[k]); if (S.size() == 3) ret++; } return ret; } };
JAG 夏合宿 Day2 A - Parades
問題
jag2016summer-day2.contest.atcoder.jp
N 頂点からなる木がある。各頂点の次数はたかだか 10 である。
このグラフ上でいくつかのパレードを開きたい。パレードの候補は M 個あり, その各パレードは頂点 u から 頂点 v へのパスで構成される。
これらのパレードは同時開催するため, 開くパレードはすべてパスの辺を共有していてはならない。最高でいくつのパレードを開けるかを求めよ。
解法
藤原さんの解答を参考にしました。
基本的には木 DP で, dp[v][s] = (頂点 v から伸びている辺のうち, s で表される集合の辺は使ったときに開催できるパレードの数の最大値) とします。
パレードはパスで表されるので, u, v の lca で特徴づけることができます。u -> lca -> v と移動する場合, lca では u 側に降りるために使う辺と v 側に降りるために使う辺を消費します。この辺が lca にとって x 番目, y 番目の辺であった場合,
dp[lca][s|(1<
ということで工夫をする必要があるわけですが, この木 dp は明らかに葉のほうから先にやっていきます。「末端が u であるようなパス」というのは lca -> u というように書けるわけですが, この lca はこれから先どんどん上に伸びていくだけなので, 「今調べている段階で u を終着点とするようなパスでどれだけのパレードを開けているか」というようなものを考えれば良いことになります。下のコードでこれをやっているのは S[v] というやつです。今までのパスの上に一つ頂点がつくことによってパレードの回数が更新される, という感じです。
あと問題なのは 各頂点に対して, その頂点を lca とするものは最高で O(n) 個考えられ, bitDP やってるときにいちいちやっていると O(n^2 2^10) かかって死ぬ, という問題があります。しかしあらかじめ M[x][y] = (頂点 lca で x 本目, y 本目の辺を使う場合に最大で開けるパレードの数) を前計算しておくとこれは大丈夫になります。
int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; while (T--) { int N; cin >> N; vector<vi> G(N); for (int i = 0; i < N-1; i++) { int a, b; cin >> a >> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } // 木についていろいろメモ // 頂点を調べる順番 vector<int> T(N); // 子 vector<vi> chs(N); // 親 vector<int> par(N); // 深さ vector<int> d(N); { d[0] = 1; par[0] = -1; int k = 0; queue<int> que; que.push(0); while (!que.empty()) { int now = que.front(); que.pop(); T[k++] = now; for (int ch : G[now]) { if (!d[ch]) { par[ch] = now; chs[now].push_back(ch); d[ch] = d[now] + 1; que.push(ch); } } } } // anc[v][u] = v, u の LCA vector<vi> anc(N, vi(N)); for (int i = 0; i < N; i++) { int v = T[i]; for (int j = 0; j < N; j++) { int u = T[j]; if (v == u) { anc[v][u] = v; } else if (d[v] > d[u]) { anc[v][u] = anc[par[v]][u]; } else if (d[v] < d[u]) { anc[v][u] = anc[v][par[u]]; } else if (d[v] > 1) { anc[v][u] = anc[par[v]][u]; } else { anc[v][u] = 0; } } } vector<vi> dir(N, vi(N)); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { int v = T[i], u = T[j]; if (v != u && anc[v][u] == v) { for (int x = 0; x < chs[v].size(); x++) { int w = chs[v][x]; if (anc[w][u] == w) { dir[v][u] = x; break; } } } } vector<vector<pii> > V(N); int M; cin >> M; for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; int lca = anc[a][b]; V[lca].emplace_back(a, b); } // dp vector<vi> dp(N, vi(1<<10)); vi S(N); for (int t = N-1; t >= 0; t--) { int v = T[t]; vi M1(10); vector<vi> M(10, vi(10)); for (pii des : V[v]) { int a = des.first, b = des.second; if (a == v) { int x = dir[v][b]; M1[x] = max(M1[x], S[b]+1); } else if (b == v) { int x = dir[v][a]; M1[x] = max(M1[x], S[a]+1); } else { int x = dir[v][a], y = dir[v][b]; M[x][y] = max(M[x][y], S[a] + S[b] + 1); } } int G = 0; for (int ch : chs[v]) { G += dp[ch][(1<<chs[ch].size())-1]; } dp[v][0] = G; int sz = chs[v].size(); for (int s = 0; s < 1<<sz; s++) { for (int x = 0; x < sz; x++) { if ((s>>x)&1) continue; dp[v][s|(1<<x)] = max(dp[v][s|(1<<x)], dp[v][s]); int ch = chs[v][x]; dp[v][s|(1<<x)] = max(dp[v][s|(1<<x)], dp[v][s] + M1[x] - dp[ch][(1<<chs[ch].size())-1]); for (int y = 0; y < sz; y++) if (x != y && ((s>>y)&1) == 0) { int ch2 = chs[v][y]; dp[v][s|(1<<x)|(1<<y)] = max(dp[v][s|(1<<x)|(1<<y)], dp[v][s] + M[x][y] - dp[ch][(1<<chs[ch].size())-1] - dp[ch2][(1<<chs[ch2].size())-1]); } } } int All = (1<<sz)-1; for (int des = 0; des < N; des++) { if (des != v && anc[v][des] == v) { int x = dir[v][des]; int ch = chs[v][x]; S[des] += dp[v][All^(1<<x)] - dp[ch][(1<<chs[ch].size())-1]; } } S[v] = dp[v][(1<<sz)-1]; } cout << dp[0][(1<<chs[0].size())-1] << endl; } return 0; }
院試(東京大学大学院情報理工工学研究科 システム情報学 2016)
院試の受験記です。なんかの参考になれば。
準備編
試験は
- 英語(TOEFL ITP)
- 数学
- 専門
- 面接
があります。日程的に英語 -> (しばらく間が空く) -> 数学 -> 専門 -> 面接 でした(数学と専門は同じ日にやってほしい感)。
噂によると筆記試験(面接以外)でほぼ結果は決まっていて, その 3 科目の配点は 1:1:2 とからしいです。1:2:2 という噂もあります(ホントかは知りません)。
自分のやったお勉強について書きたいと思います。ここからめっちゃ Amazon ラッシュ。
ただ内部生の立場で書いているので外部にはあまり参考にならないかもしれません。
英語
まず TOEFL iBT を事前に受けるか 決められた日程に TOEFL ITP を受けるかを選択できますが, iBT は受験料がクッソ高い(たしか 2 万円とか)し難しいので, ITP のほうが良いと思います。
とりあえず問題内容を知っているのと知らないのでは 50 点くらい違いがあると思うので, それは予習しておきましょう。
- 作者: 島崎美登里,ポール・ワーデン,ロバート・ヒルキ
- 出版社/メーカー: 語研
- 発売日: 2010/03/16
- メディア: 単行本（ソフトカバー）
- 購入: 1人 クリック: 3回
- この商品を含むブログを見る
本番のリスニングはこれの 114514 倍速かったのでそこは別に対策した方が良いかもしれません。僕は全く聞き取れませんでした。
後文法は対策が非常に簡単で, 3 日くらい詰め込めば 8 割は余裕で取れるようになるのでそのために 1 冊買いました。
![全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])](https://images-fe.ssl-images-amazon.com/images/I/51bQaSjxNGL._SL160_.jpg "全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])")
全問正解するTOEFL ITP TEST文法問題対策 ([テキスト])
- 作者: 林功
- 出版社/メーカー: 語研
- 発売日: 2012/05/29
- メディア: 単行本
- 購入: 9人 クリック: 13回
- この商品を含むブログ (1件) を見る
数学
線形代数と解析と確率が出るそうです。
数学に関しては公式ページに過去問があるのでそれをやっていれば良い点取れそうです。
線形代数は何も言わなくてもできそう。
解析は内部生なら数力演習のノート見直せば良さそうです(これで完璧に対策出来るとは言っていない)。
確率に関しては確率分布っぽい話と大学入試か？みたいのが混ざっています。内部生なら確率数理工学のノートを見返せば確率分布っぽいのが出たときの対策ができます。
専門
信号処理, 回路, 制御, コンピュータ, 力学 から 1 問ずつでて, その中から 3 問を解答します。これも公式ページに過去問があるのでそれで練習できます。ただ 2013 くらいからフォントがひどい(読めない)のがあるので文句言った方が良いと思います(僕は内部生なのでちゃんとした問題文を共有できたので問題なかったですが)。
信号処理は毎回狭く, 深く問うてくるイメージなので過去問解いても意味なさそうだし, 普通に難しいので僕は選択する気 0 でした。大学では信号処理論第一, 第二というのがあって, 第一の範囲はおおよそやる夫で勉強することができます。
www.ic.is.tohoku.ac.jp
今年の範囲は第二っぽかったです。第二の内容についてはよく知りません。
回路は毎年オペアンプが出ています。今年も毛色が若干変わったけど出ました。オペアンプを使った回路, 発振回路あたり勉強すれば良いのではないでしょうか。
制御は信号処理と違って毎年だいたい安定した問題が出ています。最近は古典制御の中にこっそり現代制御を仕込むみたいな形式が多かったですが, 今年は堂々と現代制御を出していました。下の 2 冊勉強すれば十分な気がします。
- 作者: 森泰親
- 出版社/メーカー: 森北出版
- 発売日: 2014/10/04
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
- 作者: 森泰親
- 出版社/メーカー: 森北出版
- 発売日: 2014/10/04
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (1件) を見る
コンピュータは…よくわからないので過去問だけやってました。今年はシミュレータでやれ💢💢というようなアセンブリを読まされる問題(再帰関数っぽかった)が出てよくわかりませんでしたが普段は結構簡単だと思います。暇だったらコンピュータの構成と設計でも読んでればよいのではないでしょうか。
- 作者: ジョン・L.ヘネシー,デイビッド・A.パターソン,成田光彰
- 出版社/メーカー: 日経BP社
- 発売日: 2014/12/06
- メディア: 単行本
- この商品を含むブログ (1件) を見る
力学はクッソ簡単な時があるのでそうだったら解こう, という感じで選択するつもりでした。1 年生の時に使ってた演習書が出てきたのでそれを使って一部勉強しました。
- 作者: 今井功,高見穎郎,高木隆司,吉沢徴,下村裕
- 出版社/メーカー: サイエンス社
- 発売日: 2006/09
- メディア: 単行本
- 購入: 1人 クリック: 21回
- この商品を含むブログ (3件) を見る
当日編
英語
リスニングで MP を使い果たす懸念をしていましたが全く聞き取れず MP を消費しなかったので他は計画通り解けました。
多分 リスニング 4 割, 文法 9 割, 長文 7 割くらいだと思います。
数学
「簡単すぎて差がつかない」と言っている人とそれを見て「ハーキレソー」と言ってる人がいました。
満点の自信は多少アリ。
専門
全然できなかったんですが周りも阿鼻叫喚だったので今年はそんな感じだったんだろうという感じでした。
5 割くらい？
追記
点数開示しました。300 円かかるのであんまりやりたくなかったんですが, 結局数学満点で自慢できたので良かったです(小並感)。
JAG 夏合宿に参加しました
楽しかったです。
前日
- 家で高速回転したり奇声を発したりしながら楽しみにしてました。
1 日目
- と言ってもシャイなのでビクビクしながら会場入りしました。
- 自己紹介でクソなぞなぞに言及したところ結構知られてるイメージでした。うれしい。
- ゆらふなさんと初めて会いました。これもうれしい。
- 懇親会。いろいろな人と話せて楽しかった。寿司はほとんど食べれなかった。egg fire。
2 日目
- 朝ごはんのブルーベリーゼリーが異様に濃い紫色でビビった(名物らしい)。
- コンテストは btk さん, たわしさんと組んだ。
- チーム全体で解いたのは C, D, H, I。
- C は btk さんが謎 TLE(入力がクソだった)を連発していて, 代わりに書いてみたら通った。
- D は問題読んで行けると思ったけど x/y の x, y が巨大になると勘違いした(実際には最初の歯車との比のみで決まるのでそんなことはない)のでたわしさんに実装を投げた。
- H, I はいつの間にか AC してた。
- 最後に F を通そうと思ったけど for 文のミスで死んだ。for 文は 1 行 に 1 個書くようにすれば防げるバグだったのですみませんという感じ。
- 解説聞いて L はなるほどという感じだった。
- 後で A は通したいぞい
3 日目
4 日目
- snuke さんのクソなぞなぞ日記が面白かった。そのあと悔しくて何個か駅を見て考えたけどあんまりおもしろいのは思いつかなかった。
- コンテストは btk さん, yurahuna さんと組んだ。in 六本木ヒルズ
- ACDFHJL を解きました。
- C は自明っぽい？(見てない) D は二分探索が嘘であることに気付いて O(N log^2 N) すれば OK
- L は知らんけど通してた
- A は後ろから見てけば良いんだけど O(N^3) しか思いつかなかったから yurahuna さんに投げたらいけそうな雰囲気にしてもらえたので投げた(そのあと大変そうだったけどなんとか通してた)
- F は各頂点で最短経路木を作ってほげる
- H は読めれば簡単
- J は dp[A] = (a の配列で合計を A にしたときの, b の配列側の最小値, およびそのとき選んだ集合) みたいのを更新していけば良い(btk さんと相談して出来た)
- I はほとんど 1/2 の確率で勝つとすると絶対に勝てる方法を btk さんが思いついたけど普通にアンチケースがあったっぽく死。後から聞いたら UMEKOMI すれば行けそうだった。
- コンテスト終わった後集まった人で築地に行って海鮮丼を食べた。いろいろ話せたし良かった。
— マヨ子@大天使クサハエル (@mayoko_) 2016年9月5日
夏合宿参加の皆さんがアップロードした美味しそうな画像たちを見ながら羽田で余った弁当を食べることに幸せを感じない
— Dで始まるくるくるくるりんが解けない人 (@Darsein) 2016年9月5日
まとめ
- egg fire
- くまみこは良かったぞ
