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

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

負値が本質的に効く問題

AtCoder ABC 178 B - Product Max (5Q, 灰色, 200 点)

「ギリギリを考える」という考察の基本形と言える問題 問題へのリンク 問題概要 整数 が与えられるので、 を満たす整数 についての の最大値を求めよ。 制約 考えたこと この手の問題で考えることは、「端点のみ考えれば良いのでは」などと疑うこと。つまり…

AtCoder ABC 173 E - Multiplication 4 (1D, 青色, 500 点)

個から 個を選ぶ設定の問題! 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…

Codeforces Round 892 (Div. 2) E. Maximum Monogonosity (R??00)

つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック!!!! 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…

EDPC (Educational DP Contest) W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにします。 今、文字列中の 個の連続する区間 ( 番目の区間を とします) が与えら…

AOJ 2956 ジャム (Jam) (HUPC 2019 day2-E)

こういうのを素早く解けるようになりたい 問題へのリンク editorial 問題概要 頂点 辺の重み付き無向グラフがある。各頂点 には そこで売ってるパンを買ったときの美味しさ そこで売ってるジャムの種類 そこで売ってるジャムを買ったときの美味しさ という 3…

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

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

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

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

AtCoder AGC 008 B - Contiguous Repainting (青色, 400 点)

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

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] として負の値もあるのが…