2020-08-05

University of Aizu Programming Contest 2012（AOJ 1508）RMQ

お題箱より。

解法

1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存在する要素のインデックスがずれます。そのため、インデックスに基づいて固定された構造を持つセグメント木では対応できません。

ではどうすれば良いのかというと、インデックスに依存しない構造を持つ平衡二分木を用いれば良いです。これなら要素の削除と追加ができます。

ということで、残りはこの問題と言うより平衡二分木の解説になってしまいますが…平衡二分木については非常に有名なスライドがあるのでこれを紹介します。

プログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～

平衡二分木の話は少し紛らわしくて、解説やサンプルコードなどを読む際には以下の2種類のどちらを目的としたものなのかを意識する必要があります。

C++の std::set のような順序付き集合としての機能。要素を順序付きで保持する。値の追加や削除、小さい方から $k$ 番目の要素の取得、大小関係に基づく二分探索、区間クエリの処理などができる。
数列の拡張としての機能。要素を列としての並びに基づいて保持する。 $k$ 番目の要素の取得・挿入・削除、区間クエリの処理などができる。

個人的には前者を特に「平衡二分探索木」と呼び、主に後者を指す時に「平衡二分木」という言葉を使うようにしていますが、競プロerの中でも確かな呼び分けがされていないように思います。先ほどのスライドで紹介されているTreapの実装は後者で、この問題で必要なのも後者です。

このスライドの実装に区間クエリの処理機能を追加します。やることはセグメント木と同様で、まず各ノードは自身以下の部分木の値を全てマージした計算済みの値（今回の問題では最小値）を常に持つようにしておきます。この値はスライドの実装の cnt や sum と同様に、自身以下の部分木が変化した時に計算し直せば良いです。

クエリ処理する時には根から再帰的に見ていって、各ノードは親に以下のような値を返すようにします。

対象ノード以下の部分木が受け持っているインデックス範囲が、
- クエリ対象範囲と全く重複していないならば、単位元を返す。
- クエリ対象範囲に完全に含まれているならば、計算済みの値を返す。
- そうでないならば、左の子が返した値、（もしノード自身のインデックスが範囲に含まれているならば自身の値、）右の子が返した値をマージした値を返す。

セグメント木とは異なり各ノードが受け持つインデックス範囲が固定されていませんが、部分木のサイズ cnt は分かるので、根から再帰的に呼び出すときに各ノードのオフセット（その部分木より左にいくつ要素があったか）を渡していくことで知ることができます。

ACコード

Aizu Online Judge

2020-08-04

AtCoder Beginner Contest 170 E - Smart Infants

AtCoder プログラミング競技プログラミング

お題箱より。実装方法に関するリクエストだったので実装中心で書きます。

E - Smart Infants

解法

解法としてはシミュレーションです。園児が移動したときに、どのようなデータを管理しておけば効率的に答えを更新できるかを考えます。

今回は以下のようなデータの流れを構築することにします。それぞれのデータに対してどのような操作が必要になるか順番に見ていきます。

f:id:betrue12:20200804105421p:plain

まず園児が移動するときに、レートいくつの園児がどこからどこに移動するのか分からないといけません。それを知るために各園児のレート A と所属幼稚園 B を管理します。必要な機能は数列の1点を取得または変更することなので、配列でOKです。

園児の移動は、「ある幼稚園から指定したレートの園児を1人削除」して、「ある幼稚園に指定したレートの園児を1人追加」する操作です。またその操作の前後で、幼稚園の最強園児のレートがいくつになったか分かる必要があります。つまり幼稚園ごとのレートの集合 st に求められる機能は

重複を含む値の集合を管理する。
ある値を1つ削除する。
ある値を1つ追加する。
集合内の最大値を調べる。

となります。

そしてこの変更で最強園児のレートが変わった場合、それを maxes に反映する必要があります。そして maxes の最小値が答えとなります。つまり maxes に求められる機能は、st とほぼ同様の

重複を含む値の集合を管理する。
ある値を1つ削除する。
ある値を1つ追加する。
集合内の最小値を調べる。

