2020-04-01から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つを選ぶ その要素より左は広義単調増加、右は広義単調増加ように配列の各要素の値を減らす 操作後の配列のうち総和が最大となるときの配列を出力せよ。 解法 ある要素を実際に選んでみ…