キーエンス プログラミング コンテスト 2021 感想

##総合結果
* [Score] 1200 pts
* [Time] 89:38+<font color="red"> 05:00 $\times$ 0</font>=89:38
* [Ranking] 813 rd [Rated 内: 792 nd]
* [Performance] <font color=#00C0C0> 1566　</font>
* [Rating] <font color=#0000FF> 1809 </font> → <font color=#0000FF> 1787 </font> (-22)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 05:45
* <font color=#808080> B問題 </font> 12:01
* <font color=#00C0C0> C問題 </font> 89:38
* <font color=#C0C000> D問題 </font> --:--
* <font color=#FF8000> E問題 </font> --:--
* <font color=#B87333> F問題 </font> --:--

##提出コード
* <font color=#808080> A問題 </font> [■](https://atcoder.jp/contests/keyence2021/submissions/19461691)
* <font color=#808080> B問題 </font> [■](https://atcoder.jp/contests/keyence2021/submissions/19463317)
* <font color=#00C0C0> C問題 </font> [■](https://atcoder.jp/contests/keyence2021/submissions/19473909)

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff: 155) </font> [Two Sequences 2](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_a)
集合 $S_i$ を
$$S_i:=\\{a_i b_j |1 \leq i \leq j \leq n\\}$$
とする. このとき, 求めるべき $c_i$ は $c_i=\max S_i$ である.

まず, $S_1=\\{a_1 b_1\\}$ なので, $c_1=a_1 b_1$ であることがわかる.

ここで, $S_{i-1}, S_i$ の間には以下のような関係がある.
$$S_i=S_{i-1} \cup \\{a_1 b_i, a_2 b_i, \dots a_i b_i \\}$$
このとき, $b_i \geq 0$ なので,
$$c_i=\max S_i=\max \\{ \max S_{i-1}, \max \\{a_1 b_i, \dots, a_i b_i \\})=\max \\{c_{i-1}, b_i \max \\{a_1,\dots, a_i\\} \\}$$
である. $\alpha_i :=\max \\{a_1,\dots,a_n\\}$ とすることによって, $c_i=\max \\{c_i,\alpha_i b_i\\}$ となる. 最後に, $\alpha_i$ は
$$\alpha_i:=\begin{cases} a_1 & (i=1) \\\\ \max \\{\alpha_{i-1},a_i\\\} & (i \geq 2)\end{cases}$$
という関係を用いることによって, $(\alpha_i)\_{i=1}^N$ を計算量 $O(N)$ で求めることができる. よって,全体でも計算量 $O(N)$  求めることができた.

##<font color=#808080> B問題 (400pts, diff: 308) </font> [Mex Boxes](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_b)
必要ならばソートして, $A_1 \leq \dots \leq A_N$ とする.
このとき, $i=1, \dots, N$ の順に以下のようにしてボールを箱に入れていく.

* 既に箱に入っているボールは全て $A_i$ 以下なので, 蓋に書かれている数字は高々 $A_i+1$ である.
* ボールを入れようとする箱に書かれている蓋の数字を $x$ とする. 
 * $x<A_i$ のとき, その箱にボールを入れても蓋の数字は変わらない.
 * $x=A_i$ のとき, その箱にボールを入れると, 蓋の数字は $1$ 増える.
 * $x=A_i+1$ のとき, その箱にボールを入れても蓋の数字は変わらない.
 よって, 存在するならば, 蓋に $A_i$ と書かれた箱にボールを入れるべきである(存在しないならば, 任意の箱に入れて良い).

よって, 順次 $k (k=0,\dots,N)$ と蓋に書かれている箱の個数を管理することによって, 計算量を $O(N \log N)$ で求めることができた.

##<font color=#00C0C0> C問題 (500pts, diff: 1468) </font> [Robot on Grid](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_c)
総和を $X$ とする. $\mathcal{T}$ を空白のマスの塗り方全体の集合, $\mathcal{P}$を, マス $(1,1)$ からマス $(H,W)$ への行き方のうち, 右または下のみの移動で構成されているもの全体の集合とする. このとき, 
$$ X=\sum_{T \in \mathcal{T}} \sum_{P \in \mathcal{P}} ~[Tと塗った時, Pは可能]$$
であるが, 2つのシグマを交換することによって, 
$$ X=\sum_{P \in \mathcal{P}} \sum_{T \in \mathcal{T}} ~[Tと塗った時, Pは可能]$$
となる. よって, マス $(1,1)$ からマス $(H,W)$ への行き方を1つ固定した時, その行き方を可能にする空白マスの塗り方を求めることができれば, その合計が $X$ になる.

