鹿島建設プログラミングコンテスト2020 (AtCoder Regular Contest 110) 感想

##総合結果
* [Score] 1800 pts
* [Time] 98:10+<font color=#FF0000>05:00$\times$1</font>=103:10
* [Ranking] 250 th
* [Performance] <font color=#C0C000>2150</font>
* [Rating] <font color=#0000FF>1633</font>→<font color=#0000FF>1698</font> (+65)

##各問題ごとの詳細
* <font color=#808080> A問題 </font> 02:42
* <font color=#804000> B問題 </font> 20:36 <font color="red"> (+1 PENALTY) </font>
* <font color=#008000> C問題 </font> 52:45
* <font color=#C0C000> D問題 </font> 98:10
* <font color=#FF0000> E問題 </font> --:--
* <font color=#FF8000> F問題 </font> --:--

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff:120) </font> [Redundant Redundancy](https://atcoder.jp/contests/arc110/tasks/arc110_a)
$L:={\rm lcm} (2, \dots, N)$ に対して, $X:=L+1$ とすると, $a=2, \dots, N$ に対して, $L$ は $a$ の倍数なので. $X \mod a=1$ である. また,
$$
{\rm lcm} (2) \leq {\rm lcm} (2,3) \leq \dots \leq {\rm lcm}(2, \dots, N) \leq \dots \leq {\rm lcm} (2,\dots,30)=2329089562800 <10^{13}
$$
より, $X+1 \leq 10^{13}$ である. なお, $N$ の値に関係なく, $2329089562801$ と出力しても <font color="green">AC</font>となる.

##<font color=#804000> B問題 (400pts, diff:655) </font> [Many 110](https://atcoder.jp/contests/arc110/tasks/arc110_b)
$X=10^{10}$ とする.
* $T=1$ のとき, 答えは $2X$
* $T=11$ のとき, 答えは $X$
* それ以外のとき, $i_0,\dots,i_M$ を $T[i_k]=0$ であり, $i_0 < i_1 < \dots < i_M$ となるものとし, $(T にある 0 の個数)=M+1$ とする. このとき, 以下を全て満たさないとき, 答えは $0$
$$ 1 \leq i_0 \leq 3,\quad i_k=3k+i_0,\quad {\rm len} (T)-2 \leq i_M \leq {\rm len} (T) $$
上を共に満たすとき,
$$\begin{cases} X-M & (T~[{\rm len} (T)]=0) \\\\
X-M-1 & (T~[{\rm len} (T)]=1) \end{cases}$$

##<font color=#008000> C問題 (500pts, diff:1100) </font> [Exoswap](https://atcoder.jp/contests/arc110/tasks/arc110_c)
以下,[$P_k,P_{k+1}$を入れ替える]という操作を $T_k$ と書く.
それぞれの場所での入れ替えは1回だけしかできないので, まずは $1$ を1番左に移動させることを考える. 初期状態で $P_m=1$ だったとすると, 行なわくては行けない操作は $T_{m-1}, \dots, T_1$ である. この操作の後, $P_2=2,\dots,P_m=m$ でなかった場合, 答えは即座に "No" になる.
このとき, $P$ は $1, \dots, m, P_{m+1}, \dots, P_N$ になるので, $P_{m+1}, \dots, P_N$ に対して上と同様に繰り返していけばよい.
なお, 上での考え方により $P=(1,\dots,N)$ にできたとしても, 操作の回数がちょうど $N-1$ 回でなければ答えは "No" になることがこの構成法からわかる.

##<font color=#C0C000> D問題 (600pts, diff:2078) </font> [Binomial Coefficient is Fun](https://atcoder.jp/contests/arc110/tasks/arc110_d)
形式的ベキ級数で考える. $i=1,\dots,N$ に対して,
$$ P_i(X):=\sum_{B_i=0}^\infty \dbinom{B_i}{A_i} X^{B_i}$$
とする. このとき,
$$ P_i(X)=\dfrac{X^{A_i}}{(1-X)^{A_i+1}}$$
となる. よって, $\alpha:=\sum_{i=1}^n A_i$ とすると,
$$ \prod_{i=1}^N  P_i(X)=\dfrac{X^{\alpha}}{(1-X)^{\alpha+N}}$$
となる. 上の形式的ベキ級数を $Q$ とすると, $\left[X^M \right] Q$ は $\beta:=\sum_{i=1}^N B_i=M$ のときの答えである. 今欲しいのは, $\beta=0,1,\dots,M$ のときの答えの総和なので, 形式的ベキ級数 $R$ を
$$\left[X^k \right] R=\left[X^0 \right]Q+\dots+\left[X^k \right]Q$$
となるようなベキ級数と定めると,

```math
\begin{align}
R&=\sum_{k=0}^\infty (\left[X^k \right] R)X^k \\
&=\sum_{k=0}^\infty (\left[X^0 \right] Q+\dots+\left[X^k \right]Q)X^k \\
&=\left(\sum_{k=0}^\infty \left(\left[X^k \right] Q \right) X^k \right) \left(\sum_{l=0}^\infty X^l \right) \\
&=\dfrac{Q}{1-X} \\
&=\dfrac{X^{\alpha}}{(1-X)^{\alpha+N+1}} \\
&=X^\alpha \sum_{k=0}^\infty \dbinom{k+\alpha+N}{\alpha+N} X^k \\
&=\sum_{k=0}^\infty \dbinom{k+\alpha+N}{\alpha+N} X^{k+\alpha}
\end{align}
```
より, 答えは
$$\left[X^M \right]R=\dbinom{M+N}{\alpha+N}$$
である.

##<font color=#FF0000> E問題 (800pts, diff:2973)</font> [Shorten ABC](https://atcoder.jp/contests/arc110/tasks/arc110_e)
(未着手)

##<font color=#FF8000> F問題 (900pts, diff:2719)</font> [Esoswap](https://atcoder.jp/contests/arc110/tasks/arc110_f)
(未着手)

#感想
##良かった点
* <font color=#008000> C問題 </font> で正しく操作を構成できた.

##反省点
* <font color=#C0C000> D問題 </font> でMathematicaを使ってしまった.