AtCoder Beginner Contest 226 (ABC226) に参加して， ABCDE5完 922位でした．冷えました．

A - Round decimals

難しかったです．

string s; cin >> s;
cout << (stoi(s.substr(0, s.size() - 4)) * 1000 + stoi(s.substr(s.size() - 3) + 500) / 1000 << endl;

B - Counting Arrays

vector<vector<int>> vec; に読み込んでおいて，sort して unique して erase して size をとりました．

C - Martial artist

技aが技bの前提になっているとき，bからaに辺がある有向グラフを考えて， 技N からたどれる技全部について 時間を加えれば良いです．

D - Teleportation

$T := \{(i, j) \mid 1 \leq i < j \leq N\}$ として， $(a,b), (c,d) \in T$ に対し， 「$(x_b - x_a, y_b - y_a)$ と $(x_d - x_c, y_d - y_c)$ が平行である」 という同値関係を$T$に入れた時，同値類の数の2倍が求める答です．

$T$を $(x_b - x_a, y_b - y_a)$ の偏角でソートして，隣り合う要素が 異なるところの数を数えれば同値類の数がわかります．

しょうもないミスで1WA．

E - Just one

題意を満たす向き付けができるための必要十分条件は，各連結成分について， 辺の数と頂点の数が等しいことです． 必要条件であることはあきらかです． 十分性: 連結成分のグラフは全域木と1本の辺からなります． その辺の両端をA, B として，全域木の根を A と見た時に， 子から親へ向き付け，最後に A → B の向きを付ければ，題意を満たします．

このとき，各連結成分上で，1つだけあるループの向きだけの自由度がありますから， 求める答は，2の連結成分数乗です．

必要十分条件を理解するまでいろいろ迷走して 2WA．

F - Score of Permutations

時間が足りず，コードを書いている途中で時間切れになりました．

順列$P$を決めた時のスコアは，$P$を巡回置換の積で表した時， 各巡回置換の長さの最小公倍数になります．

dp[n][e] := 1, 2, …, n の順列で，スコアが e であるものの数

とします．

1, .., n の順列のうち， n を含む巡回置換の長さが k であるものを数えます． まず，1, 2, …, n - 1 から k - 1 個をえらびます． 選んだものと n からなる k 個の巡回置換の数は $(k - 1)!$ ですから， このようなものは $\binom{n-1}{k-1} (k-1)!$ 個あります． 残り $n - k$ 個の並び替えのスコアが e だとすると，この順列の スコアは LCM(e, k) になりますから，

$\textrm{dp}[n][\textrm{LCM}(e, k)] \;+\!=\; \textrm{dp}[n - k][e] \times \binom{n-1}{k-1} \times (k-1)!$

という遷移が書けます．データはmap で持ちます．

求める答は $\sum_{e} e^K (\textrm{dp}[N][e])$ で， $K$乗を $O(\log K)$ で実行すれば間に合います．