atcoder.jp 個数と和が同じなら同じ数、個数が異なるなら和が同じでも異なる数にカウントする問題。 個選ぶと決め打ったとき、できる数は 前個の和と、後ろ個の和の間すべて である。 これは簡単な帰納法で証明できる。 int main() { ll N, K; cin >> N >> K…

atcoder.jp 類題がこれ。 coonevo.hatenablog.com ライブラリでやるだけ。 template<typename T> class BIT{ public: int N; vector<T> data; BIT(T _N):N(_N){ data.assign(N+1, 0); }; // a is 1-indexed void add(int a, T w){ for(int x = a; x <= N; x += x & -x)data[</t></typename>…

問題へのリンク 解説 実装 感想 解説 例えばのとき、各セルが外に出るときに嫌われる客の数の初期状態は以下のようになる 0 0 0 0 0 0 0 1 1 1 1 0 0 1 2 2 1 0 0 1 2 2 1 0 0 1 1 1 1 0 0 0 0 0 0 0 ここからあるセルが外に出た後の変化を調べたい。ここで…

4完で水パフォでした。長針は離散的に動きません。余弦定理がTwitterトレンドに入っていて笑っていました。 提出へのリンク 順位表 A - ∴ (Therefore) B - ... (Triple Dots) C - : (Colon) D - .. (Double Dots) E - ∙ (Bullet) F - Bracket Sequencing A -…

5完で青パフォでした。ムーブ的にはよかったと思います。 提出へのリンク 順位表 A - Registration B - Easy Linear Programming C - Skill Up D - Teleporter E - Colorful Blocks F - Bracket Sequencing A - Registration pop_back()するのが最適っぽいで…

atcoder.jp 広義単調増加列の数え上げ。 これなので、 coonevo.hatenablog.com

E - Rotation Matching 解説 まず操作ですが、人の数字割り当てが回転するのではなく、対戦場の割り当てが回転していくと考えても同じことです。 ある対戦場の割り当ては回回転するので、円形に考えると一周することになります。 同じ割り当てになってしまう…

5完で水パフォでした。ムーブがダメダメすぎましたし、Eは無限人が瞬殺していたので解けたことで喜ぶこともできないみたいです。Dは問題文が優しくないなあと思いつつも、よく読まない人が悪いということになるので・・・ A B C D E F A はい B お菓子持って…

AtCoder、AtCoder Beginner Contest、D - Multiple of 2019、E - Two Currencies、拡張ダイクストラ、競技プログラミング

C - Many Requirements 解説 単調増加列の数え上げですが、以下の考え方がわかりやすいです。 maspyさん 単調増加数列の数え上げは、・1 <= x < y < z <= Nbinom(N,3) それはそう・1 <= a <= b <= c <= Nx=a, y=b+1, z=c+2 とおくと、1<=x

問題へのリンク 問題概要 制約 解説 問題概要 問題が問あり、番目の問題のスコアはである。人が独立に問選び、それらのスコアをずつ上げる。人の選択後、スコアの降順に並べられ、最初の問が採用される。採用される可能性のある問題は何問あるか？ 制約 解説…

公式想定解と異なる解き方をしたので共有します。 問題概要 解説 方針 DPの定義、初期化、遷移 定義 初期化 遷移 実装 問題概要 問題へのリンク 正の整数が以下の条件を満たすとき、はルンルン数であるといいます。 Xを(leading zeroなしで)十進数表記した際…

参加しました。3完で緑パフォ、緑に戻りました。水切り楽しいですね。 E、Fは読んでないのでそのうち復習します。 My Submissions C chokudaiさんのすごろくの考え方が面白かったです。 C問題、数学の問題といえばそうなんだけど、「無限に長いすごろくがあ…

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は…

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以上となる区間の数が全…

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率が上がると思うので、ぜひ一度通したこと…

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

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>…

atcoder.jp 解説は以下の記事参照。 scrapbox.io 全国統一プログラミング王決定戦 AtCoder