#総合結果

[Score] 1500 pts
[Time] 55:48 + 5:00 $\times$ 0 = 55:48
[Ranking] 283 th [Rated内: 127 th]
[Performance] 2075　
[Rating] 1930 → 1945 (+15)

##各問題ごとの詳細, 提出コード

Question	Score	Time/Result	Penalty	During Contest	After Contest
A問題	100 pts	01:54		■
B問題	200 pts	03:20		■
C問題	300 pts	06:43		■	■
D問題	400 pts	16:05		■	■
E問題	500 pts	55:48		■	■
F問題	0 pts	--:--
G問題	0 pts	--:--			■
H問題	0 pts	--:--
Total	1500 pts	55:48	No Penalties

#問題ごとの感想
## A問題 (100pts, diff: 6) AtCoder Quiz 2

出力すべきものは

$$\begin{cases} 40-X & (0 \leq X <40) \\
70-X & (40 \leq X < 70) \\
90-X & (70 \leq X < 90) \\
{\tt expert} & (90 \leq X)
\end{cases}$$

である.

## B問題 (200pts, diff: 18) Maritozzo

$T[i]$ で $T$ の $i$ 番目の数字を表すことにして, 以下のようにして正解の文字列 $X$ を求めることができる.

$X$ を空文字列とする.
$i=1,2,\dots,|T|$ の順に以下を実行する.
- $X$ の末尾に $S_i$ を追加する.
このときの $X$ が答えである.

## C問題 (300pts, diff: 260) Neo-lexicographic Ordering

英小文字 $\alpha$ において, $I_\alpha$ で $\alpha$ が何番目かを表すとする. このとき, 文字列 $S=S[1] \cdots S[|S|]$ を数列 $(I_{S[1]}, \dots, I_{S[|S|]})$ に変換し, 数列の意味での辞書式の意味でソートすることにより, 所望のソートを行うことができる. ただし, 数列 $(x_1, \dots, x_k)$ を文字列 $X_{x_1} \cdots X_{x_k}$ に直すことを忘れないこと.

## D問題 (400pts, diff: 1085) Strange Lunchbox

動的計画法で解く. ${\rm DP}[k,x,y]$ を最初の $k$ 種類の弁当だけを見たとき, たこ焼きが $x$ 個以上, たい焼きが $y$ 個以上となる買い方のうち, 購入する弁当の最小値 (存在しない場合は $\infty$) とする. このとき, 最終的に求める値は ${\rm DP}[N,X,Y]$ である.

$k=0$ のとき
弁当を全く買わずに可能なのは $(x,y)=(0,0)$ のみに限る. よって,

$${\rm DP}[0,x,y]=\begin{cases} 0 & (x=y=0) \\ \infty & ({\rm otherwise}) \end{cases}$$

となる.

$k \geq 1$ のとき
配るDP の形の式で表す. ${\rm DP}[k-1,x,y]$ を求める際に, $k$ 種類目の弁当を買うかどうかで場合分けできる.
- 買わない場合
  このときは弁当 $1,2,\dots,k-1$ の場合を考えることになり, ${\rm DP}[k-1,x-y]$ である.
- 買う場合
  このときは弁当 $1,2,\dots,k-1$ で $x-A_k, y-A_k$ の場合を考えることになるので, ${\rm DP}[k-1, x-A_k,y-B_k]+1$ となる.
  よって, ${\rm DP}[k,x,y]=\min({\rm DP}[k-1,x,y], {\rm DP}[k-1, x-A_k, y-B_k]+1)$ で求めることができる.

ここで, ${\rm DP}[k-1, x-A_k, y-B_k]$ において, $x-A_k, y-B_k<0$ になる可能性があるが, 今, ${\rm DP}[k,x,y]$ はそれぞれ $x,y$ 個以上なのだから, 負の部分は $0$ とみなしてもよい. このことから,

$${\rm DP}[k,x,y]=\min({\rm DP}[k-1,x,y], {\rm DP}[k-1, \max(0, x-A_k), \max(0, y-B_k)]+1)$$

とすることができる.

時間計算量は配列の要素数が $O(NXY)$ で, 更新が $O(1)$ なので, 全体で $O(NXY)$ となり, 高速である.

## E問題 (500pts, diff: 1690) Moat

(囲む) 塀の作り方ではなく, 塀によって囲まれる領域で考えることにする. これらはそれぞれ1対1に対応する.

