cplusplusonly's memo

Atcoder: https://atcoder.jp/users/cplusplusonly

第6回ドワンゴからの挑戦状予選参戦記

プログラミング競技プログラミング

AtCoder の第6回ドワンゴからの挑戦状予選

に参加しました。

結果は 70 分でAB が解けて 360 位パフォーマンス 1883 でした。600 取れたからいいようなものの 200 - 600 - 800 - 800 は辛かった...

f:id:y_r:20200112144853p:plain

感想

A 問題

文字列とマッチさせてそれ以降の数値を足すだけ。

B 問題

$期待値 * 発生数$ が回答なので、全通りの移動量を回答すればよい。
位置の差分を $d_i (0 <= i < N)$ とし、 $d_i$ を通る全スライム数を $C_i$ とすると回答は $\Sigma(d_i * C_i)$
の数え方だが
- ひとつ左のスライムが通る回数は全通りなので $(N-1)!$
- ふたつ左が通る回数 + ... を足し込めばいいがよくわからん
- しかたないので実験してみると個左のスライムが通る回数は
  - $N=4$ : $6, 3, 2$
  - $N=5$ : $24, 12, 8, 6$
  - $N=6$ : $120, 60, 40, 30, 24$
- 上記をにらんでると位置 $k$ に対して $\sum^{k}_{l=1}(((N-1)!)/l)$ が見える

で AC。あとから考えてみると以下がなりたっている。

とあるスライムが 2 個以上右に移動するのは右隣のスライムの後に選ばれた場合でこれは確率
- 他のスライムとは関係なく問題のスライム間の順序なので、2 個のスライムのうち特定のスライムが後に選ばれる確率となる
同様に $k$ 個以上右に移動するのは右隣 $k-1$ 個のスライムのなかで一番後に選ばれた場合で確率 $1/k$

C 問題

見たけどわかりません。

D 問題

なんか貪欲が見えるけど、構築する手順が見えなかった。
なお、終了直後に投げた深さ探索回答は無事 TLE だった模様...