Posts

C++言語や，C++ Standard Template Library の書き方で，忘れやすいものをメモしておくページです．

公式解説にある貪欲法の証明を詳しく書きました．

重実装への対処は，どうしたらよいのでしょうか?

slope trick というのは忘れていましたが，そもそもHまで到達しませんでした．この記事は公式解説そのままです．

「牛ゲー」なる手法のまとめです

公式解説とは違う (より効率の悪い) 方法で解きました．

調べた結果分かった解法を記述します．いろいろ勉強になりました．

解けませんでした．解説を読んでも分からなかったので，自分なりの説明です．

解説AC です．公式解説も皆さんの解説もたくさん参考にしています．

解法です．公式解説そのままです．

公式解説そのままですけれど，予備知識を一応書きました．

高速アダマール変換によって，xor畳み込みをする方法についての記事 (自分用のメモ) です．

C++ での型の変換などのいろいろな変換方法です．

Atcoder Regular Contest 104 (ARC 104) E Random LIS に関する記事です． 問題文へのリンク https://atcoder.jp/contests/arc104/tasks/arc104_e 経緯 過去問埋めで解いてみようとしましたが，全然わかりませんでした． 公式解説 を読んでもやっぱりわからず， けんちょんさんの解説 を読んで，なんとか理解することができました． 解法 例えば，N = 4 として，数列 10 7 10 15 と数列 5 1 5 2000 は， 数値の差こそあれ，大小関係は同一である．これらを 1 0 1 2 というパターンとして 1つのグループとしてまとめることにする．以下を実行する． 全パターンを列挙する． 各パターンについて， LISの長さを求める． そのパターンに属する数列の数を数える． グループがいくつあるかは， Ordered Bell number として知られているということである．N = 6 の場合には，4683個． 丁寧に列挙することもできるであろうが，$6^6 = 46656$ であるから，0 から N-1 までの 数の N 個の並びから，不適なものを弾いても十分速い． 各グループに属する数列では，LIS の長さは同じであり，N <= 6 だからこれを求めるのは容易である． 各グループに属する数列の数を求めるのが主要なタスクとなる． $\{0, 1\} \cup \{A_i + 1\mid i = 1, \ldots, N\}$ を昇順にソートして $p_0, p_1, ....

発端 自分で書いた SCC (強連結成分分解) ライブラリを使っているのですが， これが，AC-library の SCC に比べて，4倍くらい遅いのです． どこが遅いのか調べてみたら，意外なところにもネックがありました． 最初は，主に使っているアルゴリズムのせいだと思ったのです． 深さ優先探索を2回行うアルゴリズム (たとえばここ を参照) を使っていました． AC-library は，Tarjan のアルゴリズム を使っているようなので，合わせれば速くなるだろう，と思って 書きかえました． たしかに速くなったのですが，それでもまだAC-libraryより3倍ほど遅いです． vector<vector<*> > 部分に分けて測定してみたところ，どうも，グラフの情報を設定しているところも 遅い，ということが分かりました． こんな感じのコードなのですが: int N, M; cin >> N >> M; // N は頂点数, M は辺の数 vector<pair<int, int>> edges; for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; // 0-indexed で入力されると仮定 edeges.emplace_back(u, v); } vector<vector<int>> fwd(N); // fwd[i] は，i から直接行ける頂点たち． // (1) for (auto [u, v] : edges) { fwd[u]....