となります。このようにデータの流れを整理して各段階で必要な操作を列挙することで、各データをどのようなデータ構造で持てば良いのかが分かり、操作回数も合わせて見積もることで計算量を把握することができます。

あとは、この操作を効率的に行えるデータ構造を適切に選びます。

実現方法（C++）

C++であれば言語機能として std::multiset というものが提供されています。これを使うと、操作時点での要素数を $n$ として必要な操作は全て $O(\log n)$ で実現可能です。

これは値の集合を、順序（大小関係）を保持しながら管理してくれるデータ構造です。各操作は以下のように行うことができます。

st からある値 a を1つ削除する：st.erase(st.find(a))
st にある値 a を1つ追加する：st.insert(a)
st の最小値を求める：*st.begin()
st の最大値を求める：*st.rbegin()

存在しない値を削除しようとしたり、要素数 $0$ であるときに最小値や最大値を求めようとすると異常な挙動になる可能性があるので注意です。

begin()や rbegin() や find() などの関数によって得られるイテレータというものについては以下を参考にしてください。

C++のイテレータを視覚的に理解する（競プロ向け） - ARMERIA

実現方法（それ以外）

C++以外の言語の場合は少し面倒です。今回の場合、必要になる操作のうち

重複を含む値の集合を管理する。
ある値を1つ追加する。
集合内の最小値/最大値を調べる。

という操作であれば優先度付きキューで実現できるので、これに値を削除する仕組みを入れることを考えます。（Rubyなど優先度付きキューもない言語の場合は自作しましょう…）

具体的には、メインの優先度付きキューとは別に、「削除予約」をするための優先度付きキューを用意します。そして各操作は以下のように行います。

値を追加する：メインキューに値を追加する。
値を削除する：削除予約キューに値を追加する。
最小値/最大値を調べる：まず、メインキューと削除予約キューの最小値/最大値が一致する限り、それらをともに除外することを繰り返す。その後、メインキューの最小値/最大値を調べる。

ACコード

C++です。

Submission #15686906 - AtCoder Beginner Contest 170

2020-08-02

CPSCO2019 Session3 F - Flexible Permutation O(N^2)解法

AtCoder プログラミング競技プログラミング

お題箱より。 $O(N^{2})$ 解法が知りたいというリクエストだったので考えてみました。

F - Flexible Permutation

解法

後に扱うDPの都合上、個人的にはインデックスよりも値に注目したほうが理解しやすいので、条件を値中心の言葉に言い換えます。 $P_{i} \gt i$ であるような値 $P_{i}$ を「左に動いた」、 $P_{i} \lt i$ であるような値 $P_{i}$ を「右に動いた」、 $P_{i} = i$ であるような値 $P_{i}$ を「動かない」と呼ぶことにします。

まず、動かない値 $N-A-B$ 個を固定します。この選び方は $_{N}C_{N-A-B}$ 通りあり、これらの値を除くと残りは $A+B$ 個の必ず動く値だけを考えれば良いことになります。

公式解説の $O(N^{3})$ 解法と同様に、値を順番に足していきながら以前の値とswapしていくDPを考えます。ただしそのまま適用した場合、DPの途中では相変わらず「左に動いている」「右に動いている」「（一時的に）動いていない」値がいくつあるかという情報を管理する必要があり、状態数が落ちません。

そこで以下のようなものを数える包除原理を考えます。

予め指定したある $k$ 個の要素の集合について、値が動かない（違反状態である）。
$A$ 個の要素について、値が左に動く。
残りの $B-k$ 個の要素について、値が動かないか、または右に動く。

つまり「ちょうど $A$ 個の値が左に動く」という条件は絶対に満たすとして、 $B$ 個の要素について包除原理を適用する、ということです。こうすると先に $k$ 個の値を除いておけば、値の扱いで区別するべきものは「左に動いている」「それ以外」の2種類になり、状態数が $O(N^{2})$ に落ちます。

$dp\lbrack i \rbrack\lbrack a\rbrack =$ 既に $i$ 個の値を置いていて、そのうち左に動いている値が $a$ 個あり、それ以外の値が $i-a$ 個あるような並べ方の数

