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

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

操作:swap

AtCoder ARC 171 C - Swap on Tree (黄色, 600 点)

備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …

AtCoder ARC 167 D - Good Permutation (黄色, 700 点)

モノグサでバチャやって、なんとか通した! 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…

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

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

DISCO presents 2016 予選 D - DDPC特別ビュッフェ (赤色)

久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…

AtCoder ABC 250 C - Adjacent Swaps (茶色, 300 点)

実はアルゴ式でもよく似た問題をすでに出していました! algo-method.com 問題へのリンク 問題概要 がこの順に並んでいます。この数列に対して 回のクエリが投げられました。 各クエリでは、値 が指定されて、次の操作を実行します。 数列中の整数 に対し、…

Codeforces Global Round 12 C2. Errich-Tac-Toe (R2300)

これ好き! 問題へのリンク 問題概要 のグリッドがあって、"." と "O" と "X" のいずれかが描かれている。"O" または "X" の描かれているマス目の個数を とする。 今、いくつかのマスに対して、"O" または "X" のマス目の "OX" を入れ替える操作を行う。それ…

AtCoder ARC 110 F - Esoswap (橙色, 900 点)

コンテスト後に AC して、解けた気持ちになっていたけど、その解法は嘘だった 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を最大 200000 回まで繰り返すことでソートされた状態にせよ。 のいずれかを選んで と を swap する 不可能である場合…

AtCoder ARC 110 C - Exoswap (緑色, 500 点)

「転倒数 = N-1 で Yes とする」という嘘解法が大量に通ったらしい 問題へのリンク 問題概要 の順列 が与えられる。 と を swap する と を swap する ... と を swap する という 種類の操作を、それぞれちょうど 1 回ずつ行う必要がある。その結果がソート…

AtCoder AGC 048 A - atcoder < S (緑色, 300 点)

単純な探索でも解けるし、考察で計算量を減らすこともできそう。 問題へのリンク 問題概要 文字列 が与えられる。文字列 に以下の操作を最小回数行うことで、辞書順で > "atcoder" となるようにせよ。 中の連続する 2 文字を swap する (このテストケースが …

AtCoder ARC 107 C - Shuffle Permutation (水色, 500 点)

面白かった 問題へのリンク 問題概要 の行列 と、整数 が与えられる。この行列は、 をちょうど一つずつ要素に含む。 sigma くんは、以下の 2 種類の操作を、好きな順序で 好きな回数 行えます。 全ての について を満たす を選び、行列の 列目をswapする 全…

Codeforces Round #625 (Div. 1) D. Reachable Strings (R2500)

まさか残り 25 分で通し切れるとは思わなかった! 問題へのリンク 問題概要 長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ 各クエリは left, right, len からなる 部分文字列 A = S[left : left + len], B = S[right: rig…

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

AtCoder AGC 006 C - Rabbit Exercise (赤色, 800 点)

操作を 回行った結果を求める系、苦手意識あるけど克服したい! 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…

AOJ 2581 完全順列 / Derangement (RUPC 2014 day3-G)

今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…

Codeforces Round #617 (Div. 3) E2. String Coloring (hard version) (R2000)

これと同じでは!? atcoder.jp 問題へのリンク 問題概要 長さ の文字列 が与えられる。 いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートさ…

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 AGC 003 C - BBuBBBlesort! (水色, 600 点)

楽しかった 問題へのリンク 問題概要 長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し 隣り合う 2 要素を swap する 連続する 3 要素を反転する という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。…

AtCoder ABC 122 D - We Like AGC (水色, 400 点)

こういうの素早く書けるようになるにはどうしたらいいんだろう... 問題へのリンク 問題概要 'A', 'G', 'C', 'T' のみからなる長さ の文字列のうち、「どの隣接した 2 文字を swap しても "AGC" を連続部分列として含まないもの」が何通りあるか求めよ。 制約…

Tenka1 2019 C - Stones (緑色, 300 点)

これをもっと早く 問題へのリンク 問題概要 長さ の白黒列が与えられる。 最小個数のマスの白と黒を入れ替えることで、「黒」と「白」とが連続している箇所がないようせによ。 制約 考えたこと つまりは「白白白白黒黒黒黒黒」のように 左 left 個が白 右 N …

AtCoder AGC 001 F - Wide Swap (2000 点)

これも自力で解けたの、嬉しい!!!!! 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…

AOJ 2942 Absum (RUPC 2019 day1-F)

難しくて、てんぷらたんが天才だった!!!!!!! とにかくすごかった!!!!! そしてすごく面白い問題だった!!!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。数列の 2 要素を選んで swap する操作を高々 回まで行うことができる。 操作…

JOI 本選 2019 C - たのしいたのしいたのしい家庭菜園 (AOJ 0660, 難易度 9)

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない…

AtCoder AGC 029 A - Irreversible operation (茶色, 300 点)

一瞬罠があるのではと怖くなるやつ 問題へのリンク 問題概要 'W' と 'B' で構成された文字列が与えられる。 "BW" を "WB" に置き換える変換を好きな回数行える。最大回数を求めよ。 考えたこと 問題の操作はつまりは 'W' を左に動かす操作と読み替えられる。…

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) C. Equalize (R1300)

超苦手系。なんとか解けた。 問題へのリンク 問題概要 長さ N のバイナリ列 a, b が与えられる。a に対して 隣接二項を swap する 0 と 1 を反転する の操作を最小回数行って b にせよ。(10 -> 01 なら 1、1000 -> 0001 なら 2) 制約 1 <= N ,= 106 考えたこ…

AtCoder ARC 102 F - Revenge of BBuBBBlesort! (銅色, 1200 点)

メッチャ楽しい問題!!! 問題へのリンク 問題概要 (ARC 102 F) 1 〜 N の順列が与えられる。 連続する三要素が単調減少のとき、それをひっくり返す という操作を好きなだけ行って、恒等順列にできるかどうか判定せよ。 制約 1 <= N <= 3 × 105 解法 (全然…

AtCoder ARC 097 E - Sorted and Sorted (黄色, 600 点)

600 にしちゃムズイ。 ARC 097 E Sorted and Sorted 問題概要 (白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートさ…

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

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

TopCoder SRM 402 DIV1 Easy - RandomSort (本番 334 人)

現代の ABC-E にも出そうな DP 問題へのリンク editorials 問題概要 の順列 が与えられる。この順列に対して、以下の操作を繰り返していく かつ であるような を一様ランダムに選び、 と を swap する ソートされた状態になるまでの回数の期待値を求めよ。 …