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

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

変化・遷移が限られる

AtCoder AGC 003 E - Sequential operations on Sequence (赤色, 1400 点)

この頃、数列を繰り返すのが流行ってたのかな 問題へのリンク 問題概要 長さ の恒等数列 () が与えられる。この数列に以下の操作を合計で 回行う。 番目の操作は、パラメータ であらわされ、以下のように行われる。 現在の数列を無限回繰り返した数列の先頭 …

AtCoder ABC 157 E - Simple String Queries (水色, 500 点)

一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1: の 文字目を に変更する タイプ 2: の区間 に含まれる文字の種類数を答える …

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning (黄色, 700 点)

遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…

AtCoder AGC 031 B - Reversi (水色, 700 点)

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