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

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

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

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

解説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]....

JOI 2020/2021 二次予選 「イベント巡り (Event Hopping)」 に関する記事です． 公式解説 を読みきれなかったので…. 問題へのリンク https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_c 解法 ちょっと不思議な感じで，小課題3 を (私の感覚では) 自然に解くと， それが満点解法にもなっているという… (解説を読むまでわからなかったのですけれど) ソートして，$S_i$ が昇順になっているとします． ナイーブに考えると，次の DP になります． dp[i][j] := i番目のイベントに参加する直前までに参加したイベントの 回数が j であるような方法がある (True/False) 遷移としては，dp[i][j] = True となる j について， 町 $P_i$ で行われるイベントで，時刻 $S_i + 1$ 以降最も早いものを i1 町 $3 - P_i$ で行われるイベントで， 時刻 $S_i + 1 + D + K(j + 1)$ 以降最も早いものを i2 として， dp[i1][j+1] := True dp[i2][j+1] := True と設定することになります．でも，これは $\Omega(N^2)$ なので，間に合いません．...

解けませんでした．オンライン・オフライン変換を調べて書きました．

距離を求める際の，ダイクストラ, 0-1BFS, BFSのコーディング方法のまとめです． 記法 ノードを表すデータ型を Node とする． int や long long や pair<int, int> など． ダイクストラ 前提: ノード間の距離δ(x,y)が全部非負 距離の候補を優先度付きキューに入れていく． あるノードがキューから初めて取り出されたときにそのノードへの距離が確定する． 使用するデータと初期化 priority_queue のメソッドは，push(), emplace(), pop(), top() など． using P = pair<ll, Node>; // 距離とノード priority_queue<P, vector<P>, greater<P>> pque; // 優先度付きキュー // 値 (d, x) は，ノードxへ，長さdのパスがあることを示す． pque.emplace(0, initial_node); // 始点をキューに vector<ll> dist(N, LLONG_MAX); // 距離．始点以外は∞ // Node型 によっては，map<Node, ll> dist; など． dist[initial_node] = 0; // 始点の距離は0 ループ pque から取り出した (d, x) について， dist[x] < d なら，もっと良い d があって， それが既に取り出されている，ということなので，単に捨てる． そうでなければ (dist[x] == d ならば) この d が x への最短距離であることが確定した． x の 各隣接ノード y について，newd = x + δ(x, y) が y への距離の候補なので以下を行う． dist[y] <= newd なら，単に捨てる． そうでなければ，次を行う． dist[y] を newd に更新する． (newd, y) を pque に入れる． ゴール...

キーエンスプログラミングコンテスト 2021 E - Greedy Ant に関する記事です． 問題へのリンク https://atcoder.jp/contests/keyence2021/tasks/keyence2021 解法 公式解説 の通りではありますが，若干表現を変えます． すぬけ君が，蟻から遠い飴を取っても，蟻の行動には直ちには影響を与えません． そういう状況ではすぬけ君は「スキップ」することにして，後から蟻がその飴に近づいてきたとき (左右いずれかで蟻の最も近い飴になったとき) に取ることにしても，ゲームの意味が変わりません． つまり，次のようにゲームを言い変えることができます． (両端などの扱いはサボっています) 初期化: // 蟻の初期位置を 2n + 1 とする． l := n // 蟻に最も近い左の飴の位置が 2l r := n + 1 // 蟻に最も近い右の飴の位置が 2r k := 0 // すぬけ君の「スキップ」回数 ループ: k += 1 while k > 0: match すぬけ君の選択(): case なし: break case 左: すぬけ君が 2l の飴を取る; l -= 1 case 右: すぬけ君が 2r の飴を取る; r += 1 k -= 1 蟻が，2l, 2r の飴のおいしい方を取る 取った方に応じて l -= 1 または r += 1 そこで， f(l,r,k) を，「上記 while の先頭位置で，l,r,k がこの値である時に，すぬけ君がこのあと取る得点の最大値」として 定義します． 次の漸化式が書けます．...