第6回ドワンゴからの挑戦状予選 - 情報妖精の競プロ日記

解けた問題だけ解説をしていきますー

要項

第6回ドワンゴからの挑戦状予選
rated ~2799
2020/1/11(土) 20:00 ～ 22:00 (120分)
200-600(400)-800-800-1100 (5問)
ペナルティ: 5分

方針

Bに関してはどうせ ${\rm O}(N^2)$ を ${\rm O}(N)$ に高速化する何らかの方法が出るとは思うので累積和高速化系か何か……まぁなんであれ数式変形だと思うから、一瞬考えて高速化が思いつかなかったら部分点も検討したいね。
後はCとDをとにかく両方読んで、解けそうな方に全力を使いたいね。
特に構築とかの私が得意な問題なら解きたいところ…….。

A - Falling Asleep

問題文

ニワンゴ君は $N$ 曲からなるプレイリストを作りました。 $i$ 番目の曲はタイトルが $s_i$ で、再生時間が $t_i$ 秒です。ここで、 $s_1,\ldots,s_N$ が相異なることが保証されます。
ニワンゴ君はこのプレイリストを再生しながら、作業をしていました。(すなわち、プレイリストの全曲が順番通りに $1$ 回ずつ、間に休止を挟むことなく再生されました。)しかし、作業中に居眠りをしてしまい、全曲の再生が終わったあとに起きました。記録から、タイトルが $X$ の曲の再生が終わるタイミングでニワンゴ君が寝てしまったことがわかりました。
ニワンゴ君が寝ている間に曲が再生された時間が何秒あったかを求めてください。
制約

$1 \leq N \leq 50$

$s_i,X$ は英小文字のみからなる長さ $1$ 以上 $100$ 以下の文字列

$s_1,\ldots,s_N$ は相異なる

$s_i = X$ なる整数 $i$ が存在する

$1 \leq t_i \leq 1000$

$t_i$ は整数

解法

まず今寝ているかどうかのフラグと寝ている間の再生時間の合計を持つ変数を持ち、最初はそのフラグをfalse、再生時間を0にします。
後は上から順に曲を見ていき、もしフラグがtrueなら再生時間にこの曲の時間 $t_i$ を足し、次にもしも $s_i = X$ ならフラグをtrueにすればいいです。
この順に処理をすることで正しく再生時間を求めることができますね。(逆にすると余計な時間が足されるので注意しましょう。)

感想

ニコニコ動画だなーって感じです。
去年あたりからかなりニコニコ動画の環境は改善されているので、人が戻ってまた盛り上がる環境になってほしいなとは思っています。
youtubeだと、コメントが流れないのが寂しい……。

B - Fusing Slimes

問題文

数直線上に $N$ 匹のスライムが並んでいます。左から $i$ 番目のスライムは位置 $x_i$ にいます。
ここで、 $1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}$ が成立することが保証されます。
ニワンゴ君は操作を $N-1$ 回行います。 $i$ 回目の操作は以下の手順からなります。

$1$ 以上 $N-i$ 以下の整数を等確率で選ぶ(これを $k$ とする)

左から $k$ 番目にいるスライムを右隣にいるスライムの位置まで移動させる

その後、同じ位置にいる $2$ 匹のスライムを合体させ、 $1$ 匹のスライムにする

$N-1$ 回の操作によって、スライムが移動した距離の総和の期待値に $(N-1)!$ をかけた値(これは整数になることが示せます)を $10^{9}+7$ で割ったあまりを求めてください。なお、合体後のスライムが移動した場合は $1$ 体のスライムの移動として数えます。
制約

$2 \leq N \leq 10^{5}$

$1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}$

$x_i$ は整数

解法

まず、スライムは他のスライムの位置まで移動したときに消滅すると言い換えても問題はありません。
次に、スライムの間の区間について着目します。
区間 $L_i$ を $i$ 番目のスライムと $i+1$ 番目のスライムの間の区間としたとき、この区間 $L_i$ を通るスライムの数の期待値が分かれば、移動距離の期待値はその値に区間の長さを掛けたものに等しくなります。
まず、スライム $i$ は必ず区間 $L_i$ を通るので、期待値は $\frac{1}{1}$ です。
次にスライム $i-1$ は自身が最後に移動するときのみ区間 $L_i$ を通るので、期待値は $\frac{1}{2}$ です。
同様に考えると、スライム $j (1 \leq j \leq i)$ 自身が最後に移動するときのみ区間 $L_i$ を通るので、期待値は $\frac{1}{i+1-j}$ です。
よって、区間 $L_i$ を通るスライムの数の期待値は $\sum_{j=1}^{i} \frac{1}{i+1-j}$ であることが分かったので、移動距離の期待値は $\sum_{i=2}^{N} (x_{i}-x_{i-1}) \sum_{j=1}^{i-1} \frac{1}{i-j}$ であることが分かります。
$\frac{1}{1} + \frac{1}{2} + \cdots$ は ${\rm O}(N)$ の前計算をしておけば ${\rm O}(1)$ で求められるので、計算量は ${\rm O}(N)$ です。

