Posts

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 がこの値である時に，すぬけ君がこのあと取る得点の最大値」として 定義します． 次の漸化式が書けます．...

gcc (g++) の policy-based data structure の中にある tree (の競技プログラミングでの利用) に関する記事です． リンク Policy-based Data Structure (GCC online docs) Codeforces admant's blog まとめ 以下の操作ができる set や map x を指定して，x より小さい要素がいくつあるか数える n を指定して，n 番目に小さい要素へのイテレータを取得する 先頭部分 #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; 型の定義 例: pair<int, int> の集合 using pair_t = pair<int, int>; using ordered_set = tree< pair_t, null_type, less<pair_t>, rb_tree_tag, tree_order_statistics_node_update >; 例: string から int へのマップ using ordered_map = tree< string, int, less<string>, rb_tree_tag, tree_order_statistics_node_update >; 機能の呼び出し ordered_set os; os....

きたまさ法に関する記事です． よすぽさんの記事 を参照して書きました． 問題設定 整数 $ d_0 , \ldots, d_{ k - 1 }$ と $a_0, \ldots, a_{k - 1}$ が与えられている． 漸化式 $ a_{n + k} = d_{0} a_{n} + \cdots + d_{ k - 1 } a_{n + k - 1}$ で定義される数列の $a_n$ を $O( k^2 \log n )$ で求める． 行列 $$ A = \begin{bmatrix} d_{ k - 1 } &\cdots & \cdots & d_{ 0 } \\ 1 & & \Large{0} & 0 \\ & \ddots & & 0\\ \Large{0} & & 1 & 0 \\ \end{bmatrix} $$...

二項係数 binom(n, r) を，小さい素数 p に対して mod p で求める方法に関する記事です． 観察 p = 3 に関していくつか書いてみると次のようになっている． 0 1 1 1 1 2 1 2 1 10 1 0 0 1 11 1 1 0 1 1 12 1 2 1 1 2 1 20 1 0 0 2 0 0 1 21 1 1 0 2 2 0 1 1 22 1 2 1 2 1 2 1 2 1 100 1 0 0 0 0 0 0 0 0 1 101 1 1 0 0 0 0 0 0 0 1 1 102 1 2 1 0 0 0 0 0 0 1 2 1 110 1 0 0 1 0 0 0 0 0 1 0 0 1 111 1 1 0 1 1 0 0 0 0 1 1 0 1 1 112 1 2 1 1 2 1 0 0 0 1 2 1 1 2 1 120 1 0 0 2 0 0 1 0 0 1 0 0 2 0 0 1 こんな感じの構造になっている:...

Lagrange補間に関する記事です． 要約 $$ f(x) = \sum_{i = 0}^{k}\frac{ f(i) }{ (-1)^{k - i} \; i ! \; (k - i) ! } \cdot \frac{ 1 }{ x - i } \cdot \prod_{j=0}^{k} ( x - j ) $$ 詳細 \( k \) 次多項式 $f(x)$ について，$x = 0, \ldots, k$ の値が，$f(0) = v_0, \ldots, f(k) = v_k$ と分かっているときに， $f(x)$ (の各係数) を決める方法． 連立方程式を解く方法だと，逆行列を計算する必要があるから，\( \Omega( k^3 ) \) になってしまうが， Lagrange補間だと，$O(k^2)$ で済む． $I = \{0, \ldots, k\}$, $I_i = I \setminus \{ i \}$ とする．$i = 0, \ldots, k$ について，$k$ 次の多項式 $g_i(x)$ を， 次で定義する．...

行列木定理についての記事です． これを使う問題が，第二回日本最強プログラマー学生選手権 の G - Spanning Tree として出題されました． 定理 自己ループのない無向グラフ $G$ がある．頂点を $1, \ldots, N$ とする． 対称 $N\times N$ 行列 $A = (a_{ij})$ を，次で定める: $a_{ii} = $ 頂点$i$の出次数 $a_{ij} = - ( i \text{と} j \text{を結ぶ辺の数} )$ このとき，A のすべての余因子は等しく，G の全域木の数と一致する． 例 上のグラフでは， $$ A = \begin{bmatrix} 3 & -1 & 0 & -2 \\ -1 & 3 & -1 & -1 \\ 0 & -1 & 2 & -1 \\ -2 & -1 & -1 & 4 \end{bmatrix} $$...