遷移は次に置く値を「そのまま右端に置いた」「左に動いている値とswapした」「それ以外の値とswapした」ときにそれぞれ $a$ がどのように変化するかを考えれば良いです。具体的には「それ以外の値とswapした」ときだけ $a$ が $1$ つ増えることになります。

包除原理に基づいて結果を集計します。違反状態として指定した要素の個数が $k$ である場合、その $k$ 個の選び方が $_{A+B}C_{k}$ 通り、残りの場所の置き方が $dp\lbrack A+B-k\rbrack\lbrack A\rbrack$ 通りあるので、これらの積に $(-1)^{k}$ を掛けて全て合計すれば良いです。最後に $_{N}C_{N-A-B}$ を掛けると答えになります。

ACコード

Submission #15585152 - CPSCO2019 Session3

2020-08-01

Educational Codeforces Round 92 F. Bicolored Segments

Codeforces プログラミング競技プログラミング

お題箱より。

Problem - F - Codeforces

問題概要

$n$ 個の閉区間 $\lbrack l_{i}, r_{i}\rbrack$ が与えられ、それぞれは赤または青のいずれか1色に塗られている。

「異なる色の2つの区間が共有点を持ってはいけない」という条件のもとで、これらのうちできるだけ多くの区間を選びたい。選ぶ個数の最大値を求めよ。

制約

$1 \le n \le 2\times 10^{5}$
$1 \le l_{i} \le r_{i} \le 10^{9}$

解法1：DP

あらかじめ区間を右端でソートしておき、右端の値が小さいものから順に見ていくDPを考えます。インデックスもソート後の順番で振り直します。

赤の区間を採用できる条件は、これまで最後に採用した青の区間の右端が、採用しようとしている赤の区間の左端よりも小さいことです。逆も然りです。なので素直に考えると、

$dp\lbrack i\rbrack\lbrack j\rbrack =$ これまで最後に採用した赤の区間が $i$ で、最後に採用した青の区間が $j$ であるときの、採用した区間数の最大値

というDPを構成することができます。区間を1-indexedで扱い、「まだその色の区間を採用していない」をインデックス $0$ で表すと都合が良いです。これで計算量 $O(n^{2})$ では解けますが、間に合いません。

ではどうするのかというと、さらに状態をまとめます。以下のように2色それぞれで状態をまとめ、区間を順番に見ていきながら同時に更新していきます。

$dp_{1}\lbrack i\rbrack =$ 今までに見た区間だけを使って、最後に採用した赤の区間が $i$ であるときの、採用した区間数の最大値
$dp_{2}\lbrack i\rbrack =$ 今までに見た区間だけを使って、最後に採用した青の区間が $i$ であるときの、採用した区間数の最大値

これは先ほどの $dp\lbrack i\rbrack\lbrack j\rbrack$ という2次元テーブルで管理していた状態について、それぞれの軸方向ごとに最大値を取ったものになります。このDPテーブルをどのように更新するのか考えます。

まず2次元テーブルを用いたDPがどのような遷移になるのか確認しましょう。見ようとしている区間が赤だとします。更新対象となるのは、最後に採用した青の区間の右端が見ようとしている赤の区間の左端よりも小さいものです。つまり $j$ がある値以下の範囲で更新が行われることになり、図で表すと以下のようになります。

f:id:betrue12:20200801153434p:plain

これを両軸方向に串刺しにして最大値を取った $dp_{1}, dp_{2}$ はどうなるでしょうか。図のインデックスを用いて説明します。まず $dp_{2}$ について考えると、更新対象となっている $dp_{2}\lbrack 0\rbrack, dp_{2}\lbrack 1\rbrack$ をそれぞれ $1$ 増やせば良いことが分かります。そして $dp_{1}\lbrack 3 \rbrack$ は増やした後のこれらの値の最大値になります。

つまり2次元テーブルで状態を管理しなくても、これらの $dp_{1}, dp_{2}$ だけで遷移を計算することができます。全ての区間を見終わったら、 $dp_{1}, dp_{2}$ のどちらか（どちらでもOK）について最大値を取ったものが答えになります。

