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

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

K回操作後の結果を求める

ACL Contest 1 E - Shuffle Window (900 点)

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

AtCoder ABC 179 E - Sequence Sum (500 点)

この手の 周期性を利用する ダブリングする のどちらでも解けるタイプの問題、最近めっちゃ多いね。 問題へのリンク 問題概要 を で割ったあまりを で表す。 整数 が与えられる。以下で定まる漸化式の最初の 項の総和を求めよ。 制約 考えたこと 最初誤読し…

AtCoder ABC 175 D - Moving Piece (400 点)

異様に難しかった!! 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…

AtCoder ABC 167 D - Teleporter (400 点)

回操作した後の結果を求めよ (ただし がめちゃくちゃ大きい) という問題は、 同じ処理の繰り返しとなっているところを見抜く ダブリングする というパターンが多いと思われる。 問題へのリンク 問題概要 個の町 がある。町 からは、町 へテレポートできる。…

AtCoder AGC 006 C - Rabbit Exercise (800 点)

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

CODE FESTIVAL 2016 qual A C - 次のアルファベット / Next Letter (400 点)

辞書順最小の教育的例題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に以下の操作をちょうど 回行う。行った結果得られる文字列の辞書順最小なものを求めよ。 の文字を 1 つ選んで、1 文字進める。ただし 'z' は 'a' になる 制約…

AtCoder AGC 011 D - Half Reflector (900 点)

この問題が解けた勝因は、「実験しよう」と思えたことな気がする。 問題へのリンク 問題概要 高橋君は,ある特殊な装置をたくさん持っています. この装置は筒状で,左右からボールを入れることができます. また,この装置には 2 種類の状態 A, B がありま…

AtCoder AGC 006 D - Median Pyramid Hard (1300 点)

一目見て、データ構造げーかな...と思ってしまった。そういう先入観を持つと危ない。実際は好みな考察で解ける問題だった。 問題へのリンク 問題概要 正の整数 と からなる順列が与えられる。いま、この順列を下図左のようにピラミッドの最底辺に書き込む。…

CODE FESTIVAL 2018 qual A C - 半分 (500 点)

少し重たい 問題へのリンク 問題概要 長さ の整数列 が与えられます。 この数列に以下の操作をちょうど 回施します。 添字 を一つ選んで、 を 2 で割る (小数点以下切り捨て) 回の操作のあとの数列としてありうるものの個数を 109+7 で割ったあまりを求めよ…