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

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

区間操作

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

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

AtCoder AGC 032 D - Rotation Sort (1000 点)

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

AtCoder ABC 124 D - Handstand (400 点)

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

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 <=…