2020-01-01から1年間の記事一覧

EDPCを3周して掴んできた勘所

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

ARC007 C 節約生活

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

1269 B. Modulo Equality

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 解答 まずソー…

1278 B. A and B

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

降順ソートされたコンテナでlower_bound

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

Vimでライブラリをスニペットとして登録する

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

C++でpriority_queueを実装する

(競プロ以外の場面で)優先度付きキューを自力で実装する必要に迫られたので、自力で実装してみました。二分ヒープをベースに実装してあります。 ※いくつかのメソッドは実装していません 実装 #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()マクロを使うと、変…

1332 C. K-Complete Word

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

Perfect Keyboard

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

Cow and Message

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

Skyscrapers (hard ver)

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

Skyscrapers

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