ZONeエナジー プログラミングコンテスト “HELLO SPACE” 感想

#総合結果
* [Score] 1500 pts
* [Time] 67:08 + <font color="red"> 05:00 $\times$ 1 </font> = 72:08
* [Ranking] 408 th [Rated内: 172 nd]
* [Performance] <font color=#C0C000> 2001　</font>
* [Rating] <font color=#0000FF> 1969 </font> → <font color=#0000FF> 1972 </font> (+3) (Highest!!!)

##各問題ごとの詳細, 提出コード [^0]
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:20|<font color="red"> </font>|[■](https://atcoder.jp/contests/zone2021/submissions/22195861)|[■](https://atcoder.jp/contests/zone2021/submissions/22244597)<br>(別解)|
|<font color=#808080> B問題 </font>|200 pts|08:25|<font color="red"> </font>|[■](https://atcoder.jp/contests/zone2021/submissions/22201764)|[■](https://atcoder.jp/contests/zone2021/submissions/22244562)|
|<font color=#00C0C0> C問題 </font>|400 pts|21:22|<font color="red"> </font>|[■](https://atcoder.jp/contests/zone2021/submissions/22207402)<br>(計算量 $O((N^2+2^{2h})\log \lambda)$)|[■](https://atcoder.jp/contests/zone2021/submissions/22236689)<br>(計算量 $O((N+2^{3h})\log \lambda)$)<br>[■](https://atcoder.jp/contests/zone2021/submissions/22244303)<br>(計算量 $O((N+2^{3h}) \log N)$)[^000]|
|<font color=#804000> D問題 </font>|300 pts|12:13|<font color="red"> </font>|[■](https://atcoder.jp/contests/zone2021/submissions/22203512)||
|<font color=#0000FF> E問題 </font>|500 pts|67:08|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/zone2021/submissions/22222787)||
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> (2 Penalties)[^00] </font>||[■](https://atcoder.jp/contests/zone2021/submissions/22244092)|
|<b>Total</b>|<b>0 pts</b>|<b>67:08</b>|<b><font color="red"> 1 Penalty </font></b>|||

[^0]: このコンテストはABC相当であるが, [C], [D] の配点が通常と異なることが事前にアナウンスされていた.
[^00]: ACできなかったので, ノーカウントになる.
[^000]: $h:=|H|$ としている. なお, $H, \lambda$ の定義は [C] の説明で定義している.

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 12) </font> [UFO襲来](https://atcoder.jp/contests/zone2021/tasks/zone2021_a)

$|S|=12$ なので, 連続する4文字の部分列として可能なのは, $S[0:3], S[1:4], \dots, S[8:11]$ の計 $9$ 個である. よって, この $9$ 個の部分列を ${\tt for}$ 文で回したり, 頑張って愚直に ${\tt ZONe}$ となる個数を求めることができる.

別解として, 標準に搭載されている関数を用いて, $S$ の中に ${\tt ZONe}$ はいくつかあるかを求めることもできる.

##<font color=#808080> B問題 (200pts, diff: 139) </font> [友好の印](https://atcoder.jp/contests/zone2021/tasks/zone2021_b)

距離 $d_i$, 高さ $h_i$ の建物が遮る範囲を求める. 2点 $(d_i, h_i), (D, H)$ が通る直線は
$$y=m_i (x-D)+H=m_i x+H-m_i D,\quad \left(m_i=\dfrac{H-h_i}{D-d_i} \right)$$

である. よって, 建物 $i$ が遮る範囲は $0 \leq y < H-m_i D$ である. よって, $i=1,2, \dots, N$ とすると, $N$ 個の建物が遮る範囲は $0 \leq y < \max_{i=1, \dots, N} (H-m_i D)$ より, 求めるべきは
$$\max \left(\max_{i=1, \dots, N} (H-m_i D), 0 \right)$$
である. なお, $m_0:=\frac{H}{D}$ とすると,
$$\max_{i=0,1, \dots, N} (H-m_i D)=H-D \times \left(\min_{i=0,1, \dots, N} m_i \right)$$
である.

##<font color=#00C0C0> C問題 (400pts, diff: 1497) </font> [MAD TEAM](https://atcoder.jp/contests/zone2021/tasks/zone2021_c)

求めるべきは最小値の最大値なので, 以下の小問題を考える.

> $T(x):$ チームの総合力を $x$ 以上にすることは可能か?

このとき, $x \leq y$ で $T(y)$ が可能ならば, $T(x)$ も可能である. よって, $T$ は単調減少である. よって, 求めるべきは
$$\max \\{x \in \mathbb{N} \mid T(x)は可能である\\}$$
であり, この値は二分探索で求めることができる. 自明な下界は $0$ で, 自明な上界は
$$\lambda:=\max(\max A, \max B, \max C, \max D, \max E)+1$$
である.

以下, $T(x)$ について考える. $i=1, \dots, N$ に対して, $P_{i,x}$ で $i$ 番目のメンバーのうち, $x$ 以上のパラメータ全体の集合とする. このとき,
$$P_{i,x}\cup P_{j,x} \cup P_{k,x}= \\{パワー, スピード, テクニック, 知識, 発想力\\}:=H$$
となる $i,j,k$ が存在すれば, $T(x)$ は可能である.

ここで, $i,j,k$ を全探索すると間に合わないが, $P_{i,x}$ として可能なのは $2^5=32$ 通りと少なく, $\mathcal{J}\_x:=\\{P_{i,x} \subset H \mid i=1, \dots, N\\}$ すると, $|\mathcal{J}\_x| \leq 32$ であり, $X, Y, Z \in \mathcal{J}\_x$ で $X \cup Y \cup Z=H$ となる $X,Y,Z$ が存在するかは単純な全探索で間に合う.

計算量は $O(|H|^3 N \log \lambda)$ である.

##<font color=#804000> D問題 (300pts, diff: 719) </font> [宇宙人からのメッセージ](https://atcoder.jp/contests/zone2021/tasks/zone2021_d)

前半パートと後半パートに分かれる.

* 前半パート: 反転グラフ $F$ と両端キュー $Q$ を用意する. 反転フラグが立っていないときは $Q$ の後ろから, 反転フラグが立っているときは $Q$ の前から文字を追加する. また, 反転の支持が出た場合はフラグの状態を変更する. そして, 全ての文字の操作が終わった際, 反転フラグが立っていたら $Q$ を反転させる.
* 後半パート: 配列 $R$ を用意する. $Q$ の先頭から順に $R$ の後ろから文字を追加する. ただし, 文字を追加した後, $R$ のサイズの $2$ 以上で 後ろ $2$ つの文字が一致するならば, この $2$ つを削除する. この方針で $Q$ の最後まで実行したときに残った $R$ 内の文字を順につなげると, 求めるべき文字列が得られる.

##<font color=#0000FF> E問題 (500pts, diff: 1624) </font> [潜入](https://atcoder.jp/contests/zone2021/tasks/zone2021_e)

与えられたグリッドグラフを $D=(V, A, C)$ とする. この $D$ 上で愚直に最短路を求めようとすると, 辺の数が $O(R^2 C)$ となり実行時間制限に間に合わない可能性がある. そこで, $D$ から新たな $D'=(V', A', C')$ を作り, $D'$ 上で解くことを考える.

$V'$ を $V$ 2つのコピーの直和とする (以降の説明の都合上, $V'=V \coprod V^\*$ とし, $v \in V$ に対して, $v^* \in V^\*$ が自然に対応づいているとする). 

