AtCoder Beginner Contest 204 感想

#総合結果
* [Score] 1500 pts
* [Time] 68:03 + <font color="red"> 05:00 $\times$ 3 </font> = 83:03
* [Ranking] 521 st [Rated内: 334 th]
* [Performance] <font color=#0000FF> 1805　</font>
* [Rating] <font color=#0000FF> 1915 </font> → <font color=#0000FF> 1904 </font> (-11)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:26|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc204/submissions/23211081)||
|<font color=#808080> B問題 </font>|200 pts|02:26|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc204/submissions/23213187)||
|<font color=#804000> C問題 </font>|300 pts|17:04|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc204/submissions/23229889)||
|<font color=#008000> D問題 </font>|400 pts|08:03|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc204/submissions/23223538)||
|<font color=#0000FF> E問題 </font>|500 pts|<b>68:03</b>|<font color="red"> 3 Penalties </font>|[■](https://atcoder.jp/contests/abc204/submissions/23245785)<br>($t^\*$ を調べる範囲がやや広い)|[■](https://atcoder.jp/contests/abc204/submissions/23267929)|
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc204/submissions/23737379)|
|<b>Total</b>|<b>1500 pts</b>|<b>68:03</b>|<b><font color="red"> 3 Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 7) </font> [Rock-paper-scissors](https://atcoder.jp/contests/abc204/tasks/abc204_a)

じゃんけんにおいて, あいこになることの定義は以下である.

* 全員の手が同じである.
* グー, チョキ, パーの全ての手が出ている.

このこと, 参加者が3人であることから, 以下のようになる.

* 提示された2人の手が同じであるとき, あいこにするためにはその同じ手を出すしかない.
* 提示された2人の手が異なるとき, あいこにするためには2人が出していない手を出すしかない.

このことから, 以下のようなプログラムを書けば良い.

* $x=y$ ならば, $x$ を出力する.
* $x\neq y$ ならば, $0,1,2$ のうち $x,y$ に登場していない整数を出力する.

ここで, $0,1,2$ のうち $x,y$ に登場していない整数は $3-(x+y)$ であらわすことができる.

##<font color=#808080> B問題 (200pts, diff: 9) </font> [Nuts](https://atcoder.jp/contests/abc204/tasks/abc204_b)

$A_i>10$ を満たす全ての $i$ に対する $A_i-10$ の総和を求めれば良い. これは ${\tt for}$ 文によって実装できる. なお, 正解 $X$ は

$$X=\sum_{i=1}^N \max (A_i-10,0)$$

でもある.

##<font color=#804000> C問題 (300pts, diff: 629) </font> [Tour](https://atcoder.jp/contests/abc204/tasks/abc204_c)

始点となる都市を固定する (都市 $X$). このとき, 都市 $X$ から到達可能な都市の数はいくつか? を解くことになる. これは (有向) グラフにおける 深さ (or 幅) 優先探索によって解くことができる. この問題は計算量 $O(N+M)$ で解くことができる.

上の問題の答えを $T_X$ とする. ここで, 始点となる都市の組が異なれば, 組としても異なることから, 答えは

$$\sum_{X=1}^N T_X$$

である. 全体の計算量は $O(N(N+M))$ となり, $N,M \leq 2000$ の状況下では十分高速である.
 

##<font color=#008000> D問題 (400pts, diff: 832) </font> [Cooking](https://atcoder.jp/contests/abc204/tasks/abc204_d)

$[\\![N]\\!]=\\{1, \dots, N\\}$ とする. $I \subset [\\![N]\\!]$ を一方のオーブンに割り当てる料理の集合とすると, 他方のオーブンに割り当てる料理の集合は $[\\![N]\\!] \setminus I$ である. このときの所要時間 $E(I)$は

$$E(I)=\max \left(\sum_{i \in I} T_i,\sum_{i \in [\\![N]\\!] \setminus I} T_i \right)=\max \left(\sum_{i \in I} T_i,\sum_{i=1}^N T_i-\sum_{i \in I} T_i \right)$$

である. ここで, $T_{\rm sum}=\sum_{i=1}^N T_i, S(I):=\sum_{i \in I} T_i$ とすると,

$$E(I)=\max(S(I), T_{\rm  sum}-S(I))$$

である. よって, 求めるべきは $\min_{I \subset [\\![N]\\!]} E(I)$ である. ここで, $\mathcal{A}$ を
$$\mathcal{A}:=\\{S(I) \mid I \subset [\\![N]\\!] \\}$$

とする. この $\mathcal{A}$ は $T_1, \dots, T_N$ から選び出した整数の和として可能な整数全体の集合である. この $\mathcal{A}$ を用いて, 求めるべき値は

$$\min_{a \in \mathcal{A}} \max(a, T_{\rm sum}-a)$$

である.

ここから, この $\mathcal{A}$ を求めていく. この問題は部分和問題という問題で, 以下のような動的計画法で求めることができる:

配列 ${\rm DP}[i,x]$ を $T_1, \dots, T_i$ からいくつか選んで和をちょうど $x$ にできるかどうかを表すとする. このとき, ${\rm DP}[i,x]$ は

$${\rm DP}[i,x]=\begin{cases} \begin{cases} \mathbb{T} & (x=0) \\\\ \mathbb{F} & (x \neq 0) \end{cases} & (i=0) \\\\
\begin{cases} {\rm DP}[i-1, x] & (x<T_i) \\\\ {\rm DP}[i-1, x] \lor {\rm DP}[i-1, x-T_i] & (x \geq T_i) 
 \end{cases} & (i \geq 1) \end{cases}$$

によって求めることができる. この ${\rm DP}[i,x]$ において,
$$\mathcal{A}=\\{x \mid {\rm DP}[N,x]=\mathbb{T} \\}$$
である. 

計算量について, ${\rm DP}[i,x]$ で必要な添字は $0 \leq i \leq N, 0 \leq x \leq T_{\rm sum}$ であることから, $\mathcal{A}$ を計算量 $O(N T_{\rm sum})$ で求めることができることから, この問題を計算量 $O(N T_{\rm sum})$ で求めることができた.

##<font color=#0000FF> E問題 (500pts, diff: 1710) </font> [Rush Hour 2](https://atcoder.jp/contests/abc204/tasks/abc204_e)

都市 $N$ に最も早く到着することを目標にしているが, それ以外の都市についても任意の整数時間だけ待機できることから, 早く付けばそれだけ選択肢が増えることから全ての都市について最も早く到着するように移動すればよい.

ここで, 以下の問題を考える.
> 現在都市 $A$ に居て, 時刻 $T$ である. 時刻 $t$ に出発すると $C+\left \lfloor \dfrac{D}{t+1} \right \rfloor$ だけかかって都市 $B$ に到着する.
> 最も早く都市 $B$ に到着するためにはどうすればよいか?

時刻 $t$ に出発したときの到着時刻と $f(t)$ とする. このとき,
$$f(t)=t+C+\left \lfloor \dfrac{D}{t+1} \right \rfloor$$
である. ここで, 関数 $g$ を
$$g(t)=t+C+\dfrac{D}{t+1}$$
とする. この関数 $g$ について, 以下の事がわかる.

* $0 \leq t \leq \sqrt{D}-1$ では $g$ は単調減少
* $\sqrt{D}-1 \leq t$ では $g$ は単調増加
* $t$ が整数のとき $f(t)=\lfloor g(t) \rfloor$

上の事実から, $g(t)$ を最小にする $t$ を $t^\*$ とすると, $t^\*$ は以下のようになる.

* $\sqrt{D}-1 \leq T$ ならば, $t^\*=T$ である.
* $T \leq \sqrt{D}-1$ ならば,

$$t^*=\operatorname{argmin}_{\substack{t \in \\{\sqrt{D}-1, \sqrt{D}\\} \\\\ T \leq t}} f(t)$$
である.

この $t^\*$ を用いて, 都市 $1$ から都市 $N$ への最早路を Dijkstra 法の辺の重みを上での $f(t^*)$ に置き換えるような応用を行うことで計算量 $O(N+M \log N)$ で求めることができる.
 
##<font color=#C0C000> F問題 (600pts, diff: 2044) </font>[Hanjo 2](https://atcoder.jp/contests/abc204/tasks/abc204_f)

$[\\![H]\\!]=\\{1,\dots,H\\}$ とし, $\mathcal{P}([\\![H]\\!])$ で $[\\![H]\\!]$ のベキ集合を表すとする. ${\rm DP}[j,S]~[0 \leq j \leq W, S \in \mathcal{P}([\\![H]\\!])]$ を $(j-1)$ 列目までを完全に埋め, $(j+1)$ 行目以降は完全に空白であるような埋め方のうち, $i$ 行目においてタイルが埋まっている行の集合が $S$ と一致するような埋め方の場合の数とする.


自明な場合として,
$${\rm DP}[0,S]=\begin{cases} 1 & (S=\emptyset) \\\\ 0 & (S \neq \emptyset) \end{cases}$$
である. 次に, ${\rm DP}[j,S]$ と ${\rm DP}[j+1,T]$ $(S,T \in \mathcal{P}([\\![H]\\!]))$ の関係を考える.

このとき, 各 $T$ において実は
$${\rm DP}[j+1,T]=\sum_{S \in \mathcal{P}([\\![H]\\!])} \alpha(T,S) {\rm DP}[j,S] $$
となる <b> $j$ に依らない </b> 定数 $\alpha(T,S)$ が存在する. $\alpha(T,S)$ が $j$ に依らないので, 行列 $M$ を $\mathcal{P}([\\![H]\\!])$ を行集合, 列集合にとる行列で, $M=\[\alpha(T,S)\]\_{T,S \in \mathcal{P}([\\![H]\\!])}$ とする. また, ベクトル ${\boldsymbol v}^{(j)}$ を $\mathcal{P}([\\![H]\\!])$ を添字集合にとる縦ベクトルで, ${\boldsymbol v}^{(j)}=[{\rm DP}[i,S]]_{S \in \mathcal{P}([\\![H]\\!])}$ とする. このとき,

$${\boldsymbol v}^{(j+1)}=M {\boldsymbol v}^{(j)}$$

が成り立つことから, 行列累乗によって

$${\boldsymbol v}^{(W)}=M^W {\boldsymbol v}^{(0)}$$

となる. このとき, ${\boldsymbol v}^{(W)}$ の第 $\emptyset$ -成分が答えである. なお, ${\boldsymbol v}^{(0)}=[S=\emptyset]_{S \in \mathcal{P([\\![H]\\!])}}$ なので, ${\boldsymbol v}^{(W)}$ の第 $\emptyset$ -成分と, $M^W$ の第 $(\emptyset,\emptyset)$ 成分と一致する.

この行列累乗パートについて, $M$ のサイズは $|\mathcal{P}([\\![H]\\!])|=2^H$ であることから, 計算量 $O((2^H)^3 \log W)=O(8^H \log W)$ で $M^W$ を求めることができる.

最後に, $\alpha(T,S)$ を求める. 各 $S$ において, $p=(p_1, \dots, p_H)$ とタイルの置き方を以下のように対応付ける.

* $p_i=0$: パス (タイルを置かないというわけではない)
* $p_i=1$: マス $(i,j)$ に $1 \times 1$ のタイルを置く.
* $p_i=2$: マス $(i,j), (i+1,j)$ に $2 \times 1$ のタイルを置く.
* $p_i=3$: マス $(i,j), (i,j+1)$ に $1 \times 2$ のタイルを置く.

各 $p$ において, 以下を満たせば, このようなタイルの置き方は正当である.

* 場外からはみ出ない $(p_H \neq 2)$ 
* $j$ 列目に空白が生じない.
* ($S$ にあったタイルも含めて) タイルの二重置きが発生しない.

正当なタイルの置き方において, $U:=\\{i \in [\\![H]\\!] \mid p_i=3\\}$ としたとき, この置き方によって, $\alpha(U,S)$ に $1$ だけ寄与する.

ここで, $p$ は高々 $4^H$ 通りであり, $S$ のとり方として $2^H$ だけあるので, $\alpha(T,S)$ を $O(H8^H)$ で求めることができる.

以上から, この問題を $O(8^H(H+\log W))$ で求めることができ, $H \leq 6, W \leq 10^{18}$ という制約下では高速である.