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

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

負値が本質的に効く問題

AtCoder EDPC W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにしま…

AtCoder ABC 155 D - Pairs (青色, 400 点)

最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…

AtCoder ARC 085 E - MUL (橙色, 700 点)

いわゆる「燃やす埋める」の典型です。 問題へのリンク 問題概要 個の整数 が与えられます (負値もありえます)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができます。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 …

AtCoder AGC 002 A - Range Product (灰色, 200 点)

注意力系。現在の AGC ではあまり見ない系な気もする。 問題へのリンク 問題概要 整数 が与えられる。 すべての積が正か負か 0 かを判定せよ。 制約 考えたこと こういうのは場合分けを丁寧にやろう!!! まず、 のケースがわかりやすく になる。 そう思っ…

CS Academy 079 DIV2 E - Smallest Subsets

CS Academy 079 DIV2 E Smallest Subsets 問題概要 N 個の整数 S[0], S[1], ..., S[N-1] が与えられる。これらの部分和 (2N 通り) を小さい順に K 個出力せよ。 1 <= N <= 105 1 <= K <= min(2N, 105) -109 <= S[i] <= 109 解法 S[i] として負の値もあるのが…