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

#総合結果
* [Score] 1500 pts
* [Time] 64:30 + <font color="red"> 05:00 $\times$ 2 </font> = 74:30
* [Ranking] 530 th [Rated内:  336 th]
* [Performance] <font color=#0000ff> 1797　</font>
* [Rating] <font color=#0000FF> 1885 </font> → <font color=#0000FF> 1877 </font> (-8)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:14|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc195/submissions/20870379)||
|<font color=#804000> B問題 </font>|200 pts|19:07|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc195/submissions/20880432)||
|<font color=#808080> C問題 </font>|300 pts|22:00|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc195/submissions/20881499)|[■](https://atcoder.jp/contests/abc195/submissions/20911677)<br>(解説に合わせた実装)|
|<font color=#008000> D問題 </font>|400 pts|33:25|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc195/submissions/20885457)||
|<font color=#0000FF> E問題 </font>|500 pts|<b>64:30</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc195/submissions/20894593)||
|<font color=#C0C000> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc195/submissions/20911143)|
|Total|<b>1500 pts</b>|<b>64:30</b>|<b><font color="red"> 2 Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 5) </font> [Health M Death](https://atcoder.jp/contests/abc195/tasks/abc195_a)

$H$ が $M$ の倍数かどうかを判定すれば良い.

##<font color=#804000> B問題 (200pts, diff: 483) </font> [Many Oranges](https://atcoder.jp/contests/abc195/tasks/abc195_b)

$k$ 個のオレンジを使って実現できる重さの総和は $kA [g]$ 以上 $kB [g]$ 以下である. また, この範囲にある重さは必ず実現可能である. よって, $kA \leq 1000W \leq kB$ を満たす $k$ の最大値と最小値を求めれば良い. ただし, $k$ の自明な下界は $0$, $k$ の自明な上界は $\left \lfloor \dfrac{1000W}{A} \right \rfloor$ であり, $k$ に関する ${\tt for}$ 文や ${\tt while}$ 文で実装できる.

##<font color=#808080> C問題 (300pts, diff: 265) </font> [Comma](https://atcoder.jp/contests/abc195/tasks/abc195_c)

$k$ -桁の整数を表すのに用いられるコンマの数は $\left \lfloor \dfrac{k-1}{3} \right \rfloor$ 個である. また, $k$ 桁の整数は $10^k-10^{k-1}=9 \cdot 10^{k-1}$ 個である. よって, $N$ が $d$ -桁だったとすると, 求めるべき答えは
$$\sum_{k=1}^{d-1} \left(9 \cdot 10^{k-1} \times \left \lfloor \dfrac{k-1}{3} \right \rfloor \right)+(N-10^{d-1}+1) \left \lfloor \dfrac{d-1}{3} \right \rfloor$$
である.

##<font color=#008000> D問題 (400pts, diff: 945) </font> [Shipping Center](https://atcoder.jp/contests/abc195/tasks/abc195_d)

<b>各クエリを独立した問題として考える.</b>

必要ならば, 箱の大きさを昇順に並べて, $X_1 \leq \dots \leq X_r$ としてもよい. このとき, $r$ 個の箱について, $i=1, \dots, N$ の順に, $X_i$ より小さい箱に入っていない荷物(が存在すれば)の中で価値が最大になる荷物を大きさ $X_i$ の箱に入れれば良い事がわかる.

これは, 大きさ $w$ の荷物が大きさ $x$ の箱に入るならば, $x$ よりも大きい箱にも入るということから, 箱が小さいほど制限が厳しく, 大きくなるほどその制限が緩んでいくということになることに起因する.

実装については基本的には1クエリあたり $O(NM)$ で実装できる. 

##<font color=#0000FF> E問題 (500pts, diff: 1609) </font> [Lucky 7 Battle](https://atcoder.jp/contests/abc195/tasks/abc195_e)

$\mathbb{Z}$ -加群 $\mathbb{Z}/7\mathbb{Z}$ の元を $[x]_7$ と書くことにする. また, 文字 $S[i]$ と, $S[i]$ が表す自然数を同一視する. また, ゲームを以下の様に改変する: 最初 $T=[0]_7$ とする. 各ターン $10T$ または $10T+[S[j]]_7$ を選び, それを $T$ として更新する. $N$ ターン終了後, $T=[0]_7$ ならば高橋くんの勝ちであり, $T \neq [0]_7$ ならば青木くんの勝ちである.

ここで, $D_0, \dots, D_N \subset \mathbb{Z}/7 \mathbb{Z}$ を,
$$D_k:=\\{T \in \mathbb{Z}/7 \mathbb{Z}|~ラウンド j 終了時の結果が T ならば高橋くんが勝つ選び方が存在する\\}$$
とする.

まず, $D_N=\\{[0]_7\\}$ である. 次に, $1 \leq j \leq N$ に対して, 

* ラウンド $j$ での行動者が高橋くんであるとき<br>
ラウンド $j-1$ の終了時の結果が $U$ であるとする. このとき, $U \in D_j$ または $10U+[S[j]]_7 \in D_j$ ならば, 高橋くんが勝つ選び方が存在することでがわかる. また, 逆も成立することから,

$$D\_{j-1}=\\{T \in \mathbb{Z}/7 \mathbb{Z}|~10T \in D_j または 10T+[S[j]]\_7 \in D_j \\}$$
である.

* ラウンド $j$ での行動者が青木くんであるとき<br>
ラウンド $j-1$ の終了時の結果が $U$ であるとする. $10U \not \in D_j$ または $10U+[S[j]]\_7 \not \in D_j$ であるとき, 青木くんは $D_j$ から外れる選択をすることによって, 青木くんが勝つことができる. そして, $10U, 10U+[S[j]]\_7 \in D_j$ ならば, どの様に選択しても $D_j$ の元になってしまい, 高橋くんが勝つことになる. よって,
$$D_{j-1}=\\{T \in \mathbb{Z}/7 \mathbb{Z}|~10T \in D_j かつ 10T+[S[j]]_7 \in D_j \\}$$
となる.

このようにして計算した結果, 高橋くんが勝つための必要十分条件は $[0]_7 \in D_0$ である.

##<font color=#C0C000> F問題 (600pts, diff: 2068) </font> [Coprime Present](https://atcoder.jp/contests/abc195/tasks/abc195_f)

この問題を解くに当たって, 以下の性質を用いる.

* $N$ 個の整数 $A_1, \dots, A_N$ が対ごとに素であることの必要十分条件は, 任意の素数 $p$ に対して, $A_1, \dots, A_N$ の中にある $p$ の倍数が1個以下であることである.
* 連続する整数 $k$ 個の整数 $n, n+1, \dots, n+k-1$ にある $a$ の倍数は高々 $\left \lceil \dfrac{k}{a} \right \rceil$ 個である.

この性質から, 求めるべき値は, $B-A+1$ 未満の任意の素数 $p$ に対して, $p$ の倍数が高々1個になるよう部分列の個数である. 

動的計画法で解く. $Q$ を $B-A+1$ 以下の素数全体の集合とし, $1 \leq i \leq B-A+1, S \in \mathcal{P}(Q)$ に対して, ${\rm DP}[i][S]$ を, $A, \dots, A+(i-1)$ の中から選んだ部分列のうち, 以下の2つを共に満たすものの個数とする.

```math
\begin{cases}
\forall p \in Q;~p \in S \Rightarrow 選んだ部分列の中にpの倍数がちょうど1つ存在する.\\\\
\forall p \in Q;~p \not \in S \Rightarrow 選んだ部分列の中にpの倍数が存在しない. \end{cases}
```

集合 $U_x$ を $U_x:=\\{p \in Q|~xはpの倍数\\}$ とし, ${\rm DP}[i][T]$ を考える. まず, $x:=A+(i-1)$ を選ばないときは, $i-1$ 個の場合に帰着できるので, ${\rm DP}[i-1][T]$ だけ寄与する. $A+(i-1)$ を選ぶとする. このとき, $T \supset U_x$ でないと選んだことに矛盾する. そして, $U_x \subset T$ のときは更に ${\rm DP}[i-1][T \setminus U_x]$ だけ寄与する.

以上から,
$${\rm DP}[i][T]={\rm DP}[i-1][T]+\begin{cases} {\rm DP}[i-1][T \setminus U_x] & (U_x \subset T) \\\\
0 & ({\rm otherwise)} \end{cases}$$
である. また, 初期条件は ${\rm DP}[0][T]=[T=\emptyset]$ である.

このようにして求めた配列を用いて, 答えは
$$\sum_{T \subset Q} {\rm DP}[N][T]$$
である.

計算量は $\pi(x)$ で $x$ 以下の素数の個数とし, $\Delta:=B-A+1$ とすることで, $O(\Delta 2^{\pi(\Delta-1)})$ で求めることができる.ここで, 今回の制約から, $\Delta \leq 73$ となり, $\pi(72)=20$ であることから, 十分間に合う.

#感想

##総評
(後日加筆予定)

##反省点
* <font color=#804000> B問題 </font>, <font color=#808080> C問題 </font> が遅すぎるし, Penalty を発生させている.

* <font color=#ff0000> Penalties </font>の理由
 * <font color=#804000> B問題 </font>: 自明な上界の誤り
 * <font color=#808080> C問題 </font>: $d$ -桁のコンマの個数を $\left \lfloor \dfrac{d}{3} \right \rfloor$ にしていた.