#総合結果

[Score] 2000 pts
[Time] 49:57 + 05:00 $\times$ 2 = 59:57
[Ranking] 275 th [Rated内: 129 th]
[Performance] 2116　
[Rating] 1908 → 1930 (+32)

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

Question	Score	Time/Result	Penalty	During Contest
A問題	100 pts	00:49		■
B問題	200 pts	02:32		■
C問題	300 pts	08:56		■
D問題	400 pts	13:37		■
E問題	500 pts	34:04	2 Penalties	■
F問題	500 pts	49:57		■
G問題	0 pts	--:--
H問題	0 pts	--:--
Total	2000 pts	59:57	2 Penalties

#問題ごとの感想
## A問題 (100pts, diff: 7) Weather Forecast

文字列 $T$ の左から $k$ 文字目を $T[k]$ と書くことにすると, $S[N]={\tt "o"}$ ならば ${\tt "Yes"}$, $S[N]={\tt "x"}$ ならば ${\tt "No"}$ と出力しなれければならない.

ただし, 大抵のプログラミング言語では左端が $0$ 番目となっているので, 自分が使っている言語がどのようになっているかを確認すること.

## B問題 (200pts, diff: 14) qwerty

$X$ は長さが $26$ の文字列で, $X={\tt "ABC} \cdots {\tt XYZ"}$ とする. このとき, 求めるべき文字列 $S$ は $S[i]=X[P[i]]$ を満たす. これを $i=1,2,\dots, 26$ の順に求めれば良い. ただし, $\mathcal{A}$ 問題でも述べたように, 大抵のプログラミング言語では左端が $0$ 番目となっているので, 自分が使っている言語がどのようになっているかを確認すること.

## C問題 (300pts, diff: 1012) Shapes

回転の方法は4通りであり, それぞれの回転を固定した際に1つでも平行移動によって一致する方法が存在するような回転があれば, 答えは YES で, なければ答えは NO である.

回転を固定する. このとき, もし一致する平行移動が存在するならば, その平行移動は一意に定まる. このことから, $S,T$ のマスで共通するある特徴を持つマスに着目してその着目したマスに関する平行移動が一致するかをみればよい. このある特徴を持つマスの例としては例えば