必要な操作は区間への加算と区間の最大値取得なので、遅延伝播セグメント木などで実現することができます。

ACコード1

Submission #88638709 - Codeforces

解法2：二部グラフ

公式解説で解説されている方法です。

各区間を頂点とみなし、同時に採用してはいけない区間の間に辺を結ぶグラフを考えると、これは二部グラフになります。求めたいのはこのグラフの最大独立集合の頂点数です。

二部グラフでは最大独立集合の頂点数は全頂点数から最大マッチングの数を引いたものになります。つまり最大マッチングを求めれば答えを計算できます。

参考：二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！ - Qiita

ということで結局、赤と青の区間の組で共有点を持つものをなるべく多くマッチングさせることを考えれば良いです。これは例えば以下のように求めることができます。

赤の区間の左端と青の区間の右端を混ぜてソートする。値が同じ場合、赤の区間のほうが前になるようにする。
区間を順番に見ていきながら以下の処理を行う。
- 赤の区間の場合は、「マッチング待ち区間」として右端をプールする。
- 青の区間の場合は、プールされているマッチング待ち区間であって共有点を持つ（つまり右端が青の区間の左端以上である）もののうち、最も右端が小さいものを取り出しマッチングする。

このマッチング待ち区間のプールに必要な操作は「ある値を追加する」「プールに存在する値のうち、ある値以上で最も小さい値を取り出し、それを削除する」なので、C++であれば multiset 、このようなものが言語機能にない場合は座標圧縮＋BIT＋二分探索などで実現することができます。

ACコード2

Submission #88626147 - Codeforces

2020-07-12

エイシングプログラミングコンテスト 2020 F - Two Snuke

AtCoder プログラミング競技プログラミング

F - Two Snuke

公式解説とは違う解法です。

解法

$N \lt 5$ のときは答えは $0$ なので、 $N \ge 5$ とします。

まずは $O(N)$ 解法を

まず答えを $O(N)$ で求める方法を考えます。

$s_{1} + n_{1} + u_{1} + k_{1} + e_{1}$ の値を $x$ として、これを全通り試しましょう。そうすると、この $x$ を $5$ つに分ける分け方が $_{x+4}C_{4}$ 通りあります。 $x$ 個並んだボールを $4$ 本の仕切りで $5$ つの領域に分ける場合の数です。

$s = s_{2} - s_{1}$ として、 $n, u, k, e$ も同様に定義します。そうすると「全部足して $N$ 以下」という条件は $s + n + u + k + e \le N-2x$ と表記することができます。これを満たす $(s, n, u, k, e)$ の組それぞれについて $snuke$ （人名ではなく積です）を計算し、全て合計したものを求めたいです。これは、以下のような場合の数と等しくなります。

$N-2x$ 個のボールに $5$ 本の仕切りを入れて $s, n, u, k, e, (あまり)$ の $6$ つの領域に分け、さらに $s, n, u, k, e$ に相当する $5$ つの領域から $1$ つずつのボールを選ぶような場合の数。

これは言い換えると、ボールと仕切りを並べる合計 $N-2x+5$ 箇所のスペースから、仕切りと選んだボールに相当する $10$ 箇所を選び、その $10$ 箇所には左から順に「選んだボール、仕切り、…、選んだボール、仕切り」と割り当てるような場合の数に等しいです。つまり、この値は $_{N-2x+5}C_{10}$ と計算できます。

$x$ の範囲としては $s, n, u, k, e$ が全て正になれるもの、つまり $N-2x \ge 5$ である範囲を考えます。そうすると答えは

$\displaystyle \sum_{x=0}^{\lfloor\frac{N-5}{2}\rfloor} \left({}_{x+4}C_{4} \times {}_{N-2x+5}C_{10}\right)$

と計算することができます。階乗を前計算して $x$ についてループを回すことで $O(N)$ で解くことができますが、間に合いません。

偶奇に分けて多項式と見る

