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

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

転倒数

AtCoder Library Practice Contest L - Lazy Segment Tree

タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値につい…

AtCoder ABC 264 D - "redocta".swap(i,i+1) (茶色, 400 点)

とてもいい感じの BFS の練習問題! 問題へのリンク 問題概要 "atcoder" の並び替えである文字列 が与えられます。 文字列 に対して「隣接する 2 要素を swap する」という操作を繰り返すことで、"atcoder" となるようにしたいとします。 最小何回の操作で実…

Codeforces Round #673 (Div. 1) C. XOR Inverse (R2000)

バチャ中に TLE が取れなかった... で実装してしまっていたけど、 にする必要があったみたい。 問題へのリンク 問題概要 長さ の 0 以上の整数からなる数列 が与えられる。 0 以上の整数 を適切に定めて XOR で定まる数列 の転倒数が最小となるようにせよ。…

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 点)

「 番目の値を求めよ」「メディアンを求めよ」といった問題では、二分探索法が有効なことが多々ありますね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 この数列の連続する区間として考えられるものは 個あります。そのそれぞれの区間について…

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

TL 見て面白そうだったから解いてみた! 問題へのリンク 問題概要 サイズ N の順列が与えられる。これは以下のいずれかによってつくられたものである。 Petr: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap する操作を 3N 回繰り返す Um_nik…

CS Academy 079 DIV2 C K - Inversions

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