有向辺全体の集合 $A'$ を
$$A'=A \cup \\left\\{\overrightarrow{vv^\*} \mid v \in V \\right\\} \cup \\left\\{\overrightarrow{v^\* v} \mid v \in V \\right\\} \cup \\left\\{\overrightarrow{u^\* v^\*} \mid u,v \in V, vはuの真上 \\right\\}$$
とする. また, コストを 
$$C'(\overrightarrow{xy}):=\begin{cases} C(\overrightarrow{xy}) & (\overrightarrow{xy} \in A) \\\\
0 & (\overrightarrow{xy}=\overrightarrow{vv^\*}) \\\\
1 & (\overrightarrow{xy}=\overrightarrow{v^\*v}) \\\\
1 & (\overrightarrow{xy}=\overrightarrow{u^\* v^\*}, vはuの真上) \end{cases}$$

このように作ったグラフ上で 元々の始点と終点を $S,T$ としたとき, $D'$ 上での $S,T$ -最短路のコストがそのまま求めるべき答えになる.

##<font color=#C0C000> F問題 (600pts, diff: 2197) </font>[出会いと別れ](https://atcoder.jp/contests/zone2021/tasks/zone2021_f)

$0$ 以上 $N=2^n$ 未満全体の整数の集合 $V$ はxor $\oplus$ を和, $\mathbb{F}_2$ とのスカラー倍を
$$[1]_2 x:=x, \quad [0]_2 \cdot x:=0 \quad (x \in V)$$
と定めることにより, 体 $\mathbb{F}_2$ 上のベクトル空間とみなせる.

