けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

転倒数

ACL Beginner Contest D - Flat Subsequence (水色, 400 点)

LIS を求める in-place DP を応用すればできる! でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった! in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク 問題概…

ACL Contest 1 E - Shuffle Window (橙色, 900 点)

コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…

AtCoder ARC 075 E - Meaningful Mean (青色, 600 点)

じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…

Codeforces Round #598 (Div. 3) F. Equalizing Two Strings (R2200)

誤読したーーーーーー操作は 1 回しか行えないものと思って悩んでた 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を好きな回数だけ行うことで、 と とが一致する状態にすることが可能かどうかを判定せよ。 1 以上 以下の整数 を定める …

Codeforces Round #609 (Div. 1) C. K Integers (R2300)

とてもこどふぉっぽい問題だと思った!!!こういうのを得意になるぞー!!! 問題へのリンク 問題概要 の順列が与えられる。各 に対して、以下の問いに答えよ。 順列の隣り合う 2 要素を swap して、順列のどこかの場所で がこの順に連続で並んでいる状態に…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip (青色, 700 点)

隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる!!! drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…

AtCoder ABC 107 D - Median of Medians (ARC 101 D) (黄色, 700 点)

今更前々回の ARC を見て、噂の 700-D Median of Medians を見てみたけど、これはJOI 2017 予選 F - L番目のK番目の数https://t.co/EEfPlJ18Tkとほぼ同じ問題な気がしたん。— けんちょん ( ´ ꒳ `) (@drken1215) 2018年9月6日 とは言え、完全に一緒ではなく…

Codeforces #485 (Div. 1) B. Petr and Permutations (R1800)

TL 見て面白そうだったから解いてみたのん Codeforces 486 DIV1 B Petr and Permutations 問題概要 サイズ N の順列が与えられる。これは以下のいずれかによってつくられたものである。 Petr: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap …

CS Academy 079 DIV2 C K - Inversions

CSA 079 DIV2 C K Inversions 問題概要 1 ~ N の順列で転倒数が K となるもののうち、辞書順最小のものを求めよ。 2 <= N <= 105 0 <= K <= NC2 やったこと 辞書順最小ということで、とにかく今見ている部分を極力小さくする Greedy を行う。 具体的には、…