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

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

操作:区間

HackerRank Happy Query Contest 2019 Array Restoring

形式的冪級数 (FPS) を用いた「多項式としての除算」の練習に 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 がある。 は初期状態ではすべて 0 である。 に以下の一連の 回の操作を行った。 各操作は区間 で表される ( を満たす) 数列 の該当する区…

AtCoder ABC 140 D - Face Produces Unhappiness (400 点)

ABC では数少ない発想力系。 問題へのリンク 問題概要 L と R から成る 文字の文字列 が与えられる。文字列のスコアは次のようにして決められる。 各 index i について S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算 S[ i …

Codeforces Round #598 (Div. 3) F. Equalizing Two Strings (R2200)

誤読したーーーーーー操作は 1 回しか行えないものと思って悩んでた 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を好きな回数だけ行うことで、 と とが一致する状態にすることが可能かどうかを判定せよ。 1 以上 以下の整数 を定める …

AtCoder AGC 043 A - Range Flip Find Route (400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

Codeforces Round #618 (Div. 1) C. Water Balance (R2100)

これが R2100 って嘘でしょ...R2500 くらいに感じる...こどふぉ民の感覚って... 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。その結果として考えられる辞書順最小なものを求めよ。 数列の任意の区間…

AtCoder ABC 153 F - Silver Fox vs Monster (600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

AtCoder ARC 085 F - NRE (1000 点)

実家なんだと思うけど...意外とはまりやすい問題な気がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (500 点)

区間反転操作問題シリーズ!!! それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

CPSCO 2019 session2 E - Mogu Mogu Gummi (600 点)

二乗の木 DP のいい練習問題!!!!! ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

AtCoder AGC 032 D - Rotation Sort (1000 点)

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

AtCoder ABC 124 D - Handstand (400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

AtCoder AGC 010 B - Boxes (500 点)

状況がゴチャゴチャとして来て、整理するのが大変だった 問題へのリンク 問題概要 個のマスがあって最初は全マスに が書かれている。これに以下の操作を好きな回数だけ好きな順序で行って数列 にできるかどうか判定せよ。 を巡回させてできるものを足す 制約…

AtCoder AGC 031 B - Reversi (700 点)

これは安定感のある思考過程を経て解けた気がするので共有したい気持ち!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。各 は 以上 以下の整数値である。今、以下のような操作を何回でも行うことができる: となるような < を選んで、 と との間の…

AtCoder AGC 008 B - Contiguous Repainting (400 点)

操作を逆順に見るとよいという、すごく良い例題!大好き!!! 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…

AtCoder ABC 116 C - Grand Garden (300 点)

整理するのがちょっと大変系。でもとても教育的だと思う! 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…

全国統一プログラミング王決定戦 本選 E - Erasure (700 点)

700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…

SoundHound 2018 本戦 B - Neutralize (400 点)

本番では回避したん。こういうのをサッサササッとバババババーンと解けるようになりたいん。 問題へのリンク 問題概要 個の数列 が与えられる。以下の操作を好きな回数だけ行って得られる数列の総和を最大化せよ。 連続する 個の区間の数列を一斉に 0 にする…

AtCoder ARC 099 C - Minimization (300 点)

ARC 099 C - Minimization 問題概要 (ARC 099 D / ABC 101 C) 1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。 連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える 制約 1 <= K <=…