パナソニックプログラミングコンテスト (AtCoder Beginner Contest 186) 感想

##総合結果
* [Score] 2100 pts (★Perfect★)
* [Time] 71:08+<font color=#FF0000>05:00$\times$1</font>=76:08
* [Ranking] 207th (Rated内:75th)
* [Performance] <font color=#C0C000>2202</font>
* [Rating] <font color=#0000FF>1686</font>→<font color=#0000FF>1750</font> (+64)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 00:30
* <font color=#808080> B問題 </font> 02:30
* <font color=#808080> C問題 </font> 04:09
* <font color=#804000> D問題 </font> 08:51 
* <font color=#00C0C0> E問題 </font> 27:38
* <font color="blue"> F問題 </font> 71:08 <font color="red"> (+1 PENALTY) </font>

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff:4) </font> [Brick](https://atcoder.jp/contests/abc186/tasks/abc186_a)
答えは $\left \lfloor \frac{N}{W} \right \rfloor$ である.

##<font color=#808080> B問題 (200pts, diff:27) </font> [Blocks on Grid](https://atcoder.jp/contests/abc186/tasks/abc186_b)
各マスについて, ブロックのマスを増やすことはできないので, 各マスで目指すべきブロックの個数は
$$\alpha:=\min_{\substack{1 \leq i \leq H \\\\ 1 \leq j \leq W}} A_{i,j}$$
である. よって, 求めるべき値は
$$\sum_{\substack{1 \leq i \leq H \\\\ 1 \leq j \leq W}} (A_{i,j}-\alpha)=\sum_{\substack{1 \leq i \leq H \\\\ 1 \leq j \leq W}} A_{i,j}-HW\alpha$$
である.
##<font color=#808080> C問題 (300pts, diff:131) </font> [Unlucky 7](https://atcoder.jp/contests/abc186/tasks/abc186_c)
整数 $N$ の $d$-進表記は $O(\log_d N)$ で求めることができる. この求める際に $7$ が含まれるかどうかを判定すれば, 1つの整数 $N$ について $O(\log_d N)$ で判定できる. 今回の問題は $N \leq 10^5$ なので, $M=1,2,\dots,N$ について, 1つずつ整数 $M$ が条件を満たすかを調べれば, 全体で $O(N\log N)$ で答えを出すことができる.

##<font color=#804000> D問題 (400pts, diff:436) </font> [Sum of difference](https://atcoder.jp/contests/abc186/tasks/abc186_d)
数列 $A$ の各項は昇順であっても問題ない. つまり, $A_1 \leq \dots \leq A_N$ としても問題ない. このとき, 求めるべき値を $X$ とすると,
$$ X=\sum_{i=1}^{N-1} \sum_{j=i+1}^N |A_i-A_j|=\sum_{i=1}^{N-1} \sum_{j=i+1}^N (A_i-A_j)$$
となる. このとき, $k=1,\dots,N$ を一つ固定した時, $k$ がそれぞれ $i,j$ に何回ずつ登場するかを $I_k,J_k$ で表すとすると, $I_k=k-1, J_k=N-k$ なので, 
$$X=\sum_{k=1}^N (I_k-J_k) A_k=\sum_{k=1}^N (2k-(N+1)) A_k$$
とすることにより, $O(N)$ で計算できた.

##<font color=#00C0C0> E問題 (500pts, diff:1461) </font> [Throne](https://atcoder.jp/contests/abc186/tasks/abc186_e)
玉座を椅子 $0$, 玉座から時計回りに $N-1$ 個の椅子を 椅子 $1, \dots,$ 椅子 $N-1$ と名づける. 高橋くんが行動を $m~(m \geq 0)$ 回終えた後に座っている椅子の番号は $(S+mK) {\rm ~mod~} N$ となる. よって, これはある非負整数 $l$ を用いて, $S+mK=lN$ となる.

ここで, $g=\gcd(N,K)$ として, $S$ が $g$ の倍数でない時, 答えは不可能である.

以下, $S$ は $g$ の倍数であるとする. このとき, $N,K,S$ をすべて $g$ で割り, 特に $N,K$ は互いに素としてもよい.

整数 $x,y$ に関する不定方程式 $xN-yK=S$ について, $N,K$ は互いに素なので, $\alpha N+\beta K=1$ を満たす整数の組 $(x,y)=(\alpha,\beta)$ が存在する. この $\alpha,\beta$ と整数 $p$ を用いて, $m,l$ はそれぞれ
$$l=pK+S \alpha,\quad m=pN-S \beta$$
となる.

ここで, $m,l \geq 0$ であったことに注意すると, $p$ の範囲は
$$ \gamma:=\min \left(\dfrac{-S \alpha}{K},\dfrac{S\beta}{N} \right)$$
としたとき, $\gamma \leq p$ である. $p$ は整数なので, $\lceil \gamma \rceil \leq p$ であり, 求めるべき $m$ の最小値 $m_{{\rm min}}$は,
$$ m_{{\rm min}}=\lceil \gamma \rceil N-S \beta $$
である.

##<font color=#0000FF> F問題 (600pts, diff:1833) </font> [Rook on Grid](https://atcoder.jp/contests/abc186/tasks/abc186_f)
以下, ボードの下と右を1行, 1列ずつ拡張し, $H+1$ 行目と $W+1$ 列目のすべてのマスに障害物があるとする. 数列 $X=(X_i)_{i=1}^{H+1}, Y=(Y_j)\_{j=1}^{W+1}$を以下の様に定義する. ただし, 障害物が存在するマス全体の集合を $\mathcal{M}$ とする.

$$X_i:=\begin{cases} \min \\{1 \leq j \leq W+1| (i,j) \in \mathcal{M} \\}-1& ((i,1) \not \in \mathcal{M}) \\\\ 0 & ((i,1) \in \mathcal{M})\end{cases} \\\\
Y_j:=\begin{cases} \min \\{1 \leq i \leq H+1| (i,j) \in \mathcal{M} \\}-1& ((1,j) \not \in \mathcal{M}) \\\\ 0 & ((1,j) \in \mathcal{M})\end{cases}$$

このとき, $X_i$ はマス $(i,1)$ から下へ1回移動することで到達可能なマスの数を表している. $Y_j$ についても同様である. 次に, $X_{\rm ess}, Y_{\rm ess}$ を
$$X_{\rm ess}:=\min\\{1 \leq i \leq W+1|(i,1) \in \mathcal{M}\\}-1 \\\\
Y_{\rm ess}:=\min\\{1 \leq j \leq H+1|(1,j) \in \mathcal{M}\\}-1$$
とする. このとき, $i=1,\dots,W+1$ に対して以下が成立する.
$$ マス (i,1) に到達可能 \iff  i \leq X_{\rm ess}$$
$Y_{\rm ess}$ についても同様である. このとき, 数列 $Y'=(Y_j')\_{j=1}^{W+1}$ を
$$Y_j':=\begin{cases} Y_j & (j \leq Y_{\rm ess}) \\\\ 0 & (j>Y_{\rm ess})\end{cases}$$
と定義すると, $\alpha:=\sum_{j=1}^{W+1} Y_j'$ は, マス $(1,1)$ から 横→縦 [^1] と移動することによって到達可能なマスの総数である. よって, $\beta$ を 横→縦 [^1] と移動しても到達不能だが, 縦→横 [^1] と移動することによって到達可能なマスの総数として, $\beta$ を求めることができれば, $\alpha+\beta$ が解答になる.

