AtCoder Regular Contest 117のきろく - Flkanjin’s 競プロ録

A - God Sequence (200点)
B - ARC Wrecker (400点)
C - Tricolor Pyramid (600点)
D - Miracle Tree (600点): 未提出
E - Zero-Sum Ranges 2 (900点、実行時間制限: 5 sec): 未提出
F - Gateau (900点、実行時間制限: 3 sec): 未提出
結果、感想

A - God Sequence (200点)

$A = B$ のとき $E_i = i\hspace{0.5cm} (1 \leq i \leq A),$ $E_{A+i} = -i\hspace{0.5cm} (1 \leq i \leq B)$ とすれば条件を満たします。
$A \gt B$ のとき $E_i = i\hspace{0.5cm} (1 \leq i \leq A),$ $E_{A+i} = -i\hspace{0.5cm} (1 \leq i \leq B-1),$ $\displaystyle E_{A+B} = -\sum_{i = B}^{A}i = -\frac{A(A+1) - B(B-1)}{2}$ とすれば条件を満たします。
$A \lt B$ のとき正負の役割を入れ換え、 $E_i = i\hspace{0.5cm} (1 \leq i \leq B),$ $E_{B+i} = -i\hspace{0.5cm} (1 \leq i \leq A-1),$ $\displaystyle E_{A+B} = \sum_{i = A}^{B}i = \frac{B(B+1) - A(A-1)}{2}$ とすれば条件を満たします。

B - ARC Wrecker (400点)

建物を並び替えても状況を変わらず、両者での景観は一対一対応するため、 $A$ をソートし、 $A_0 = 0$ を追加したものを考えます。
隣り合う建物の高さについて、その差が大きくなることはなく、他の建物とは独立にその間の値を全てとることができます。そのため答えは $\displaystyle \prod_{i=1}^{N} (A_i - A_{i-1} + 1)$ となります。

C - Tricolor Pyramid (600点)

青、白、赤の色を数 $0,\,1,\,2$ と対応させ、 $a_{i,j}$ を下から $i$ 段目の左から $j$ 番目のブロックの色に対応する数とします。
このとき $9$ 通りのパターンを全て試すことで $a_{i+1,j} = -(a_{i,j} + a_{i,j+1}) \bmod{3}$ が成り立つことが分かります。これは二項係数の漸化式によく似た式で、実際の所 $a_{i,j} = \displaystyle \left( (-1)^{i-1}\sum_{k = j}^{j + i -1} {}_{i-1}\mathrm{C}_{k-1}\, a_{1,k}\right) \bmod{3}$ となるため、 $a_{N,1} = \displaystyle \left( (-1)^{N-1}\sum_{k = 1}^{N} {}_{N-1}\mathrm{C}_{k-1}\, a_{1,k}\right) \bmod{3}$ となり、これを対応する色にすれば答えですが、各 ${}_{n}\mathrm{C}_{r}$ を $\bmod{3}$ で求める場合、いつものように逆元を用いる方法では $r \geq 3$ のとき常に $0$ となってしまい、WAとなってしまいます。そこで蟻本の262, 263ページに記載されている方法で求めることになります。