与えられた数列 $A$ を集合とみなし, $S:=V \setminus A$ とする. このとき, 条件を満たすようなゲートの通し方が存在することと, $\langle S \rangle =V$ であることは同値である.

* $(\Rightarrow):$ $v \in V$ に対して, $0$ を始点, $v$ を終点とする歩道が存在する. この歩道が辿った頂点を $0=x_0, x_1, \dots, x_m=v$ とする. このとき, $x_j \oplus x_{j-1} \in S$ であるので,
 $$v=v \oplus (x_{m-1} \oplus x_{m-1}) \oplus \dots \oplus (x_1 \oplus x_1) \oplus 0=(v \oplus x_{m-1}) \oplus \dots \oplus (x_1 \oplus 0) \in \langle S \rangle$$
である.
* $(\Leftarrow):$ 任意の $x,y \in V$ に対して, $y-x \in V$ なので, $w_1, \dots, w_s$ で $y=x \oplus w_1 \oplus\dots \oplus w_s$ なるものが取れる. このとき, $x \to x \oplus w_1 \to \dots \to x \oplus w_1 \oplus \dots \oplus w_s$ は移動可能である. よって, 各 $v \in V$ に対して, $v \oplus u ~(u \in S)$ を近傍とするグラフを考えると, このグラフは連結であり, 連結成分における全域木の存在性から, 木が存在する. 木には辺の数が $N-1$ 本あるので, この全域木の各辺 $uv$ に対して, ワープゲート $(u,v)$ を設置すれば良い. なお, 全域木の発見は実装の際には深さ(幅)優先探索で十分である.

よって, $\langle S \rangle =V$ かどうかを判定すれば, 構築可能かどうかは答えることはできる. $S$ に対して掃き出し法を実施した結果で非零のベクトルの個数が $n$ ならば構築可能, $n$ 未満ならば構築不能である.

以下, 構築可能とする. このとき, $V$ の基底として, $w_1, \dots, w_n \in S$ が取れるが, これを構成しなければならない. これは例えば以下のようにすれば良い.

* $V_0:=V, W_0:=\\{0\\}$ とする.
* $i=0$ からインクリメントしながら以下を実行する.
    * $V_i$ がゼロベクトルからなる1要素の集合ならば終了する.
    * $V_i$ のゼロベクトルでないベクトルを1つ取り, $w_{i+1}$ とする. このとき, $W_{i+1}:=\langle W_i \cup \\{w_{i+1}\\} \rangle, V_{i+1}:=V_i/W_{i+1}$ と設定する.
 
ただし, ゼロベクトルでないベクトルを1つ取るとき, 元々 $S$ のどの要素だったのかも記録しておくこと.

#感想

##総評
アナウンスの時点で<font color=#00C0C0>C問題</font>, <font color=#804000>D問題</font>の得点が異なっていることが判明していたため, この2問をうまく処理できるかどうかが良い成績を取るためのポイントになった.

##良かった点
* <font color=#804000>D問題</font>までは高速に解くことができた.

##反省点
* <font color=#C0C000>F問題</font>は解かなくてはいけない問題であった.
* <font color=#FF0000>WA</font>の理由
 * <font color=#0000FF>E問題</font> 上がる処理の考察ミス
 * <font color=#C0C000>F問題</font> $V/W$ の要素がどこ由来か記録していなかった.

#<font color=#C0C000>黄色</font>になるためには
次回のコンテストのPerformanceが<font color=#C0C000>2219</font>以上ならば, <font color=#C0C000>黄色</font>達成.