AOJ 2785 Escape from the Hell
解法
とりあえず C[i] については無視して考えてみる。
最終日に使うドリンクを決めたとする。このドリンクを k とする。
すると、L - a[k] をできるだけ早く達成したいということになり、
当然 a[i] - b[i] が大きい方から貪欲に飲むのが最適である。
以降 a[i] - b[i] の降順でソートされているとする。
L - a[i] を達成する最小日数を求めるが、これは以下の2通りがある。
- 場合1：ドリンク k より前のドリンクを飲んだ時点で達成
- 場合2：ドリンク k 以降のドリンクを飲んだ時点で達成
場合1は簡単で、a[i] - b[i] の累積和（の max）が L - a[i] 以上となる位置を
二分探索で求めれば良い。
場合2のときは、0 ～ k - 1 までの a[i] - b[i] の総和を S として、
(a[i + 1] - b[i + 1]) + ... + (a[j] - b[j]) が L - a[i] - S 以上となる最小の j を探索する。
このために、区間 [l, r) に対し、[l, i) (l < i <= r) なる全ての i について考えたときの (a[l] - b[l]) + ... + (a[i - 1] - b[i - 1]) の最大値を求める必要があり、これは segment tree で実現できる。
こうして得られた最小日数の id を x としよう。
最後に c[i] について考える。これは a[i] - b[i] - c[i] の累積和について、先と同じように2通りに分けられる。
場合1は簡単であり、a[i] - b[i] - c[i] の x までの累積和（の min）が 0 より大きければ OK である。
場合2のときは、a[i] - b[i] - c[i] の k まで (exclusive k) の累積和が 0 より大きい、かつ (k + 1 から x までの "a[i] - b[i] - c[i - 1] の" 累積和の min) + (0 から k までの累積和）が 0 より大きければ OK である。
k を使えないので、インデックスが1つずれていることに注意する。
これも segment tree（max のときと同じ要領）で処理することができる。
あとはすべての k についてこれをやれば良い。
segment tree の上で二分探索をしたので O(n (logn)^2) で解ける。
ちゃんとやれば log はもう一つ落とせるが、まあ間に合うのでよし。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; constexpr ll inf = 1e18; template<typename Monoid> class segment_tree { using T = typename Monoid::type; public: segment_tree(std::vector<T> const& init) : sz(init.size()), n(expand(init.size())) { dat.assign(n*2, Monoid::id()); std::copy(begin(init), end(init), begin(dat) + n); for(int i = n - 1; i >= 0; --i) { dat[i] = Monoid::op(dat[i * 2], dat[i * 2 + 1]); } } segment_tree(int const n_, T const& init = Monoid::id()) : segment_tree(std::vector<T>(n_, init)) {} void update(int p, T val) { assert(0 <= p && p < sz); dat[p += n] = val; while(p /= 2) { dat[p] = Monoid::op(dat[p * 2], dat[p * 2 + 1]); } } // [l, r) T query(int l, int r) const { assert(0 <= l && l <= r && r <= sz); l += n, r += n; T res1 = Monoid::id(), res2 = Monoid::id(); while(l != r) { if(l & 1) res1 = Monoid::op(res1, dat[l++]); if(r & 1) res2 = Monoid::op(dat[--r], res2); l /= 2, r /= 2; } return Monoid::op(res1, res2); } private: int expand(int n_) const { assert(n_ >= 1); return n_ == 1 ? n_ : expand((n_ + 1) / 2) * 2; } private: const int sz, n; std::vector<T> dat; }; struct RSMQ { struct type { ll sum, mini, maxi; type() : sum(0), mini(inf), maxi(-inf) {} type(ll s, ll mi, ll ma) : sum(s), mini(mi), maxi(ma) {} }; static type id() { return type{0, inf, -inf}; } static type op(type const& l, type const& r) { if(l.mini == inf) return r; if(r.mini == inf) return l; return type(l.sum + r.sum, min(l.mini, l.sum + r.mini), max(l.maxi, l.sum + r.maxi)); } }; int main() { ll n, l; cin >> n >> l; vector<pll> drink(n); vector<ll> c(n); for(int i = 0; i < n; ++i) { cin >> drink[i].first >> drink[i].second; } for(int i = 0; i < n; ++i) { cin >> c[i]; } sort(begin(drink), end(drink), [] (const pll& p1, const pll& p2) { return p1.first - p1.second > p2.first - p2.second; }); // a[i] - b[i], a[i] - b[i] - c[i], a[i] - b[i] - c[i - 1] vector<RSMQ::type> dat1(n), dat2(n), dat3(n); for(int i = 0; i < n; ++i) { const ll a = drink[i].first, b = drink[i].second; dat1[i] = RSMQ::type{a - b, a - b, a - b}; dat2[i] = RSMQ::type{a - b - c[i], a - b - c[i], a - b - c[i]}; if(i != 0) { dat3[i] = RSMQ::type{a - b - c[i - 1], a - b - c[i - 1], a - b - c[i - 1]}; } } segment_tree<RSMQ> seg1(dat1), seg2(dat2), seg3(dat3); int ans = n + 1; for(int i = 0; i < n; ++i) { // last use const ll r = l - drink[i].first; if(r <= 0) { ans = 1; break; } if(seg1.query(0, i).maxi < r) { if(seg2.query(0, i).mini <= 0) continue; int lb = i + 1, ub = n; const ll s = seg1.query(0, i).sum; while(ub - lb > 1) { const int mid = (ub + lb) >> 1; (seg1.query(i + 1, mid).maxi < r - s ? lb : ub) = mid; } if(seg1.query(i + 1, ub).maxi < r - s) continue; if(seg2.query(0, i).sum + seg3.query(i + 1, ub).mini <= 0) continue; ans = min(ans, ub); } else { int lb = 0, ub = i; while(ub - lb > 1) { const int mid = (lb + ub) >> 1; (seg1.query(0, mid).maxi < r ? lb : ub) = mid; } if(seg2.query(0, ub).mini <= 0) continue; ans = min(ans, ub + 1); } } cout << (ans == n + 1 ? -1 : ans) << endl; }
感想
実装に失敗している感じもするが、なぜか全くバグらなかった。
ところで、こういうセグ木ははじめて書いた気がする。
DDCC 2018 D - DISCO!
解法
区間同士でうまくマージできるような形であればセグ木に乗せることができるので、とりあえずその方針で考えてみる。
2つの区間 A, B があって、それらをマージしたときに "DISCO" がいくつ現れるかを考えてみると
- A から "", B から "DISCO"
- A から "D", B から "ISCO"
- A から "DI", B から "SCO"
- A から "DIS, B から "CO"
- A から "DISC", B から "O"
- A から "DISCO", B から ""
の5通りある。
よって、それぞれの区間に、対応する文字列が何通りあるか持てば良いことがわかる。
この議論は、当然 "ISCO" や "SCO" などを数えるときにも必要であるが、
冷静に考えると、文字列は "DISCO" の連続部分文字列であり、先程列挙したように、文字列の構成の仕方に特徴がある。
これに気がつけば
A[i][j] := "DISCO" の [i, j) が完成している場合の数
と定義した行列積が、区間のマージに対応することがわかる。
たとえば、s[i] が 'I' であるなら、A[1][2] = 1 とすればよい（ただし対角成分は常に1）。
以上で、計算量は O(6^3 * Q * logN) となる。
TL が 13sec なので普通に書けば通るだろう。
ソースコード
#include <bits/stdc++.h> using namespace std; using u32 = uint32_t; using matrix = array<array<u32, 6>, 6>; matrix make_zmat() { matrix res; for(int i = 0; i < 6; ++i) { for(int j = 0; j < 6; ++j) { res[i][j] = 0; } } return res; } matrix make_id_mat() { auto res = make_zmat(); for(int i = 0; i < 6; ++i) res[i][i] = 1; return res; } matrix operator*(matrix const& a, matrix const& b) { auto res = make_zmat(); for(int k = 0; k < 6; ++k) { for(int i = 0; i < 6; ++i) { for(int j = 0; j < 6; ++j) { res[i][j] += a[i][k] * b[k][j]; } } } return res; } template<typename Monoid> class segment_tree { using T = typename Monoid::type; public: segment_tree(std::vector<T> const& init) : sz(init.size()), n(expand(init.size())) { dat.assign(n*2, Monoid::id()); std::copy(begin(init), end(init), begin(dat) + n); for(int i = n - 1; i >= 0; --i) { dat[i] = Monoid::op(dat[i * 2], dat[i * 2 + 1]); } } segment_tree(int const n_, T const& init = Monoid::id()) : segment_tree(std::vector<T>(n_, init)) {} void update(int p, T val) { assert(0 <= p && p < sz); dat[p += n] = val; while(p /= 2) { dat[p] = Monoid::op(dat[p * 2], dat[p * 2 + 1]); } } // [l, r) T query(int l, int r) const { assert(0 <= l && l <= r && r <= sz); l += n, r += n; T res1 = Monoid::id(), res2 = Monoid::id(); while(l != r) { if(l & 1) res1 = Monoid::op(res1, dat[l++]); if(r & 1) res2 = Monoid::op(dat[--r], res2); l /= 2, r /= 2; } return Monoid::op(res1, res2); } private: int expand(int n_) const { assert(n_ >= 1); return n_ == 1 ? n_ : expand((n_ + 1) / 2) * 2; } private: const int sz, n; std::vector<T> dat; }; struct DISCO { using type = matrix; static type id() { return make_id_mat(); } static type op(type const& l, type const& r) { return l * r; } }; int main() { string s; cin >> s; const int n = s.size(); segment_tree<DISCO> seg(n); const string disco = "DISCO"; for(int i = 0; i < n; ++i) { auto a = make_id_mat(); const int idx = find(begin(disco), end(disco), s[i]) - begin(disco); a[idx][idx + 1] = 1; seg.update(i, a); } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; l--; cout << seg.query(l, r)[0][5] << endl; } }
感想
なぜか本番で解けなかったやつ。大反省。
競プロでも使える C++ の便利機能
はじめに
C++14, 17, 20 と規格が改定されていくにつれ、色々便利な機能が追加されています。
そのうちのいくつかは競プロであっても有用なのですが、特に最近始めた人のコードを読んでいるとほとんど使われておらずもったいないと感じることが多いです。
そこで今回は今すぐにでも使えそうな*1機能を紹介したいと思います。
ただし、それぞれの機能について深く掘り下げはしません。
一応、規格が策定された順で書いてあります。
ジャッジによっては古いコンパイラしか使えなかったりするためです。
例えば AtCoder はまだ C++14 しか使えませんね。すぐ上がりそうですが。
Codeforces は C++17 が使えます。頻繁にアップデートしている印象があります。
ライブラリを自作で整備する人に有用な機能もたくさんあるのですが、少数派だと思ったのでこの記事には書きません。あしからず。
C++11 ～
range-based for
とりわけ vector などのコンテナをイテレートするのに便利です。
要素の中身だけではなく、インデックスも欲しい場合は通常の for によるループを書くことになるでしょう。
vector<int> v = {1, 2, 3}; // index もほしい場合 for(int i = 0; i < (int)v.size(); ++i) { cout << "i: " << i << " => " << v[i] << endl; } // range-based for for(auto const x : v) { cout << x << endl; }
ラムダ式
その場でちょっとした関数を生成できる機能です。競プロにおける用途は、例えば
- 外に関数を切り分ける程でもないが、分けておくと見やすいとき（二分探索の check 関数など）、
- キャプチャによりローカル変数を参照できるような関数が欲しい時（サボりたいとき便利
- 一部ライブラリの一般化のため
などがあるでしょう。
// 二分探索 auto check = [&] (int x) { ... }; int lb = 0, ub = inf; while(ub - lb > 1) { const int mid = (ub - lb) >> 1; (check(mid) ? lb : ub) = mid; } // 再帰関数（サボり） // グローバル変数は嫌だがローカル変数をたくさん使いたいときに楽 vector<vector<int>> g; // graph function<void(int, int)> dfs = [&] (int v, int p) { // [&] で参照キャプチャ for(auto to : g[v]) { if(to == p) continue; dfs(to, v); } }; dfs(0, -1);
再帰の例は function を使っているので定数倍遅いことに注意が必要です。
オーバーヘッドが気になる人は
C++のラムダで再帰する - koturnの日記
こういう記事を参考にすると良いでしょう。
自分はその場でちゃちゃっと書いちゃいたい人なので、function を使う場面が多いです。
emplace_* メソッド
vector などのコンテナに primitive 型以外を持たせる場合に使えたりします。
よくあるケースは pair だと思います。
queue<pair<int, int>> que; vector<pair<int, int>> v; // 二行は同じ意味と考えて良い（本当は違います） que.push(make_pair(0, 0)); que.emplace(0, 0); v.push_back(make_pair(0, 0)); v.emplace_back(0, 0);
using alias
typedef の上位互換です。template と一緒に使えるので便利です。
using ll = long long; // typedef long long ll; と同じ // template にも使える template <typename T> using matrix = vector<vector<T>>;
std::next, std::prev
イテレータを1つ進める、戻す機能。
std::set と一緒に使うことが多い気がします。advance で似たことはできますけどね。
set<int> s = {1, 2, 3}; auto it = begin(s); cout << *it << endl; // 1 it = std::next(it); cout << *it << endl; // 2 it = std::prev(it); cout << *it << endl; // 1
乱数ライブラリ random
メルセンヌ・ツイスタといった疑似乱数生成器が使えます。
uniform_int_distribution などと合わせて使えば、指定された範囲での一様乱数を得られたりします。
いっぱいあるんでここで調べてください（書くのがめんどくさくなりました）
random - cpprefjp C++日本語リファレンス
std::min/max + initializer_list
min, max に3つ以上の引数を入れたい場面があるかもしれませんが、initializer_list と合わせて使えば楽にかけます。
int a = 1, b = 2, c = -1; cout << max(a, max(b, c)) << endl; // つらい cout << max({a, b, c}) << endl; // よさ
C++14 ～
C++14 は C++11 に比べて大きな変化はないですが、細かいところが修正されています。
2進数リテラル
int b1 = 0b11; // => 3 int b2 = 0b0110; // => 6
桁区切り
1e9 など、0が連続して見にくいときに便利かも。
int inf = 1'000'000'000; // 1e9
generic lambda
lambda 式の引数に auto が使えます。
// 書くの面倒 auto f1 = [] (std::vector<int> v) { ... }; // 楽 auto f2 = [] (auto v) { ... };
本当は型省略のためだけにあるわけじゃない（実質 template と同じなので…）のですが、まあいいでしょう。
variable templates
変数定義時に template を使えます。inf とか pi とかの定数に対して使うと便利かも。
template <typename T> constexpr T INF = numeric_limits<T>::max() / 2; cout << INF<int> << " " << INF<long long> << endl;
C++17 ～
構造化束縛 (structured bindings)
pair、tuple、あるいは構造体などから各要素を取り出す機能。
auto p = make_pair(0, 1); auto t = make_tuple(1, 2, 3); auto [fst, snd] = p; // fst == 0, snd == 1 auto [fst, snd, trd] = t; // fst == 1, ...
map を range-based for で回してうんたら～とか、queue に頂点と距離持たせてうんたら～みたいなときに便利でしょうね。
std::gcd, lcm
なんか追加されてました。O(logn) だと思います。
引数に int を渡すと int のまま計算されるので、long long が欲しい場合は注意が必要です（そういう意味では自作の lcm のほうがいいかもね）。
int n = numeric_limits<int>::max(); int m = n - 1; cout << lcm(n, m) << endl; // overflow cout << lcm((ll)n, m) << endl; // ok
C++20 ～
書くの飽きた（は？）。まあ 20 はまだ先だし、そのうち書きますね。
気が向いたときにちょっとずつ追記していきます。
Range
Range という概念があるんですけど、例えば以下のようなコードが書けます。
// for(int i = 0; i < n; ++i); と同等 for(int i : iota(0, n)); // for(int i = n - 1; i >= 0; --i); と同等 for(int i : iota(0, n) | reverse);
これで REP マクロともおさらば…と言いたいところですが、タイプ数が多いのでおさらばしないひとも多そうですね。
でも range を使わない for ループよりははるかに良くなってると思います。
range view には iota, `reverse` の他にも filter, take, transform などが入る予定です。
終わりに
競プロであってもきれいなコードのほうがいいに決まってるので、使える機能はジャカジャカ使っていきましょう！
なお、この記事はかなり勢いで書いたため、推敲や誤字チェックなどは一切していません。
間違いを見つけたり、なにか気がついたことがあれば教えてください。
*1:というか、僕がよく使うやつ
自分が書く今後の競プロ問題解説記事について
これまでは、難しいなと思った問題や AOJ で解説がない問題の記事をはてなに直接書いてきた。
しかし最近は解いたときのコードを git で管理するようになったので、今後は github の解答コードへのリンクを貼るようにしようと思う。
解説や考察メモはコードの上にコメントとして書くことにする。
メモがない場合は、僕が自明だと思ったか、あるいは書くのを忘れているだけなので、そこらへんは許してほしい。
例えばこんな感じにする。
https://github.com/Suikaba/procon-solved/blob/master/Codeforces/Round200-249/Round210/Div1-C.cpp
Lindström–Gessel–Viennot lemma
概要
格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。（$a_i$ をどの $b_j$ と対応付けるか、まで含めて。）
後にこの定理を用いて解ける問題を挙げる。
主張
$G$ を局所的に有限なDAGとする。
始点集合を $A = \{a_1, \ldots, a_n\}$ とし、終点集合を $B = \{b_1, \ldots, b_n\}$ とする。
辺には重みがついており、パス $P$ に対して $w(P)$ で $P$ 上の辺の重みの積と定義する。
また、$e(a, b) := \sum_{P : a \rightarrow b}w(P)$ と定義する。
もしすべての辺の重みが 1 であるならば、$e(a, b)$ は $a$ から $b$ へ行く方法の総数に対応する。
ここで、
$M = \left(
\begin{array}{cccc}
e(a_1, b_1) & e(a_1, b_2) & \cdots & e(a_1, b_n) \\
e(a_2, b_1) & e(a_2, b_2) & \cdots & e(a_2, b_n) \\
\vdots & \vdots & & \vdots \\
e(a_n, b_1) & e(a_n, b_2) & \cdots & e(a_n, b_n)
\end{array}
\right)$
とおく。
$n$ 組の $A$ から $B$ へのパス $P = (P_1, P_2, \ldots, P_n)$ が交差しないとは、以下の性質を満たすことである。
- $\{1, \ldots, n\}$ のある順列 $\pi$ があって、パス $P_i$ は $a_i$ から $b_{\pi(i)}$ へのパスと表される
- $i \neq j$ ならば、$P_i$ と $P_j$ は端点も含め共通な頂点を持たない
すると、$det(M)$ は $A$ から $B$ への $n$ 組非交差パス $P = (P_1, \ldots, P_n)$ についての符号付き総和となる。
つまり、 $\det (M) = \sum_{(P_1, \ldots, P_n) : A \rightarrow B} sgn(\pi(P)) \prod_{i=1}^{n}w(P_i)$ である。
とくに、2つの性質を満たす順列 $\pi$ が identity な順列、つまりすべての $i$ について $\pi(i) = i$ となる順列しか無く、かつ辺の重みがすべて 1 の場合、$\det(M)$ は $A$ から $B$ への $n$ 組非交差パスのとり方の総数と等しくなる。
証明
そのうち（ごめんなさい）
問題概要
n * m のグリッドが与えられる。いくつかのマスは障害物があり通れない。
2人が座標 (0, 0) からスタートして (n - 1, m - 1) に到達する移動方法で、同じマスを通らないようなもの（ただし始点と終点はよい）は何通りあるか。
許される移動方法は、今の座標を (x, y) として (x + 1, y) か (x, y + 1) に移動することだけである。
・2 <= n, m <= 3000
解法
さっきの定理で解ける。
今回であれば、始点として $A = \{(0, 1), (1, 0)\}$ を、終点として $B = \{(n - 2, m - 1), (n - 1, m - 2)\}$ を与えて適用できる。
適用できる理由は、順列 $\pi$ としては identity なものしかありえないからである。
具体的には、$(0, 1)$ と $(n - 1, m - 2)$ を対応付ければ、かならずパスが交差してしまうということである。
よって、求める答えは、行列式
$\left|
\begin{array}{cc}
f(a_1, b_1) & f(a_1, b_2) \\
f(a_2, b_1) & f(a_2, b_2)
\end{array}
\right|$
である。ただし、$f(a_i, b_i)$ は $a_i$ から $b_i$ への移動方法の総数を表し、これは簡単な dp で O(nm) で解ける。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int mod = 1e9 + 7; int add(int a, int b) { a += b; if(a >= mod) a -= mod; return a; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<string> v(n); for(int i = 0; i < n; ++i) { cin >> v[i]; } vector<vector<int>> dp(n, vector<int>(m)); auto calc = [&] (int sy, int sx, int gy, int gx) { if(v[sy][sx] == '#') return 0; for(int i = 0; i < n; ++i) { fill(begin(dp[i]), end(dp[i]), 0); } dp[sy][sx] = 1; for(int i = sy; i < n; ++i) { for(int j = sx; j < m; ++j) { if(v[i][j] == '#' || (i == sy && j == sx)) continue; if(i != 0) dp[i][j] = add(dp[i][j], dp[i - 1][j]); if(j != 0) dp[i][j] = add(dp[i][j], dp[i][j - 1]); } } return dp[gy][gx]; }; int ans = (ll)calc(1, 0, n - 1, m - 2) * calc(0, 1, n - 2 , m - 1) % mod; (ans += mod - (ll)calc(1, 0, n - 2, m - 1) * calc(0, 1, n - 1, m - 2) % mod) %= mod; cout << ans << endl; }
参考文献
Lindström–Gessel–Viennot lemma - Wikipedia
主張はほとんどここからのパクリです。
ACM-ICPC 2018 Asia Yokohama Regional 参加記
はじめに
2018年12月8, 9日に横浜で行われた ACM-ICPC 2018 Asia Yokohama Regional の参加記です。
プラクティス～懇親会あたりまでの話を大雑把にまとめようと思います。
チームについて
自分はチーム Zerokan_Sunshine として kazuma, nakano と一緒に出ました。
基本的に担当は
- suibaka (自分) : 実装担当、自明とか典型とか幾何とか。あと問題読解。
- kazuma : 実装担当2。データ構造が得意（ICPCではあまり出ないので悲しい）
- nakano : 考察・問題読解担当、コードは書かない（早く US 配列に慣れろ）
となっています。
プラクティス
プラクティスは基本的に1問ACしてあとはジャッジで遊ぶだけなんですが、今年は問題が普通に過去問だったので真面目にやりました。
A 問題
kazuma が Link-cut tree で解けるとか言い出したので後回しにした（流石にネタ）
n 要素の数列が与えられるから合計値出力するだけ。
B 問題
覚えてないが全探索、kazuma に書かせた
C 問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320
知っているので油断していたらコーナーケースを忘れて 1WA 。
知っていると思考が無になる。
D 問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1605&lang=jp
これも解いたことがあるが今思えば条件判定部分を間違えていた。
間に合わなかった。
プラクティス後
雑にチーム紹介をして終わり。今年はご飯の提供がなかった。
まあ近くに中華街があるのでそっちで食べられた。
ただ寝不足が続いていてコンディションが悪い人が多く、ちょっと食べてさっさと寝た…んだったら良かったんだけどなー。
ABC
なんかABCがあった。後述の Snackdown まで仮眠をとるつもりが何故か眠れず、出ることにした。
さっさと終わらせて寝るつもりだったけど、冷えたので布団で暴れたり呪詛の言葉を吐いたりした。
Snackdown 2019
運の悪いことに今年は Snackdown の最終予選が 23:00 ～ 04:00 とかいうヤバヤバの時間で、しかも完全に予定がかぶっていた。
普通なら出ないって？僕らは頭が悪いので出ました。
詳細は脱線なので書きませんが、難しすぎて絶望した。
10問あって3完、ラスト1問は実装間に合わないとかだった。
多分Tシャツはゲットなのでセーフということにした。
就寝（04:30）
本番
8:30 ぐらいに起きて飯をくい、さっさと会場へ。
以下内容。
A 問題
問題文の解釈に少し手間取ったけどまあやるだけなので書いて終わり (0:12 AC)
C 問題
nakano が読んでいたので教えてもらって、Bのあとに書く予定だった。
B が自明 O(N^2logN) 解は多分 TLE するからめんどい、とのことだったので先に C を書くことにした (0:30 AC)
B 問題
kazuma が O(N^2) で通す。(0:41 AC)
疑問なんですが、5sec で N <= 5000 だったら O(N^2logN) は通ると思いますか？
僕はかなり微妙だと思います（強いて今回のセットで不満があるならここぐらいかな…）
虚無
虚無です。いつもの時間です。虚無虚無プリン。
G 問題
nakano が概要を教えてくれた、明らかに BIT だし kazuma に投げた。
まあいけるね、となったけど方針が想定と違っていて、駄目なケースがあった。
幸いサンプルに存在したので気づけてセーフ。nakano が想定解に修正して kazuma が通す。(1:40 AC)
E 問題
オイラー路が存在するように与えられたグラフに辺を生やせ、という構築。
第一感は解けそう、という感じ。
自分は D, K をやっていたので kazuma がやることに。
実装頑張って投げたが WA、しかし落ちるケースをすぐ発見（やりますねえ！）して AC (3:18 AC)。
G の次に解いたのが E なの完全に異常、僕のせいですごめんなさい。
K 問題
辞書順最大を誤読しており 1WA。Standings みればわかることなんだよね。
前の値から決めていくいつものやつじゃ～んとなる。
けど、普通にやったら O(N^3) なのでどうしようなあとなっていて、
nakano とあーでもないこーでもない言ってたら生えた。
O(N^2logN) の少し重めの実装になって、とりあえずTLEかどうか投げてから考えようと思ってたら通った (3:59 AC)
D 問題
これ最初の方からずっと考えていて、今それぞれの文字でどのインデックスにいるかの dp やるだけなのは割とすぐ見えていたんですが…
これのややこしいバージョンを解いたことがあって、経路復元パートで直前に使った数字しか記憶しないことに起因して、直前の状態が一意に定まらない、みたいな理解をしてしまい、実装がめんどくさいなーと思って後回しにしてしまった。K問題で虚無っていたというのもあるけど。
この場合、現状態として解となりうる状態の頂点集合を持ちながら、復元していく（最終的には一意的になる）実装になる。
でまあなんとか1発で通ったわけですが (4:41 AC)、これで通ってなかったら戦犯だな。
普通に BFS で0を優先的に使っていく遷移をすれば、直前の状態は一意的に定まっているので本当にやるだけでした。なーにやってんだか。
ここからは本番で解いてない問題
F 問題
nakano に解ける解ける言われて kazuma と2人で全力拒否していた問題。
どう考えてもこのセットで飛びついていいものではない。他にやることあるからね。
H 問題
解説聞いてかなりおもろいな～と思った。
グラフの形が特徴的だから、座標の辞書順に埋めていけば、すでに色が塗られている頂点は高々4個しか無い、というのがうまく効いていてすごい。
色の塗替えのあの発想は彩色問題の証明で見たテクな気がする。
I 問題
未だに完全理解していない。本番で4チームも通してるのすごくない？
懇親会
ご飯おいしかった。ごちそうさまです。
今年はブースもちゃんと回ることにした。
毎年1社はでかいカバンを配っているような気がするので、最初にそこにいくと後が楽でいいと思う。
Indeed ブースでコネクションハントをし、頑張って集めて T シャツゲット。
別のブースで真剣にコーヒー淹れていた人がいたんですが、なんか話しかけられない空気でちょっと怖かった…。
感想
決意表明として、来年も同じチームで来ることを誓おうと思います。
今年は同大学の earlybird が WF に行けそうなので、一緒に応援しましょう！！
あわよくばメダルを取って帰ってきてほしいですね～。
