ひらめの日常

日常のメモをつらつらと

区間

AtCoder: ABC146-E Rem of Sum is Num (500)

問題はこちら atcoder.jp 長さ の整数列 と正の整数 が与えられる。 の空でない連続する部分列であって、要素の和を で割った余りが要素の数と等しくなるものの数を求めよ。 以下は0-indexで話を進める。 考え方 要素の和の余りに関する問題なので、とりあえ…

AtCoder: 第二回日本最強プログラマー学生選手権-予選- D Shortest Path on a Line (600)

問題はこちら atcoder.jp 個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。 となる頂点と頂点 の間にコストの辺を追加する。 最終的な頂点からまでの最短距離を求めよ。 以降は0-indexとして話を進める。 解法1 - seg木でdp が与…

AtCoder: ABC140-E Second Sum (500)

問題はこちら atcoder.jp 長さ の順列 が与えられた時、区間 に対して以下を計算せよ。 全ての重複しない区間において、二番目に大きい数の和。 考え方 簡単バージョンとしてこの問題があるので見ると良い。 atcoder.jp step1 - 問題の言い換え 愚直にやると…

AtCoder: ABC140-D Face Produces Unhappiness (400)

問題はこちら atcoder.jp 長さ の文字列 が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。 操作: となる を選び、 ] 内にある文字列を左…

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

問題はこちら atcoder.jp 考え方 なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。 misteer.hatenablog.com Cで僕が考えたこと・累積的な何かを考えるとよさそう・[L, R]…