| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
39 分 2 ペナ → 12位。
なんか、いつも以上に既出典型要素が多かった気がしました。結構易しめだったのではないでしょうか？
多重辺…。
問題E – Traveling Salesman among Aerial Cities
ほとんど同じ問題もいくつかある、完全に典型問題でした。
最後に訪れた町で場合分けして最小値を求めようとすると、集合 $S \subset \{0,1,\ldots,N-1\}$ および町 $n$ に対して
$$\dp[S,n] : = （集合 S 内の町をすべて訪れて、最後に町 n に居るときの総距離の最小値）$$
とおくことが思いつくでしょう。集合 $S$ を、$\{0\}$ から始めて適当なトポロジカル順序で $\dp$ 更新していけばよいです。
$$\dp[S\cup\{n\}, n] \leftarrow \dp[S, m] + \mathrm{dist}(n,m)$$
あるいは
$$\dp[S, n] \leftarrow \dp[S\setminus\{n\}, m] + \mathrm{dist}(n,m)$$
といった要領で更新していけばよいです。集合 $S$ をビット表記により $0, 1, \ldots, 2^N-1$ までの自然数にエンコードしてしまうと、$S = 0, 1, 2, \ldots$ 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。この実装方法から bit dp とも呼ばれることの多い手法です。
問題F – Unbranched
問題文をよく読む！！
ああはい、自己ループを持たなくて、いつものやつね…と思っていたら。多重辺がありました。サンプル 1 だけ確認したあと実装を進めてしまいましたが、サンプル 2 も確かめる余裕を持っておけばよかったか…。
実装がすべて終わったあと、サンプル 2 が合わず、サンプル 2 が手計算で合うまでにかなり時間をかけて読み直す羽目に。まぁ、私が悪かったです…。（サンプル 2 がなければ問題文よりも実装ロジックを疑いにかかっていた可能性もあり、時間を大きく溶かすコースでした、危ない）
最大値が $L$ であるような数え上げが問われていますが、
- 最大値が $L$ 以下であるような数え上げを求める関数 $f(L)$ を実装する
- $f(L) – f(L-1)$ が答
とします。これは、$\max\{a_1,a_2,\ldots\} = x$ という条件よりも $\max\{a_1,a_2,\ldots,\} \leq x$ の方が扱いやすい：
$$\max\{a_1,a_2,\ldots\}\leq x \iff \forall i, a_i \leq x$$
ことから来る言い換えです。この性質から最大値（あるいは多くの順位統計量）を求めるときに二分探索することになったりしがちですよね。また、
でも $\max$ のこの性質が用いられていたことは記憶に新しいと思います。
- 頂点数が $L$ 以下のパスまたはサイクルのみを成分とする、$N$ 頂点 $M$ 辺のラベル付きグラフを数え上げよ
という問題になりました。この値を、$\dp[N,M]$ と置くことにして、これをラベル $N$ の頂点を含む連結成分によって場合分けして数えようとします。すると、$k$ 頂点からなるパスの個数 $p$、サイクルの個数 $c$ とするとき
$$dp[N,M] += p\times \dp[N-k,M-k+1], dp[N,M] += c\times \dp[N-k,M-k]$$
といった要領で計算できることが分かります。$c$ を求めるときには、$n = 2$ の場合分けに注意（多重辺がどちらの場合であっても）。
全体集合を一定の構造を持つなにかに分割する場合に、$1$ 点を固定して、それを含む成分で場合分けするという考え方は、割とよく出てきます。最近ですと
でも現れていましたね。
