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

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

操作をちょうどK回行う

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

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

DISCO presents 2016 予選 C - アメージングな文字列は、きみが作る! (橙色)

とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…

AtCoder ABC 246 C - Coupon (灰色, 300 点)

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

AtCoder AGC 036 C - GP 2 (黄色, 900 点)

こういう数え上げ、大好きすぎる!!! 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…

CPSCO2019 Session3 G - Grand Election (800 点設定)

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

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

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

AtCoder ABC 175 C - Walking Takahashi (茶色, 300 点)

ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう! 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…

AtCoder ABC 171 F - Strivore (青色, 600 点)

実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という!!! 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…

AtCoder ABC 167 D - Teleporter (茶色, 400 点)

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

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

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

AtCoder AGC 011 D - Half Reflector (赤色, 900 点)

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

みんなのプロコン 2019 C - When I hit my pocket... (茶色, 400 点)

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…

AtCoder AGC 021 D - Reversed LCS (黄色, 900 点)

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …

yukicoder No.801 エレベーター

累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…

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

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