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

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

操作:circular_shift

OMC 165 F 問題を、競プロする!

OMC 165 F 問題 が面白かったので、競プロの問題として解いてみることにしました! OMC で出題された原作は、下の問題概要において、 の場合の答えを手計算で求めるというものでした。 問題概要 のグリッドの各マスを白色と黒色に塗り分ける方法のうち、次の…

AtCoder ABC 235 D - Multiply and Rotate (緑色, 400 点)

最小回数を求めるには BFS!!(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…

AtCoder ABC 286 C - Rotate and Palindrome (茶色, 300 点)

慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…

AtCoder AGC 046 C - Shift (黄色, 800 点)

こういう問題めっちゃ好き!!! 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…

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

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

CODE FESTIVAL 2016 qual A E - LRU パズル / LRU Puzzle (橙色, 1200 点)

D 問題はコーナーケースゲーかと思ったらそうでもなかった。むしろこっちの方が苦しかった。 問題へのリンク 問題概要 要素からなる配列が 個あって、それぞれ最初は で初期化されている。以下の操作を 回終えた段階で、 個の配列が等しい状態とすることが可…

Codeforces Round #615 (Div. 3) E. Obtain a Permutation (R1900)

こういうのをちゃんと解けるようになったのは成長! 問題へのリンク 問題概要 (意訳) 以下の 個のクエリに答えよ。 番目のクエリでは、数列 が与えられる。この数列に以下のいずれかの操作をほどこして、 となるようにしたい。その最小回数を求めよ。 を任意…

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…

Codeforces Round #584 (Div. 1 + Div. 2) E. Rotate Columns (R2400)

すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…

AtCoder AGC 032 D - Rotation Sort (橙色, 1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

AtCoder ABC 006 D - トランプ挿入ソート (試験管青色)

順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…

AtCoder ARC 064 F - Rotated Palindromes (赤色, 1000 点)

約数系包除。かなり教育的要素の多い問題だと思った!!!!! 操作によって何通りできるのかを問う問題の取り組み方 約数系包除の考え方 問題へのリンク 問題概要 以上 以下の整数からなる数列のうち、以下のようにしてつくられるものは何通りあるか、10000…