AtCoder Regular Contest 096
Updated:
Source codes
Solutions
C - Half and Half
まず $A + B \leq 2C$ の場合は、素直に $A$ のピザと $B$ のピザを買うべきである。そうでない場合はまず片方または両方のピザが足りるまで AB ピザの方を買うべきである。次に $A > 2C$ の場合は A ピザを買うより AB ピザを 2 枚買って B ピザ分を捨てるべきである。さらに $B > 2C$ の場合は B ピザを買うより AB ピザを 2 枚買って A ピザ分を捨てるべきである。
ポイント
眠くて頭働いてなかったけど無事クリアできた。万全の体調だとここはもう少し早く切り抜けられたと思う。
D - Static Sushi
貪欲法。丁寧に全探索する。まず「最初に進む方向」は時計回りとして良い。反時計回りの場合は $x[i] \gets C - x[i]$ とし reverse することであとで同じメソッドを走らせれば良いからだ。ここでありえる行動は次の 2 パターンである：
- ある $0 \leq i < N$ があって、 $x[i]$ まで行き $v[0] + v[1] + \dots + v[i]$ カロリーを摂取して退店する。
- ある $0 \leq i < j < N$ があって、 $x[i]$ まで行き $v[0] + v[1] + \dots + v[i]$ カロリーを摂取して、反時計回りに戻って来て、原点から $x[j]$ まで反時計回りに行きさらに $v[N-1] + v[N-2] + \dots + v[j]$ カロリーを摂取して退店する。
このうち 1. は簡単な累積和で $O(N)$ で処理できる。 2. の場合は、まず $i$ を決めると $v[0] + v[1] + \dots + v[i] - 2x[i]$ にさらに $\max_{i < j < N} ( (\sum_{k = j}^{N-1} v[k]) - (C - x[j]))$ を足したのが答えである。前者と後者はそれぞれ $i$ を更新するごとに $O(1)$ で更新できる。
ポイント
実は丁寧にやるだけであることを割と短時間で見抜けた。円形なので実装怪しいかと思っていたが、そうでもなかった。ゆっくりコーディングして一発で通ったのは幸運だった。
E - Everything on It
やったこと
全部の注文の仕方は $2^{2^N}$ 通りである。「 $N$ 種類のトッピングそれぞれが、注文したラーメンのうち $1$ 杯以上に乗っている」の場合は包除原理で、 \[ \sum_{I \subset N} (-1)^{\lvert I \rvert} 2^{2^{N - \lvert I \rvert}} = \sum_{i = 0}^N (-1)^i \begin{pmatrix} N \\ i \end{pmatrix} 2^{2^{N-i}} \] と求まる。ところが $2$ 杯以上だとどうするべきなのか全くわからず。
包除原理を適用するところまで
解説放送を見て理解した。 $0$-indexed とする。いつもの通り $N \in \mathbb{N}$ は $N = { 0, \dots, N-1 }$ と表記する。求めるものを $X$ とすると、
\[
\begin{align}
X &= \sum_{i \subset N} (-1)^{\lvert i \rvert} g(i) \
&= \sum_{k = 0}^{N} (-1)^{k} \begin{pmatrix} N \\ k \end{pmatrix} f(k)
\end{align}
\]
である。ここで、
$g(i) = $ 「集合 $i$ に含まれるトッピングがのっているラーメンは $1$ 杯以下である」というラーメンの注文の仕方の場合の数
$f(k) = $ 「トッピング $[0, k)$ がのっているラーメンは $1$ 杯以下である」というラーメンの注文の仕方の場合の数
と定めた。以下 $f(k)$ を求める。
トッピングを制約ある/なしに分けて数える
$A = [0, k)$ とし、 $B = [k, N)$ とする。条件を充たすトッピング $K$ は、つまるところ $K \subset \mathcal{P}(N)$ であるが、 $K$ を次の 2 つの disjoint な和集合に分割する。
$K_1 = \{ Z \in K \mid Z \subset B \}$. (もちろん $\emptyset \in K$ ならば $\emptyset \in K_1$ である)
$K_2 = K \setminus K_1$.
$K$ の選び方は、 $K_1$ の選び方と $K_2$ の選び方の積である。 $K_1, K_2$ はお互いになんの関係もなしに選べることに注意されたい。このうち $K_1$ の選び方は簡単である。何の制約もないのだから、 $2^{2^{N-k}}$ 通りである。一方で $K_2$ の選び方は $\sum_{x = 0}^{k} DP[k][x] \times (2^{N-k})^x$ 通りである。ここで、
$DP[k][x] = $ 集合 $S_{k, x}$ の元の個数
とし、$0 \leq x \leq k$ に対し、集合 $S_{k, x}$ は以下を充たす $T \subset \mathcal{P}(k)$ の全体とする。
- $T$ の元の個数は $x$ である。
- $\emptyset \not\in T$.
- $T$ は disjoint である。
この漸化式はあとで定めることにする1。これはつまり何をやっているのかというと、 $x = \sharp K_2$ とし、 $Z \in K_2$ に対し、 $Z’ = Z \cap A$ を先に考え(この選び方の総数が $DP[k][x]$ 通り)、それらに対して $Z \setminus Z’ \subset B$ をあとで適当に割り当てている( $x$ 個それぞれに $2^{N-k}$ 通り自由に割り当てられてる)。 $A$ の集合というのは $0$ 個または $1$ 個のトッピングしかしてはならないので、それが disjoint の条件になっているという理屈である。
まとめると以下のようになる。
\[ f(k) = 2^{2^{N-k}} \sum_{x = 0}^{k} DP[k][x] \cdot 2^{x(N-k)}. \]
漸化式を求める
ここから先は $n$ と $k$ の記号を別のものにする。 $0 \leq k \leq n$ とする。注釈ですでに指摘したが、 $DP[n][k]$ は第 2 種スターリング数に近い性質を持つものであり、この漸化式の立て方がほとんどそのまま使用できる。
$T \in S_{n, k}$ において、 $n - 1 \in T$ はどのように取り扱われているかで場合分けをしよう。
- $A = \{ n - 1 \} \in T$ である。この場合は、 $T \setminus \{ A \} \in S_{n-1, k-1}$ であるから $DP[n-1][k-1]$ 通りである。
- ある $A \in T$ が存在し、 $n - 1 \in A$ だが、 $\{ n - 1 \} \neq A$ である。この場合は $(T \setminus \{ A \}) \cup \{ A \setminus \{ n - 1 \} } \in S_{n-1, k}$ である。この $A$ の選び方に $k$ 通りの自由度があるので、 $DP[n-1][k] \times k$ 通りである。
- $n - 1 \in A$ となる $A \in T$ は存在しない。この場合は $T \in S_{n-1, k}$ であるから $DP[n-1][k]$ 通りである。
以上のうち 2. と 3. は $n = k$ の時は生じないことに注意されたい。また、 $\emptyset \in S_{n, 0}$ であることに注意されたい。したがって以下の漸化式が定まる。
\[
DP[n][k] =
\begin{cases}
DP[n-1][k-1] & (k = n), \
DP[n-1][k-1] + (k + 1)DP[n-1][k] & (1 \leq k \leq n-1), \
1 & (k = 0).
\end{cases}
\]
あとは実装するだけである。時間制限に余裕があるので、漸化式はメモ化で書いてしまって問題ない。
実装上のポイント
私が間違えた箇所は 2 箇所ある。どちらも私にとっては新規性のある間違いだったので書いておきたい。
最初の間違えは簡単で、 組み合わせ数の下準備をする前に MOD を受け取る 必要があった。つまり、以下の順で書く必要がある。
cin >> N >> MOD;
init();
次の間違い方は気づきにくいものである。 $2^{2^{N-k}}$ の実装である。 power の引数に power を書いてはならない 。すなわち、
ll ans = power(2, power(2, N - k));
とすると間違いである。というのも $N - k \leq 3000$ であるから、外側の power の第 2 引数はすでに MOD で剰余が取られた状態で入っている。つまり、
else if (n % 2 == 1)
{
return (x * power(x, n - 1)) % MOD;
}
else
{
long long half = power(x, n / 2);
return (half * half) % MOD;
}
のように引き算や割り算をするところで正しい計算ができていない。正しい実装は、
long long power_2_power(ll n)
{
if (n == 0)
{
return 2 % MOD;
}
ll half = power_2_power(n - 1);
return (half * half) % MOD;
}
のように $2^{2^n}$ を与える関数を改めて定義することである。
ポイント
第 2 種スターリング数の求め方を知らないと観賞用の問題であることは否めない。 $Z’ = Z \cap A$ を数えましょうという着想がまず出てこないとどうしようもない。
「 $0$ 個または $1$ 個しか選べない」を「 disjoint な和集合」という風に言い換えるのがポイントである。これは覚えていないとできない気がする。
F - Sweet Alchemy
ポイント
Others
順位表を見ていて「あー今回のは難しかったんだろうなー」と思いながら何にも思いつかなかった。これは自分で考えても思いつきそうにないので、解説放送をあとで見る。気になって仕方ないけど、睡眠薬を飲んで寝るんだよ。
-
上記の 1. - 3. の条件に「$T$ は $k$ の被覆である」を加えた場合、 $DP[k][x]$ は第 2 種スターリング数と一致する。 ↩