たれながし

色々雑多に書きます

緑diff精進その1 (1/23)

近況報告

レート4桁になった。 atcoder.jp

ところで最近悲しいくらい精進できていない。就活や研究が若干忙しいせいもあるが、普通に怠惰。

AtcoderProblems Heatmap

ということで水コーダー目指してAtCoder ProblemsのRecommendation (Moderate)を埋めていく日記をつけていくことにする。

あくまで日記なので、解説ではないことに注意してほしい。

あと大嘘担当大臣していたらひっそりと教えてください。

本編 (解いた問題)

ABC253 E - Distance Sequence
ABC140 D - Face Produces Unhappiness
ABC223 D - Restricted Permutation

ABC253 E - Distance Sequence

感想 (解答中に考えたこと)

$i$ 番目の要素が決まれば $i+1$ 番目の要素の候補がわかるので、DPで解けそう (制約的にもDPっぽい)
$i$ 番目の要素は必ず保持しなければならないので、 $dp(i, m):= i番目の要素の大きさがmであるような数列の数$
遷移を考える。 $i$ 番目の要素が $m$ である時、 $i-1$ 番目の要素は $m-K$ 以下か $m+K$ 以上であるので
- $dp(i, m)=\sum_{j=1}^{m-K}dp(i-1, j) + \sum_{j=m+K}^{M}dp(i-1,j)$
1番目の要素は何を選んでも良いので、 $dp(0, m)=1$
計算量が $O(NM^2)$ だが、累積和で $O(NM)$ で解ける
実装するもバグる。ランダムテスト(N, M, K) = (2, 2, 0)の場合に答えがズレている
3.の式で $K=0$ のとき、 $dp(i-1, m)$ を2回計上しているので、上記の式のままだと面倒な分岐が必要そう
差を取る方針に変更する
- $dp(i, m)=\sum_{j=1}^{M}dp(i-1, j) - \sum_{j=m-K+1}^{m+K-1}dp(i-1,j)$

提出コード

ABC140 D - Face Produces Unhappiness

感想 (解答中に考えたこと)

ランレングス圧縮っぽい。とりあえず幸福な人数はsum(c-1 for _, c in T)であることはわかる。
- ランレングス圧縮後の文字列を $T=L_{a}R_{b}L_{c}R_{d}...$ とした。
操作前後の評価を慎重に確認してみる。どんなに最適なムーブをしても最大で2ずつしか増えない。
について、といった取り方や端を選択してしまうと嬉しくない。
- というよりも、 $L$ や $R$ の単一のまとまりかつ端でないような取り方をするのが一番嬉しいムーブになる。
つまりで先頭から順に見た時、末尾でなく先頭の文字と異なる文字が現れる回数が以下であれば、そうでなければ全て同じ方向を向けるのでになる
- 前半の条件がわかりにくい。 $T = L_{2}R_{3}L_{1}R_{5}L_{3}R_{1}$ である場合、先頭の文字が $L$ なので、異なる文字は3回( $R_{3}, R_{5}, R_{1}$ )現れ、うち $R_{1}$ は末尾なので、末尾でなく先頭の文字と異なる文字が現れる回数は2回と言える。

提出コード

ABC223 D - Restricted Permutation

感想 (解答中に考えたこと)

トポロジカルソートっぽい雰囲気。入次数が0の頂点のうち小さい順に要素を選べば良さそう。
priority_queueでも実装可能っぽいけど、MultiSet(SortedSet 厳密には違うもののはず?)の練習がてら後者で実装する。
SortedSetの中身がなくなるまで最小の要素をappendする。appendした頂点は食べたものとして扱えば、いずれ入次数が0になる頂点が現れるので、その都度SortedSetにaddしていく。
SortedSet遅いんですが…… SortedListに変更して、HashSetで数字を利用したかを管理する。

提出コード