おさらい: トポロジカルソートとは トポロジカルソートは、DAGをソートして右にあるノードから左へエッジが伸びないようにするソート。 アルゴリズムはこんな感じ 入次数が 0 のノードをすべてキューへ積む キューからノードを取り出す 取り出したノードから…

後半のT以降はまだ1回も解けてないのですが、Sまでは3周したのでメモです。 ひたすら「メモ化再帰」と思い込む いきなりdpの配列を想像すると脳がパンクするので、まずはメモ化再帰を書いてみてください。メモ化再帰から始める利点としては以下が挙げられま…

問題設定がけっこうややこしいので本文を読んでください C - 節約生活 解説 まず、答えがN以下であることは明らかだ。なぜならoが1個は含まれるので、oをN個並べてやればそれ以降条件を満たすからだ。 これをさらによく考えてみる。まず、Sの後ろにもうひと…

Problem - 1269B - Codeforces 問題概要 長さNの数列A,Bを与えられる。Aの各要素にXを足し、Mで割った数列をCとする。Cを並べ替えるとBと一致するとき、Aに足すべき最小のXを求めよ。 入力 1 ≦ n ≦ 2000 1 ≦ m ≦ 109 0 ≦ a_i < m 0 ≦ b_i < m 解答 まずソー…

Problem - 1278B - Codeforces 問題概要 A,Bの2数が与えられる。これらに対し、以下の操作を行う。 片方を選ぶ n回目の操作だとしたら、選んだ数へnを足す A,Bを等しくするには最小で何回の操作が必要か答えよ。入力はT個与えられる。 制約 1 ≦ A,B ≦ 109 1 …

わかればそれはそうか、となるのですが頭に入ってないとこの発想が出てこなそうなので書いておきます。 やり方はメチャクチャ簡単です。 lower_bound(v.rbegin(), v.rend(), value); これだけです。ポイントは逆イテレータを渡していることです。たったそれ…

僕は今まで競プロ用のライブラリをファイルとして保存しておいて、それをコピペするスタイルを取っていました。しかし、いささか面倒になってきたのでスニペット化してみました。 実現したいこと たとえばmint.cppというファイルがあるとします。 template<int MOD>st</int>…

(競プロ以外の場面で)優先度付きキューを自力で実装する必要に迫られたので、自力で実装してみました。二分ヒープをベースに実装してあります。 ※いくつかのメソッドは実装していません 実装 #include <vector> #include <functional> template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>> cla</typename></class></functional></vector>…

書きやすさ・使いやすさ・応用性の高さから便利だよという紹介です。 #define in(v) v; cin >> v; int main() { int in(N); // int in(M); // int in(H); int in(W); rep(i, N) { int in(a); // cin >> A[i]; } return 0; } 解説 このin()マクロを使うと、変…

codeforces.com 問題概要 ある文字列SとKが与えられる。文字列SをK-completeな単語にするには最小で何文字変えれば良いか？なお、K-completeな単語とは以下のような単語を意味する。 回文である i文字目とi+K文字目が等しい なお、t個のテストケースに対して…

codeforces.com 問題 アルファベット26文字が1列に並ぶキーボードを考える。いま、パスワードがN個与えられる。キーボードの配列をうまく組み替えることで、隣接したキー間の移動のみでパスワードを入力することができるか？ 入出力例 入力 はじめにパスワー…

codeforces.com 問題 ある文字列Sが与えられる。Sに含まれる部分文字列のうち出現頻度が最も高いものの長さを求めよ 例 入力: ababab 出力: 6 これにはabが6個入っているので出力は6となっている。 解説 参考: 题解 Codeforces Round #621 (Div. 1 + Div. 2)…

codeforces.com 問題概要 簡単に言えば ある配列が与えられる ある要素1つを選ぶ その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす 操作後の配列のうち総和が最大となるときの配列を出力せよ。 C1と同様の問題で、制約のみが…

codeforces.com 問題概要 簡単に言えば ある配列が与えられる ある要素1つを選ぶ その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす 操作後の配列のうち総和が最大となるときの配列を出力せよ。 解法 ある要素を実際に選んでみ…