AtCoder Beginner Contest 204のきろく - Flkanjin’s 競プロ録

A - Rock-paper-scissors (100点)
B - Nuts (200点)
C - Tour (300点)
D - Cooking (400点)
E - Rush Hour 2 (500点)
F - Hanjo 2 (600点): 未提出
結果、感想

A - Rock-paper-scissors (100点)

$3$ 人のじゃんけんであいこになるのは、全員同じ手を出すか、全員違う手を出した時なので、 $x = y$ のときはその手、そうでないときは $3-x-y$ の手を出せばいいです。また、サーバルの出した手に対応する文字を $z$ としたとき、 $x + y + z \equiv 0 \pmod 3$ となることを利用すると $z = (6 - x - y) \bmod 3$ となります。

B - Nuts (200点)

forとifを組み合わせて答えを出すことができますが、各 $i$ について足す数は $\max\{A_i - 10,\,0\}$ であるのでこれを足していく方が多分少し短いです。

C - Tour (300点)

全頂点対について移動が可能かどうかなので、Warshall-Floyd法で...とすると $O(N^3)$ なので間に合いません。
始点を固定した時同じ頂点を2度以上訪れないようにしたDFSやBFSを行うと、どの頂点も辺も高々1回しか通らないので $O(N+M)$ でその始点から訪れることができるかどうか判別できるので、その始点を全て試して足して合わせてやることで $O(N(N+M))$ で判定することができます。

D - Cooking (400点)

コストをlong longにし忘れと辺を双方向につなぎ忘れによって3WA出してしまいました... これがなければ、青色復帰できたのに...

$U = \{1,\,2,\,\dots,\,N\}$ を二つの集合 $A_1,\,A_2$ に空集合を許した分割を行ったときの $\displaystyle\min \max\left\{\sum_{i \in A_1} T_i,\,\sum_{i\in A_2}T_i\right\}$ が答えです。分割の方法は $2^N$ 通り存在するため、全探索では間に合いません。
この問題は部分和問題であるためDPの利用を考えます。

${\mathrm{dp}}_{i,j} = (T_1,\,T_2,\,\dots,\,T_i \text{の部分和を$j$にすることができるかのbool値})$

とすると ${\mathrm{dp}}_{0,0} =\mathrm{true}$ であり、 $1 \leq ileq N$ について

${\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} {\mathrm{dp}}_{i-1,j} & (j < T_i)\\ {\mathrm{dp}}_{i-1,j}\ \mathrm{OR}\ {\mathrm{dp}}_{i-1,j-T_i} & ({j \geq T_i}) \end{array} \right.$

が成り立ち、 $\displaystyle S = \sum_{i=1}^{N}T_i$ とすると $\displaystyle \sum_{i\in A_2}T_i = S - \sum_{i\in A_1}T_i$ であるため、答えは $\displaystyle\min_{{\mathrm{dp}}_{N,j} = \mathrm{true}}\max\{j, \,S-j\}$ が答えとなります。 $j$ の値は $S$ 以下で $S \leq N \displaystyle \max_i T_i \leq 10^5$ であり、計算量 $O(NS)$ で十分間に合いました。

E - Rush Hour 2 (500点)

任意の整数時間待機することができるので、各都市への最速到達時間を考えればいいです。道路 $i$ を通って都市 $A_i$ から時刻 $t$ に出発して都市 $B_i$ に到達する時刻は $t + C_i + \displaystyle \left\lfloor \frac{D_i}{t+1} \right\rfloor$ となります。 $f(t) = t + C + \displaystyle \left\lfloor \frac{D}{t+1} \right\rfloor,$ $g(t) = t + C + \displaystyle\frac{D}{t+1}$ とした時 $g'(t) = 1 - \displaystyle\frac{D}{(t+1)^2}$ であり、 $g$ は $t \leq \sqrt{D} -1$ で単調減少、 $t \geq \sqrt{D} -1$ で単調増加することから、 $t = \sqrt{D}-1$ のときに最小値をとり、 $f(t) = \lfloor g(t) \rfloor$ であることから $f$ も $\sqrt{D}-1$ 附近で最小値をとることが分かります。ちゃんとした解説は公式解説を参照して下さい。
上記から各道を通った時の反対側に着く時刻が最小値となるような出発時刻 $t_i$ が求まります。よって、頂点 $A_i$ に到達可能な最速時刻が $T$ であるとき、 $T \lt t_i$ の時は $t_i$ まで待ってから、 $T \geq t_i$ の時は即座に道 $i$ を用いることでその道を用いて $B_i$ へ行く経路のうち最速で $B_i$ に行くことができるため、このように改造したDĳkstra法で答えを求めることができます。