geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

部分和DP

AtCoder Biginner Contest 262 参加記録

コンテストへのリンク:■ コンテスト中AC:A〜D D - I Hate Non-integer Number 数列の部分和に関する問題なので、部分和DPを考えます。 数列の項目までの部分和であって、和がとなるものの個数 今回は、何個選んだかも必要なので、情報を足します。 数列の項…

ABC222 参加記録

コンテスト中AC:A〜E D - Between Two Arrays 以下のDPを考えます。 がである整数列の総数 遷移を考えると、のとき、をにできるので、 となります。 これをについて計算していると、 というワーストケースを例として計算量はは超えてくるので、計算量を改善…

ABC216 参加記録

コンテスト中AC:A, B, C, D C - Many Balls 操作を逆順に考えるのは典型です。Nから始めて0にすることを考えると、魔法Aは-1、魔法Bは÷2することになります。 すると、奇数なら魔法Aしかできず、偶数なら魔法Bを使用する方が0に近づけます。 奇数ならA、偶…