ながめも

競技プログラミングについて

DP

Codeforces Round #672 (Div. 2) 参加記

A. Cubes Sorting すべての要素が異なり、逆順に並んでいるとき、バブルソートは最大で回の操作が必要になります。そうでないとき、それ未満で終わります。 void solve(){ int N; cin >> N; vector<ll> a(N); rep(i,N)cin >> a[i]; rep(i,N-1){ if(a[i] <= a[i+1</ll>…

AtCoder Beginner Contest 179 ABC179 参加記

A - Plural Form 解説 実装 B - Go to Jail 解説 実装 C - A x B + C 解説 実装 D - Leaping Tak 解説 実装 E - Sequence Sum 解説 実装 F - Simplified Reversi A - Plural Form 問題へのリンク 解説 末尾を確認します。 実装 int main() { string S; cin >…

AtCoder Beginner Contest 178 ABC178 参加記

5完で水パフォでした。青パフォstreakが切れて悲しいですね。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 178での成績:864位パフォーマンス:1597相当レーティング:1412→1432 (+20) :)Highestを更新しました!#AtCoder #ABC178 https://t.co/JlM3Zncq…

Codeforces Round #642 (Div. 3) E. K-periodic Garland

問題へのリンク 問題概要 解説 提出 問題概要 とのみで構成された文字列が与えられる。隣り合うの距離をちょうどにするために必要な操作回数の最小値を求めよ。 解説 周期で考える。 ある一つので割った余りが等しいindexについて、 という形に、 他のindex…

Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov!

A. Nastya and Rice 問題概要 実装 B. Nastya and Door 問題概要 解説 実装 C. Nastya and Strange Generator 問題概要 実装 D. Nastya and Scoreboard 問題概要 解説 実装 A. Nastya and Rice 問題概要 一つ重さの粒が個あり、その和がである場合、粒の重さ…

Typical DP Contest N - 木

Typical DP Contest N - 木 Typical DP Contest N - 木 問題概要 解説 問題概要 問題へのリンク 解説 まんまこれ。 AtCoder Beginner Contest 160 F - Distributing Integers 実はというと、当問題の答えは、類題の答えの半分になります。なぜかというと、辺…

AtCoder Grand Contest 043 AGC043 A - Range Flip Find Route

AtCoder Grand Contest 043 A - Range Flip Find Route コンテスト中に色々あったのでメモ。 問題へのリンク 問題概要 コンテスト中の方針(ダイクストラ) 解説 実装 別解 DP(こっちの方が簡単) 実装 類題 ※最後に類題を載せていますが、ヒントにもなりか…

AtCoder Beginner Contest 114 ABC114 D - 756

問題へのリンク 問題概要 提出 問題概要 個の約数なので、その性質自体を活かした解法もあるが、今回はあえて一般的な問題として捉え、DPをしてみる。 dp[i][j]: i個目までの素因数で約数の個数がj個 とする。 dp[0][1] = 1として(の約数は個と考える) 個…

Educational DP Contest / DP まとめコンテスト V - Subtree

Educational DP Contest / DP まとめコンテスト V - Subtree rerootingをします。全方位DPとも呼ばれているらしいです。 問題へのリンク 解説 rerootingをします。dp[i]: iを黒にしたときのiの部分木のパターン数とすると、根が0の場合の計算がdfsでできる。…

Codeforces Round #627 (Div. 3) F - Maximum White Subtree

F - Maximum White Subtree 問題概要 木に黒白の色が割り当てられていて、ある頂点を含む部分グラフにおいて白の数と黒の数の差を最大化してください。 解説 rerootingという概念らしいです。まず根が0も場合についてdpをします。 この計算自体はO(N)で終わ…

Codeforces Round #627 (Div. 3)

Codeforces Round #627 (Div. 3)に参加しました。 A - Yet Another Tetris Problem 問題概要 解説 提出 Yet Another Palindrome Problem 問題概要 解説 提出 C - Frog Jumps 問題概要 解説 提出 D - Pair of Topics 問題概要 解説 提出 E - Sleeping Schedul…

Educational Codeforces Round 83 (Rated for Div. 2) E. Array Shrinking

Educational Codeforces Round 83 (Rated for Div. 2) E. Array Shrinking) 問題 解説 提出 - for文 - メモ化再帰 参考 問題 隣り合う要素の値が同じ場合、それらを結合し、+1した値に置換える操作を繰り返したとき、長さの最小値。 解説 区間DP。 dp[i][j]:…

Educational DP Contest / DP まとめコンテスト N - Slimes

Educational DP Contest / DP まとめコンテスト N - Slimesを解きました。 問題 解説 提出 for文 メモ化再帰 参考 問題 隣り合うスライムをくっつけていっていくとき、かかるコストの最小値。ただしxとyのスライムをくっつけるときx + yのコストがかかる。 …