感想

癒し枠です。
600点問題なので難しいと思っていたのですが、考察5分、実装5分で終わったので平和で良かったです。

C - Cookie Distribution

問題文

$N$ 人の子供たちがいます。子供たちには $1,2,\ldots,N$ と番号が振られています。これから $K$ 日間、子供たちにクッキーが配られることになりました。 $i$ 日目には $N$ 人の中から $a_i$ 人の子供が等確率で選ばれ、選ばれた子供たちはそれぞれクッキーを $1$ 枚受け取ります。( $K$ 回の子供の選択はすべて独立に行われます。)
$K$ 日間で子供 $i$ が受け取るクッキーの枚数を $c_i$ として、子供たちのうれしさを $c_1 \times c_2 \times \ldots \times c_N$ で定義します。うれしさの期待値に $\binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K}$ をかけた値(これは整数となることが示せます)を $10^9+7$ で割ったあまりを求めてください。
注記
$\binom{n}{k}$ は異なる $n$ 個の対象から $k$ 個を選ぶ選び方の総数を表します。
制約

$1 \leq K \leq 20$

$1 \leq a_i \leq N$

解法

D問題に全力を尽くしたので解いていません。

感想

期待値典型っぽい？なんか改めて書いたところでこれ自明DPじゃんって気持ちになってる

D - Arrangement

問題文

ニワンゴ君は $N$ 枚のカードを持っています。カードには $1,2,\ldots,N$ と番号が振られています。ニワンゴ君はこれらのカードを一列に並べることにしました。
ニワンゴ君は以下の $N$ 個の条件の全てを満たすカードの並べ方が存在するかどうかを知りたいです。ニワンゴ君のためにそのような並べ方が存在するかどうかを判定し、存在する場合は辞書順最小の並べ方を求めてください。

カード $1$ の右隣のカードは(存在するならば) $a_1$ でない

カード $2$ の右隣のカードは(存在するならば) $a_2$ でない

$\vdots$

カード $N$ の右隣のカードは(存在するならば) $a_N$ でない

制約

$2 \leq N \leq 10^{5}$

$1 \leq a_i \leq N$

$a_i \neq i$

解法

現在、まだACできていないため保留です。
この後で解くのでちょっと待っていてください……。
一応説明しておくと、残っているカードが $1$ 枚を除きすべて残っているカードを指している場合、そのカードを取らないと詰みます。
逆にそうでなく、かつ残りが $4$ 枚以上ならば選べる中で最も小さいカードを左に置くのが最適です。
これを繰り返せば残りは $3$ 枚以下になるので、ここから取り方を考えるのはなんとかなるでしょう。
……のはずなのですが、自分の解法だとこの $3$ 枚以下になってからの取り方を間違えてるっぽい……。
全探索が苦手過ぎて辛い。

感想

解きたかった、なんでACできなかったのだろう？

E - Span Covering

問題文

ニワンゴ君は半開区間 $[0,X)$ で表される土地を購入しました。
ニワンゴ君はこの土地に $N$ 枚のシートを敷くことにしました。シートには $1,2, \ldots, N$ と番号が振られており、これらは区別されます。シート $i$ は、 $0 \leq j \leq X - L_i$ を満たす整数 $j$ を選んで $[j, j + L_i)$ を覆うように敷くことができます。
$[0,X)$ にシートに覆われていない座標が存在しないようなシートの敷き方の総数を $10^9+7$ で割ったあまりを求めてください。ただし、 $2$ つの敷き方が異なるとは、整数 $i(1 \leq i \leq N)$ であって、シート $i$ が覆っている領域が異なるものが存在することを指します。
制約

$1 \leq N \leq 100$

$1 \leq L_i \leq X \leq 500$

入力中の値はすべて整数