塀によって囲まれる領域は $4 \times 4=16$ のブロックに別れ, それぞれにおいて採用する採用しないの $2$ 通りがあり, 独立に決定できることから, 領域の選択肢は $2^{16}=65536$ であり, 全列挙可能である.

ある領域 $T$ が条件を満たすかどうかを考える. 領域で考えたことにより, 以下を全て満たすかどうかをチェックすれば良い.

全ての村は領域 $T$ に含まれる.
$T$ は連結である.
$T$ に属さない部分+外周が連結

1.は愚直に済み, 2.,3. はBFS や DFS を利用することにより, $N=4$ として, 共に $O(N^2)$ で判定できる. 以上から, 上の3条件を全て満たすような領域の個数を求めることにより, 計算量 $O(N^2 2^{N^2})$ で計算できる.

## F問題 (500pts, diff: 2542) Cleaning Robot

(正解でき次第加筆)

## G問題 (600pts, diff: 2287) Propagation
(2021/09/21 加筆)

与えられたグラフを $G=(V:=[\![N]\!],E)$ とする. この問題のポイントは, 次数が多い頂点に対する更新をどのように処理するかである.

以下, 頂点 $v \in V$ の次数を $d(v)$ とする. ここで,　定数 $B$ を設定する (決め方は最後に述べる).

頂点集合の2つの分割 $V=L \coprod S$ をそれぞれ

$L=\{v \in V \mid d(v) \geq B\}$
$S=\{v \in V \mid d(v) < B\}$

とし, $v \in L$ であるような頂点を "大きい頂点", $v \in S$ であるような頂点を "小さい頂点" ということにする.

各クエリは $x$ が与えられた際, 以下のように処理される. また, このクエリが $t$ 番目のクエリ (クエリ番号) であるとする.

その時点での頂点 $x$ にかかれている整数 $K$ を特定する.
隣接する頂点全てに $x$ を書き込む.

このとき, $x$ が大きい頂点か小さい頂点かどうかで処理を場合分けする.

先に, 書き込みについて考える.

$x$ が小さい頂点だった場合, $x$ の各近傍 $y$ において, 頂点 $y$ に「小さい頂点からの $t$ 番目のクエリで, $K$ になった」と記録 (上書き) する.
$x$ が大きい頂点だった場合, 頂点 $x$ に「$t$ 番目のクエリで, 隣接する頂点に $K$ を書き込む」と記録 (上書き) する.

このとき, 計算量は $x$ が大きい頂点だった場合は $O(1)$, 小さい頂点だった場合, $d(x) <B$ なので, $O(B)$ であり, 書き込みの計算量は $O(B)$ でできることがわかった.

次に, $K$ の特定方法を考える. 小さい頂点からの書き込みと, 大きい頂点からの書き込みそれぞれで場合分けする.

小さい頂点からの書き込みは直接記録していることから, $x$ の小さい頂点からの書き込みの情報を見れば良い (クエリ番号を $t_s$ とする).
大きい頂点からの書き込みについては, $x$ の近傍のうち, 大きい頂点であるものについての記録を見る. このとき, クエリ番号が最大になるような情報が最近で大きい頂点からの書き込みの情報になる (この情報のクエリ番号を $t_l$ とする).

そして, $t_s, t_l$ のうち, 大きい方の情報が持っている整数が現在その頂点に書き込まれている整数となる.

計算量は, 小さい頂点からの書き込みの確認は $O(1)$ ででき, 大きい頂点からの書き込みの確認は $O(|L|)$ でできる.

$|L|$ について考える. 握手補題から, $\sum_{v=1}^N d(v)=2M$ が成り立つ. このことから, $|L| \leq \frac{2M}{B}$ であることがわかり, $|L|=O \left(\frac{M}{B} \right)$ となる.

以上から, $Q$ 個のクエリを全部で $O \left(Q \left(B+\dfrac{M}{B} \right) \right)$ で処理できることが分かった.

ここで, $B$ をうまく設定する必要があるが, $B$ を $\sqrt{M}$ 程度に設定すると, $O \left(Q \left(B+\dfrac{M}{B} \right) \right)=O(Q\sqrt{M})$ となり, 高速で処理できる.

## H問題 (600pts, diff: 3297) Candles

(正解でき次第加筆)