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

F - Distributing Integers F - Distributing Integers 問題概要 方針 k = 1パート 更新パート 実装 類題 タイトルの上に全方位DPタグがあると思うので、そこから類題を探してもいいと思います。類題が見たくない人は実装の下まで見ないように注意してくださ…

参加しました。5完で青パフォ、水色に復帰しました。苦しい時間が続いていたので戻れてよかったです。 My Submissions C 間で一番長いところを通らないように一周すればよいです。 D N回ダイクストラしましょう。制約的に通ります。 E DPかと思ったけど、Cは…

参加しました。 順位表 Sum of Odd Integers 問題概要 解説 提出 Princesses and Princes 問題 問題 入力 出力 解説 提出 Game with Chips 問題概要 解説 提出 D - Infini Path 問題概要 E - Count The Blocks 問題概要 解説 提出 Sum of Odd Integers 問題…

ABC159に参加しました。 Eの無限ループに気づかず4完でした。悲しいです。実装は自分なりに綺麗にできていたのでそこは満足しています。 A - The Number of Even Pairs 問題へのリンク 偶数が個、奇数が個からつ選んで足して偶数になるペアは何通りあるか数…

E - Dividing Chocolate 記事を移動してきました。 ABC159の記事へのリンクはこちら 実装が重いと思うのは私の実装力のなさ故でしょうか・・・。反省点としては、通るはずの計算量なのにTLEした場合は、更なる高速化に走る必要はなく、コーナーケースによっ…

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

問題 方針 単調性 判定問題 区間の中央値がX以上になる条件 区間列挙の解決策 実装 問題 長さNの数列が与えられる。この中の全ての連続部分列における中央値の中央値を求めよ。 問題へのリンク 方針 単調性 二分探索する。 中央値がX以上となる区間の数が全…

反転数とは 方針 愚直にO(N2) 高速化、O(NlogN) 方針転換 準備 実装 今回は反転数について扱っています。転倒数とも呼ばれるようです（というより競プロ界隈では転倒数の方が一般的かも？）。 問題へのリンク 反転数とは 数列があるとき、 のとき となるの組…

AOJ RSQ 問題へのリンク AOJ RSQ Binary indexed Treeによる解答 BITとは 実装 提出 Binary indexed Treeによる解答 BITとは 以下のスライドが参考になります。説明はいろいろなところにあるので、適宜調べてみてください。 Binary Indexed Tree のはなし 実…

AtCoder Beginner Contest 091 ABC091 D - Two Sequences AtCoder Beginner Contest 091 ABC091 D - Two Sequences 問題概要 解説 方針 解答方法 提出 問題概要 長さNの二つの数列a,bがある。これらの全ての組み合わせa_i + b_jに対して、全てxorをとったと…

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

ABC149 E - Handshake 問題へのリンク ABC149 E - Handshake 問題概要 解説 提出 問題概要 i,jをM回選んだとき、A[i] + A[j]の最大値を答えよ。ただし、同じi,jを選べない。 解説 方針として、全てのi,jを列挙して大きい方からM個とってくれば良いことがわか…

D - String Equivalence 公式解説と別の方法でACしたので共有します。DFSによる全探索は様々な方法で実装できます。いろいろな実装方針で書けるようになると、何が本質なのかが見えてきやすくなり、問題によらずAC率が上がると思うので、ぜひ一度通したこと…

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

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

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

AtCoder Beginner Contest 129 E - Sum Equals Xor 解説 提出 解説 a + b = a xor b a + b = a xor b + 2 * (a & b) より a & b = 0 と読み替える a + b <= L以下で、a & b = 0となるaとbの組み合わせの個数を答える問題に変わる。 桁DPをする。 a + bがL未…

AtCoder Begginer Contest 129 E - Sum Equals Xor 解説 提出 解説 a + b = a xor b a + b = a xor b + 2 * (a & b) より a & b = 0 と読み替える a + b <= L以下で、a & b = 0となるaとbの組み合わせの個数を答える問題に変わる。 桁DPをする。 a + bがL未…

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

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

Educational Codeforces Round 81 (Rated for Div. 2)にVirtual参加しました。 A - Display The Number 問題概要 解説 提出 B - Infinite Prefixes 問題概要 解説 提出 C - Obtain The String 問題概要 解説 提出 D - Same GCDs 問題概要 解説 提出 参考 A -…

Educational Codeforces Round 82 (Rated for Div. 2)にVirtual参加しました。 A - Erasing Zeroes 問題概要 解説 提出 B - National Project 問題概要 解説 提出 C - Perfect Keyboard 問題概要 考えたこと 解説 提出 D - Fill The Bag 解説 提出 参考 A - …

参加しました。 A Two Regular Polygons 解説 提出 B Bogosort 解説 提出 C Adding Powers 解説 提出 D Count the Arrays 解説 提出 A Two Regular Polygons 解説 N % M == 0 提出 #include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i</bits/stdc++.h>

ABC127 E - Cell Distance 方針 xとyは別に計算してあとで足し合わせてよい もっと言えば、xとyは対称なので、xについて考えればよい 距離は2点間に定義される量なので、K個選ぶとか考えずに、距離dが何回現れるかを考える d=0は考える必要がない dは1 ~ N-1…

参加しました。 結果は散々だったので割愛します。 A - Hitachi String 感想 B - Nice Shopping 解説 C - ThREE コンテスト中 解説 実装 A - Hitachi String 感想 長さの偶奇でわかるのでやるだけなんですが、焦って3WA出しました・・・ #include <bits/stdc++.h> using nam</bits/stdc++.h>…