先ほどのシグマの中身を見てみましょう。 ${}_{x+4}C_{4}$ という値は、具体的には $\frac{1}{24}(x+4)(x+3)(x+2)(x+1)$ という $x$ についての $4$ 次多項式です。同様に ${}_{N-2x+5}C_{10}$ は $(N-2x)$ についての $10$ 次多項式です。つまりシグマの中身は $x$ と $N$ についての $14$ 次多項式です。より正確には、全ての項で $x$ と $N$ の次数合計が $14$ 以下であるような多項式となっています。

ここで重要な性質として、 $x$ についての $d$ 次多項式の値を $x=0, ..., n$ まで合計したものは $n$ についての $d+1$ 次多項式になります。

今回の計算式におけるループ終端は $\lfloor\frac{N-5}{2}\rfloor$ でした。このままでは扱いにくいので $N$ の偶奇で場合分けします。例えば $N$ が奇数である場合、 $n = \frac{N-5}{2}$ と置きます。そうするとループの終端は $n$ となり、 $N$ を $2n+5$ で置き換えるとシグマの中身は $x$ と $n$ についての $14$ 次多項式になります。先ほどの性質から、このシグマを処理した結果は $n$ についての $15$ 次多項式になることが分かります。

具体的に冪乗和の公式を当てはめて大量の計算をすればこの多項式の係数が求められますが、絶対にやりたくないです。「ラグランジュ補間」という方法を使いましょう。これは「 $n$ についての $d$ 次多項式 $f(n)$ の自由度は $d+1$ であり、 $d+1$ 通りの相異なる点 $(n, f(n))$ から多項式を一意に決定することができる」という性質を用いるものです。特に相異なる既知の点として $n=0, 1, ..., d$ に対する $f(n)$ を用いた場合、1つの未知の $n$ に対する $f(n)$ の値は $O(d)$ で計算することができます。

つまり、 $n=0, 1, ..., 15$ （すなわち $N=5, 7, ..., 35$ ）に対する答えをそれぞれ $O(N)$ で計算し、これらを用いてラグランジュ補間を行えば、入力 $N$ が奇数である場合の答えを高速に求めることができます。

$N$ が偶数である場合も $n = \frac{N-6}{2}$ と置くことで同様に計算することができます。

ACコード

Submission #15191688 - AIsing Programming Contest 2020

ラグランジュ補間のライブラリを持っていれば実装は楽です。ラグランジュ補間の実装は、長くはないですが計算式がややこしいです。

実は $N \ge 5$ かどうかを場合分けせずに $N=0, 2, ...$ または $N=1, 3, ...$ の結果からラグランジュ補間しても良いのですが、一応説明に従い場合分けをしています。

2020-07-07

Codeforces Round #654 (Div. 2) E2. Asterism (Hard Version)

Codeforces プログラミング競技プログラミング

Problem - E2 - Codeforces

問題概要

長さ $n$ の数列 $a = \lbrace a_{0}, ..., a_{n-1} \rbrace$ と素数 $p$ が与えられる。まず、以下の問題を考える。

整数 $x$ が与えられる。 $\lbrace 0, 1, ..., n-1\rbrace$ を並び替えた順列 $q_{0}, ..., q_{n-1}$ であって、全ての $i$ について $a_{q_{i}} \le x + i$ が成り立つようなものは何通りか？

この問題の答えが $p$ の倍数とならないような $x$ を全て列挙せよ。

制約

$2 \le p \le n \le 10^{5}$
$1 \le a_{i} \le 10^{9}$

解法

説明と実装を合わせるために0-indexedで表記します。また、与えられた数列 $a$ をソートしておきます。

まず数え上げ問題の答えがどうなるかを考えます。 $i$ 番目（最初を $0$ 番目とします）の選択において $q_{i}$ として選べるインデックス $k$ の候補は、 $a_{k} \le x+i$ が成立するものから、 $q_{i-1}$ までで既に使っている $i$ 個を除外したものです。この選択肢の数は $x$ が増えるほど増えていき、それ以前の選択で何を選んだかに依存しません。 $n$ 個全てにおける選択肢の個数の積が数え上げ問題の答えになります。