計算量の意識が必要になる良問！ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。これを左右に 2 つに分ける（左右ともに 1 個以上はとる）。 左側の要素の総和を 、右側の要素の総和を とするとき、 の最小値を求めよ。 制約 考えたこと もし…

「区間の値の和」を見たら、累積和をとろう！！ 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…

この時代、この手の Greedy はたくさんあったのね！ 問題へのリンク 問題概要 長さ の数列 が与えられる。「数列の要素を 1 つ選び、+1 するか、-1 する」という操作を行うことで、次の状態を達成したい。ただし、 とする。 すべての に対して、 である すべ…

数学の部分を乗り越えることが難しいかもしれない。 問題へのリンク 問題概要 人 が、一対一の勝敗のつくゲームを何度か行った。 人の最初の持ち点は 0 点である。 各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減る。（持ち点が負になることもある…

とっても教育的な DP の問題！！！ 問題へのリンク 問題概要 高橋君の前に 個の料理が順に配られる。高橋君はその都度「食べる」「下げてもらう」を選択することができる。 番目の料理は、 のとき、解毒剤入りの、美味しさが の料理 のとき、毒入りの、美味…

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

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

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

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

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

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

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

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

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