CodeForces Round #431 (Div.2) E - Goodbye Souvenir についての記事です． 問題へのリンク https://codeforces.com/contest/849/problem/E 経緯 Yoika さんが主催している Morningforces というバーチャルコンテスト で出て，解けませんでした． 公式解説 を読んだのですが，最後に出てくる座標圧縮云々がよく分かりませんでした． 問題概要 整数列 $a = a_1, \ldots, a_k $ に対して，$m(a)$ を，$a$ に現れる各数 $x$ に対して，$x$ が最後に現れる位置と最初に現れる位置との差の総和として定義する．例えば，$m(1, 2, 3, 1, 3, 2, 1) = (7-1) + (6-2) + (5- 3) = 12$．最初に長さ n の整数列 a が与えられる．各要素は1以上n以下．次の2種類のクエリ (全部で$m$個) を処理せよ．$ 1 \leq n, m \leq 100,000$． p, x が与えられて，aのp番目の要素をxに書き換える． l, r が与えられて，$ m(a[l:r]) $ を求める． 解法 ということで，実装手段を除いては公式解説をなぞっています．...

C++ での乱数の使い方のメモです． 典型的なコード ll n; cin >> n; random_device rand_dev; mt19937 rng(rand_dev()); uniform_int_distribution<ll> dist(1, n); for (ll i = 0; i < 10; i++) cout << dist(rng) << " "; cout << endl; クラス random_device マニュアル オブジェクトは乱数発生器．non-deterministic な乱数を生成する． operator() を実行すると，unsigned int の乱数が返り，状態が進む． 実行は高価である可能性がある． クラス mt19937 マニュアル 32bitメルセンヌツィッター乱数発生器 64bitメルセンヌツィッター乱数発生器 の mt19937_64 というクラスもある． o.operator() を実行すると，uint_fast32_t の乱数が返り，状態が進む． コンストラクタに seed を渡す． デフォルトコンストラクタは引数をとらず，seed = 5489u を用いる．したがって，次のように書けば，どの実行でも同じ値が生成される． mt19937 rng; クラス uniform_int_distribution マニュアル 乱数分布を一様分布とする．constructor に a, b を指定すると，a以上b以下の一様分布． T は int や ll など．デフォルトは int． operator() は，引数に乱数発生器を取り，一様分布を生成する． 他の乱数分布クラスとコンストラクタの例: uniform_real_distribution<double> dist1(a, b); normal_distribution<double> dist2(mean, stddev);

AtCoder Regular Contest (ARC) 056 D - サケノミ についての記事です． 問題へのリンク 状況 解けないだけではなく，答を見てもなかなかわからなかったので，整理するために書いています．下記を参考にしています． 公式解説 kmjpさんのブログ 解法 時刻 $2j+1$ にドリンクを飲むような飲み方全部に関する，時刻 $2j+1$ 時点での美味しさの総和の最大値を $x(j)$ とする． 時刻 $2i$ に全部のグラスが空だったとき，半開区間 $(2i, 2j]$ に属する時刻に注がれるドリンクの美味しさの総和を $y(i, j)$ とすると， $x(j) = \max \{ x(i) + y(i, j) \mid i < j \} $ である．ここで，$z(i, j) = x(i) + y(i, j)$ と書くことにする．時刻 $j$ に注がれるドリンク全体の集合を $P$ とし，$ p \in P $ に対して時刻 $2j$ の一回前にドリンク $p$ が注がれる時刻を $l_p$ とする (時刻 j が初回なら，$l_p = 0$ とする)．すると，次が成り立つ．...

ABC237 Ex Hakata を解くのに必要だった Dilworth の定理他に関する記事です．