動的計画法で解く. ${\rm DP}[i,j]$ を 問題を $(1,1), \dots, (1,j), (2,1) ,\dots, (i,j)$ の $ij$ マスに制限し, マス $(i,j)$ の状態を考慮しない時の答えとする. 

${\rm DP\}[1,1]=1$ は自明である. 
マス $(1,1)$ からマス$(i,j)$ への生き方は, $(i-1,j)$ から移動されるものと, $(i,j-1)$ から移動されるものに分割される.

$(i-1,j)$ から移動されるものについて考える. ここで, 以下のことに注意する.
> $(i-1,j)$ から $(i,j)$ へ移動する行き方は $(i,1), \dots, (i,j-1)$ の状態によらない.

* マス $(i-1,j)$ に書かれている文字が ${\tt R}$ のとき: $(i-1,j)$ から $(i,j)$ への移動は不可能である.
* マス $(i-1,j)$ に書かれている文字が ${\tt X}, {\tt D}$ のとき: $(i-1,j)$ の状態は確定しているが, $(i-1,j)$ から $(i,j)$ への移動は可能である.
* マス $(i-1,j)$ が空白のとき: $(i-1,j)$ から $(i,j)$ への移動を可能にする $(i-1,j)$ への書き込みは, ${\tt X}, {\tt D}$ の2つである.

そして, 上で述べた注意より, $(i,1), \dots, (i,j-1)$ にある空白のマスの個数を $q_{i,j}$ とすると, $(i-1,j)$ から移動される行き方による寄与は
$$\left(\begin{cases} 2 & (c_{i-1,j}=\emptyset) \\\\
1 & (c_{i-1,j}={\tt X}, {\tt D}) \\\\
0 & (c_{i-1,j}={\tt R}) \\\\ \end{cases} \right) \times 3^{q_{i,j}} {\rm DP}[i-1,j]$$
である. ただし, $c_{i,j}$ は $(i,j)$ に書かれている文字を表し, $c_{i,j}=\emptyset$ は $(i,j)$ に文字が書かれていないことを表す. 同様にして, $(1,j), \dots, (i-1,j)$ にある空白マスの個数を $p_{i,j}$ とする. $(i-1,j)$ から移動される行き方による寄与も考えることによって, 漸化式は
$${\rm DP}[i,j]=\left(\begin{cases} 2 & (c_{i-1,j}=\emptyset) \\\\
1 & (c_{i-1,j}={\tt X}, {\tt D}) \\\\
0 & (c_{i-1,j}={\tt R}) \\\\ \end{cases} \right) \times 3^{q_{i,j}} {\rm DP}[i-1,j]+\left(\begin{cases} 2 & (c_{i,j-1}=\emptyset) \\\\
1 & (c_{i,j-1}={\tt X}, {\tt R}) \\\\
0 & (c_{i,j-1}={\tt D}) \\\\ \end{cases} \right) \times 3^{p_{i,j}} {\rm DP}[i,j-1]$$
となることが分かった. よって, 総和は
$$\begin{cases} DP[H,W] & (c_{i,j} \neq \emptyset) \\\\ 3DP[H,W] & (c_{i,j}=\emptyset) \end{cases}$$
である. なお, 計算量は $O(HW)$ である.

##<font color=#C0C000> D問題 (700pts, diff: 2115) </font> [Choosing Up Sides](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_d)
(正解でき次第掲載)

##<font color=#FF8000> E問題 (700pts, diff: 2560) </font> [Greedy Ant](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_e)
(未着手)

##<font color=#B87333> F問題 (1000pts, diff: 3461) </font> [Keyence Repetition](https://atcoder.jp/contests/keyence2021/tasks/keyence2021_f)
(未着手)

#感想
##反省点

* <font color=#00C0C0>C問題</font>が圧倒的に遅すぎる.