$S$ 上で ${\tt \#}$ であるマスを $(i^S_1, j^S_1), \dots, (i^S_k, j^S_k)$ としたとき, $I^S:= \min (i^S_1, \dots, i^S_k), J^S:=\min (j^S_1, \dots, j^S_k)$ としたときのマス $(I^S,J^S)$. $T$ についても同様.
${\tt \#}$ であるマスのうち, 辞書式最小のマス

この場合, 計算量は $O(N^2)$ である.

## D問題 (400pts, diff: 715) Rectangles

全ての辺が軸に平行な長方形の頂点の座標は $4$ つの実数 $a,b,a',b' \in \mathbb{R}~(a \neq a', b \neq b')$ を用いて, $(a,b), (a',b), (a,b'), (a',b')$ となる.

ここで, $(a,b), (a',b')$ が定まれば, 残りの $(a',b), (a,b')$ も自動的に定まることに着目すると, $(a,b), (a',b')$ の組それぞれに対して, $(a',b), (a,b')$ 共に存在するかどうかを判定することにより, $(a,b), (a',b')$ の全探索により, $O(N^2)$ で求めることができる.

ただし, 何も考えずに実装すると, 1つの長方形に対して複数回カウントしてしまう可能性があるので, 複数回のカウントを避けなくてはならない. 例えば, $a<a', b<b'$ のときのみ判定するという方法がある.

## E問題 (500pts, diff: 1004) Destruction

与えられる連結グラフを $G=(V,E)$ とし, $I:=\{1,2,\dots,M\}$ とする. このとき, この問題は以下のようになる.

$K \subset I$ に対して, $G_K:=(V,E')~(E':=\{A_k B_k \in E \mid k \in K\})$ とする.
このとき, $G_{J^c}$ を連結にするという条件下で, $\displaystyle \sum_{j \in J} C_j$ を最大化せよ.

ここで, $J$ の選び方に関わらず, $\sum_{j=1}^M C_j$ は一定であることから, $\sum_{j \in J} C_j=\sum_{j=1}^M C_j-\sum_{j \in J^c} C_j$ を考え, $J^c$ を $J$ に置き換えることにより, 以下の問題に帰着できる.

$K \subset I$ に対して, $G_{J}$ を連結にするという条件下で, $\displaystyle \sum_{j \in J} C_j$ を最小化せよ.

このとき, 全ての $j \in I$ に対して, $C_j \geq 0$ ならば, この問題は最小全域木の問題そのものである. ただし, 今回は $C_j<0$ の可能性があるので, 最小全域木を求めるアルゴリズム ¹ で求まった答えをそのまま使うことはできない.

ただし, 最小全域木を求めるアルゴリズムによって取り除く可能性がある辺のうち, $C_j<0$ となる辺は取り除かなくても完成したグラフは連結であることから, 求めるべき答えは

最小全域木から外れた辺のうち, $C_j>0$ であるような辺における $C_j$ の総和

である. 計算量はたとえば　Kruskal 法を利用することにより, 計算量 $O(M \log N)$ で求めることができる.

## F問題 (500pts, diff: 1753) Blocked Roads

与えられたグラフを $D$ とし, $D$ から辺 $i$ を除いたグラフを $D_i$ とする. また, グラフ $F$ に対して, $\gamma(F)$ を $F$ 上での頂点 $1$ と頂点 $N$ の距離　($1$ - $N$ Path が存在しない場合は $\infty$) とする. ここで, 考察により, 以下の2つの事がわかる.

$\gamma(D)<\infty$ とする. $D$ における $1$ - $N$ 最短路 $P^D_{1,N}$ を 1つ取る. このとき $\overrightarrow{A_i B_i}$ が $P^D_{1,N}$ の辺に含まれていなければ, $\gamma(D_i)=\gamma(D)$ である.
$\gamma(D)<\infty \Rightarrow \gamma(D)<N$

(証明)

$\overrightarrow{A_i B_i}$ が $P^D_{1,N}$ に含まれていなければ, $D_i$ 上でも $P^D_{1,N}$ がそのまま $D_i$ 上の $1$ - $N$ Path になる. また, $D_i$ は $D$ の部分グラフなので, $\gamma(D_i)<\gamma(D)$ となることはない. よって, $\gamma(D_i)=\gamma(D)$ である.
$P^D_{1,N}$ が辿る頂点を順に $1=v_0, v_1, \dots, v_{\gamma(D)}=N$ とする. このとき, $\gamma(D) \geq N$ ならば, $v_0, v_1, \dots, v_{\gamma(D)}$ には少なくとも $N+1$ 個の要素があり, $1 \leq v_i \leq N$ なので, 鳩ノ巣原理から, $i \neq j$ で, $v_i=v_j$ となるものが存在する. $i<j$ として, $1=v_0, \dots, v_{i-1}, v_j \dots, v_{\gamma(D)}=N$ は $P^D_{1,N}$ よりも真に短くなり, $P^D_{1,N}$ が $1$ - $N$ 最短路であることに矛盾する. よって, $\gamma(D)<N$ である.

このことから, 以下のようにして, $\gamma(D_i)$ を求める事ができる.

$\gamma(D)$ を求める. これは BFS で求めることができる. このとき, $\gamma(D)=\infty$ ならば, $\gamma(D_1)=\dots=\gamma(D_N)=\infty$ で確定である.
$\gamma(D)<\infty$ とし, $P^D_{1,N}$ をなす有向辺を $a_i=\overrightarrow{A_i B_i}$ として, $a_{j_1}, \dots, a_{j_{\gamma(D)}}$ とする.
- $k=1, \dots, M$ に対して, 以下のようにして $\gamma(D_k)$ を求める.
- $k \not \in \{j_1, \dots, j_{\gamma(D)}\}$ ならば, 上での 1. から, $\gamma(D_k)=\gamma(D)$ である.
- $k \in \{j_1, \dots, j_{\gamma(D)}\}$ ならば, $D_k$ 上での BFS で $\gamma(D_k)$ を求めることができる.

ここで, 頂点数 $|V|$, 有向辺の数 $|A|$ における BFS の計算量は $O(|V|+|A|)$ であり, BFS は上の 2. から高々 $N$ 回で十分であることに着目すると, 計算量 $O(N(N+M))$ であり, 今回の有向グラフは単純であることから, $M=O(N^2)$ なので, $O(N(N+M))=O(N^3)$ となり, 高速に求まる.

## G問題 (600pts, diff: 2217) Game on Tree 2

(正解でき次第加筆予定)

## H問題 (600pts, diff: 2805) Red and Blue Lamps

(正解でき次第加筆予定)

Kruskal 法やPrim 法 ↩