以下の様にして, $\beta$ を求めることができる.

1. 数列 $T=(T_j)\_{j=1}^W$ を $T_j:=[Y_j=0]$ で定める.
2. $i=1,\dots,X_{\rm ess}$ の順に, 以下の行動を行う.
  * $\beta$ に $\sum_{j=1}^{X_i'} T_i$ の値を加える.
  * $Y_j'=i$ を満たす全ての $j$ に対して, $T_j$ を $1$ に変更する.
  * 
この $\beta$ を求める一連の流れは, 2. で区間の和を求めることに注目すると, BIT木 [^2] で高速に処理することができる.

以上から, $\alpha,\beta$ を計算量 $O((H+W) \log W)$ で求めることができた.

[^1]: それぞれの移動で0マスの移動を認める.
[^2]: セグメント木でも良いが, 整数の加法が群を成すので, BIT木のほうがより高速に動く.
#感想
##良かった点
* Beginner Contest において, 時間内に初めて<font color=#0000FF>青色難易度</font>の問題を正解することができた.
* <font color="brown">D問題</font>でソートしてもよいことをすぐに気付けた.

##反省点
* <font color=#00C0C0>E問題</font>は数学問題だったので, もう少し速く解きたかった.
* <font color=#0000FF>F問題</font>で<font color=red>1 PENALTY</font>を出してしまった.