ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder LibraryのLazy Segtreeのチートシート

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

こちらの記事でAtCoder LibraryのLazy Segtreeの使い方を説明しましたが、コンテスト中に読んでられっか!みたいな時のためにコピペで使えるチートシートをまとめます。整数列に対する、以下の組み合わせ6種類です。

  • 区間変更クエリ:加算、更新
  • 区間取得クエリ:最小値、最大値、和

オーバーフローで死なないように整数列の要素を long long で扱っています。また INF および ID として  8\times 10^{18} を使います。

区間加算・区間最小値取得

AOJ(RMQ and RAQ)提出:Aizu Online Judge

using S = long long;
using F = long long;

const S INF = 8e18;

S op(S a, S b){ return std::min(a, b); }
S e(){ return INF; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    int N;
    std::vector<S> v(N);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

区間加算・区間最大値取得

using S = long long;
using F = long long;

const S INF = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    int N;
    std::vector<S> v(N);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

区間加算・区間和取得

区間幅が必要なので値を構造体で持ちます。seg.prod(l, r).value で値を取り出してください。

AOJ(RSQ and RAQ)提出:Aizu Online Judge

struct S{
    long long value;
    int size;
};
using F = long long;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    int N;
    std::vector<S> v(N, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

区間変更・区間最小値取得

AOJ(RMQ and RUQ)提出:Aizu Online Judge

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::min(a, b); }
S e(){ return INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

int main(){
    int N;
    std::vector<S> v(N);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

区間変更・区間最大値取得

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

int main(){
    int N;
    std::vector<S> v(N);
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

区間変更・区間和取得

区間幅が必要なので値を構造体で持ちます。seg.prod(l, r).value で値を取り出してください。

AOJ(RSQ and RUQ)提出:Aizu Online Judge

struct S{
    long long value;
    int size;
};
using F = long long;

const F ID = 8e18;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){
    if(f != ID) x.value = f*x.size;
    return x;
}
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

int main(){
    int N;
    std::vector<S> v(N, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

AtCoder LibraryのLazy Segtreeの使い方

AtCoder Libraryが遅延伝播機能を持つセグメント木 atcoder::lazy_segtree を提供しているものの、何か渡すものいっぱいあるしドキュメントは数学用語だらけだしよく分からん!みたいな人向けの記事です。

問題を解いていて、セグメント木に必要な機能(区間加算操作と区間最小値取得がしたい!みたいな)が明確になったときに、それを実現するためには atcoder::lazy_segtree の生成時に何を渡せばいいかを考えられるようになることがこの記事の目標です。ただしコンテスト中に読める分量ではなくなったので、整数列に対する単純な機能の組み合わせについてはコピペで使えるチートシート的なものを別途作る予定です。→作りました

対象読者は「セグメント木(抽象化も遅延伝播もナシで可)を書いたことがあって、その構造と動作の仕組みについて何となく理解している人」くらいを想定しています。もちろん遅延伝播の仕組みと内部実装を知っておくに越したことはないので、以下の記事を読んでおくことをオススメします。私もこの記事で勉強しました。

遅延評価セグメント木をソラで書きたいあなたに - hogecoder

また、この記事を書こうと思ったきっかけはお題箱の「AOJのRSQ and RUQをAtcoder Libraryでどう解けばいいか」というリクエストでした。その答えは最後のほうに書いています。

AtCoder Libraryの公式ドキュメント

https://atcoder.github.io/ac-library/document_ja/lazysegtree.html

遅延伝播セグメント木の機能

遅延伝播セグメント木を使うと、整数列などのデータ列  a_{0}, ..., a_{n-1} に対して以下の2つのクエリを処理できるようになります。

  • 区間変更クエリ:指定した区間内のデータ  a_{l}, ..., a_{r-1} それぞれに対して、一様に何らかの変更操作を行います。
  • 区間取得クエリ:指定した区間内のデータ  a_{l}, ..., a_{r-1} に対して何らかの計算を行った結果を得ることができます。

例えばこういう問題が解けるようになります。

変更クエリ・取得クエリでそれぞれどういう処理を行うかは解きたい問題によって変わります。atcoder::lazy_segtree は生成時にこれらの処理内容をプログラマーが与えることで、1つのライブラリで様々なクエリの組み合わせを実現できるようになっています。これは非常に便利で強力である反面、使い方が難しくなりがちです。この記事ではその使い方を学びます。

またやりたい処理が何でもかんでもセグメント木で扱えるわけではなく、特定の性質を満たしている必要があります。そのことについても終わりの方で説明します。

遅延伝播の仕組み

遅延伝播セグメント木はこんな形をしています。

f:id:betrue12:20200922142356p:plain:h300

区間を担当する各ノードが data と lazy の2つの値を保持しています。 atcoder::lazy_segtree の内部実装ではそれぞれ dlz です。

  • data:一番下のノードは列の各要素を保持する。その上にあるノードは、受け持つ区間の要素に対して取得演算を行った結果(区間最小値取得の機能を持つセグ木なら、その区間の最小値)を保持する。
  • lazy:その区間に対して行われた操作のうち、まだ自身より下のノードに作用させていないものを保持する。

data は通常のセグメント木と同じです。lazy が遅延伝播のキモで、操作をすぐに全ノードに伝播させず、必要になるまで上側にあるノードが溜めます。逆に言えば各ノードが持っている data は、自身の上にあるノードたちが lazy として溜めている操作が全て降りて来るまでは正確な(最新の)値とは限らない、ということです。

※そのため、もう伝える先がない末端のノードの lazy は実際には不要です。AtCoder Libraryの内部実装でもここの領域は確保されていません。

ある広い区間に対して何度も操作クエリが行われた時、それを末端のノードまで毎回伝えていくと計算量が増えてしまいます。なのでノード全体を覆うような操作はそのノードがずっと溜めておいて、その中のより狭い区間に対するクエリが来たときに初めて下に伝えていく。これが遅延伝播の仕組みです。

f:id:betrue12:20200922195813p:plain

とりあえずここまで理解できればOKです。atcoder::lazy_segtree に渡す型や関数の説明ができるようになります。

テンプレート引数の作り方

atcoder::lazy_segtree のコンストラクタは以下のように定義されています。

(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);

具体例として「整数の数列に対する、区間加算操作と区間最小値取得」の機能を持つセグメント木を作るために、<> の中のテンプレート引数として何を渡すべきか考えてみましょう。この例にしたのはイレギュラーなパターンが一番少ないからです。

SF

S は data、つまり各要素および区間取得結果の型です。整数の数列なら intlong long などです。

F は lazy、つまり操作(写像)を表す値の型です。整数を加算する操作なら同じく intlong long などです。

今回の場合は両方 int とします。int と直接書いても良いですし、using S = int; などと別名を付けて S と書いても良いです。

S op(S a, S b)

区間取得をどのような演算で行うかを定義します。通常のセグメント木と同じです。

ドキュメントの使用例にあるように、関数を別途定義してその関数名を引数に書けば良いです。区間最小値取得なら S op(S a, S b){ return std::min(a, b); } を作って op を渡します。ドキュメントの関数名と合わせる必要はありません。

S mapping(F f, S x)

操作 f を各ノードが持つ data の値 x に対して作用させる関数です。この mapping と次の composition が、先ほど伝播の仕組みを説明した図においてどこに該当するかを示します。

f:id:betrue12:20200922195827p:plain

区間加算操作・区間最小値取得の場合を考えます。末端のノードの data は数列の各要素1つに該当するので、加算操作では単に fx に足せば良いです。ですがここでは「上側のノードが持つ値、つまり既に取得演算をしてしまった値に対して操作しても大丈夫か?」という点に注意する必要があります。

例えば区間  \lbrack 0, 4) を受け持つノードは data として  \min(a_{0}, a_{1}, a_{2}, a_{3}) の値を保持しています。この区間に対して「区間内の全要素に整数  f を加算する」という操作を行うと、この data の値は  \min(a_{0}+f, a_{1}+f, a_{2}+f, a_{3}+f) = \min(a_{0}, a_{1}, a_{2}, a_{3}) + f となります。

同様にどのノードであっても、操作 f を行った時には元々持っていた data の値に f を足せば良いです。そのため mapping の定義は S mapping(F f, S x){ return x+f; } となります。

区間和取得の機能を持たせる場合は少し面倒です。後で説明します。

F composition(F f, F g)

既にこれまでの操作を溜めている lazy に対して、さらに新しい操作を追加する関数です。g がこれまでの操作、f が後に追加する操作で、「その2つの操作を順に行うようなひとまとめの操作(合成写像)」を返します。

区間加算操作の場合、「g を足す」という操作の後に追加で「f を足す」という操作は、合わせると結局「f+g を足す」という操作になります。なので composition の定義は F composition(F f, F g){ return f+g; } とします。

今回の場合は足し算が可換な演算なので気にしなくても良いですが、可換でない場合には順番に注意しましょう。f のほうが後の操作です。

S e()F id()

それぞれ、区間取得演算 op単位元区間操作演算 mapping における恒等写像を返す関数です。関数として渡す仕様になっていますが、この値がプログラムの途中で変わることはほぼないので定数を返す関数を作れば良いです。

二項演算 op単位元 e とは、全ての a に対して op(a, e) = op(e, a) = a を満たすものを指します。区間最小値取得の場合は「(自身相手でない限り)絶対に最小値として採用されないような値」、つまり  \infty とすれば良いです。実装上は data が取り得ないような十分大きな整数を使います。例えば data が最大で  10^{9} までの値を取り得る場合、S e(){ return int(1e9)+1; } とすれば良いです。

操作を行う関数 mapping における恒等写像 id とは、全ての a に対してmapping(id, a) = a となるものを指します。区間加算操作の場合は「足しても絶対に対象の値を変えないような値」、つまり  0 を使います。F id(){ return 0; } とすれば良いです。

よく使う単位元や恒等写像として、最小値であれば  +\infty 、最大値であれば  -\infty 、和や加算であれば  0、積や乗算であれば  1 を使えば良いです。更新操作の場合は?恒等写像がないですね。後で説明します。

完成!

これで全部の型と関数が定義できました。以下のように使うことができます。

using S = int;
using F = int;
S op(S a, S b){ return std::min(a, b); }
S e(){ return int(1e9)+1; }
S mapping(F f, S x){ return x+f; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    std::vector<int> v = {0, 1, 2, 3, 4};
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

変数名として使いたい S とか e がグローバルに置いてあると何かと面倒だと思うので、適宜名前は変えて良いです。

注意すべきケース

いくつか注意すべきケースを説明します。

区間和を取る場合の mapping

区間加算操作・区間取得の機能を持たせる場合の mapping の実装を考えます。

区間  \lbrack 0, 4) を受け持つノードの data の値は  a_{0} + a_{1} + a_{2} + a_{3} です。ここに「区間内の全要素に  f を加算する」という操作を行うと、その値は  a_{0} + a_{1} + a_{2} + a_{3} + 4f となるべきです。つまり元々持っていた値に  f \times (区間の幅) を足す必要がありますが、mapping の引数では区間の幅が渡されていません。

この場合は公式ドキュメントの使用例に倣い、data のほうに区間の幅を持ちます。例えば data の型 S

struct S{
    int value;   // 実際の値
    int size;    // 区間の幅
};

という構造体で定義します。末端の要素については data[k].size = 1 として、区間取得の演算を S op(S a, S b){ return {a.value + b.value, a.size + b.size}; } とすれば、各ノードが持つ区間幅が適切に求められます。

これで区間幅が使えるので、区間加算操作は S mapping(F f, S x){ return {x.value+x.size*f, x.size}; } と実現することができます。

注意点として、必ず全要素の size を  1 にセットした vector を渡して初期化してください単位元の size は  0 とするので、要素数を渡して初期化してしまうと全ての data の値が単位元になり、区間幅が全て  0 になってしまいます。

以上の内容を踏まえた、区間加算操作・区間和取得の機能を持つセグメント木の定義の全体像を示します。

struct S{
    int value;
    int size;
};
using F = int;
S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {x.value+x.size*f, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    int n = 5;
    std::vector<S> v(n, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

応用的な使い方として、例えば座標圧縮をしたことで各末端ノードが受け持っている実際の長さが  1 とは限らない時も、この size に入れておくと各ノードが受け持つ実際の長さが分かります。操作対象の数列の要素数がクエリ数に対して非常に多い場合に有効です。

区間更新操作の恒等写像

区間中の値を全てある値  x に更新する」という区間更新操作と、区間和取得の機能を持たせる場合を考えます。この場合恒等写像を表現できる値がないので困ります。

何通りか解決方法があって、「lazy の値として取り得ないような値を擬似的に恒等写像として扱う」方法と、「更新すべき値が存在する(恒等写像でない)かどうかのフラグをbool値で持つ」方法があります。今回は型を変えなくて良い前者を紹介しますが、「その値が lazy として本当に取り得ないか?」という点には十分注意してください。

擬似的に恒等写像として扱う値を ID とします。このとき写像を扱う関数である mappingcomposition はそれぞれ以下のようになります。

  • S mapping(F f, S x)fID ならばそのまま x を返す。そうでなければ区間内の値全てを f に変更するので、x.value = x.size * f とする。
  • F composition(F f, F g)fID ならばそのまま g を返す。そうでなければ、後からの操作で上書きされるので f を返す。

区間和取得を考える場合、先ほどと同様に区間幅が必要な点に注意してください。

以上の内容を踏まえた、区間更新操作・区間和取得の機能を持つセグメント木の定義の全体像を示します。

struct S{
    int value;
    int size;
};
using F = int;
const F ID = int(2e9);
S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){
    if(f != ID) x.value = x.size * f;
    return x;
}
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

int main(){
    int n = 5;
    std::vector<S> v(n, {0, 1});
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

これを用いてAOJの「RSQ and RUQ」を解いたコードが以下です。

Aizu Online Judge

bool値でフラグを持つ場合は、F の型を S と同じように構造体にしたり pair<int, bool> にしたりします。実装はだいたい同じで、最初にフラグを見て恒等写像であれば更新せずに返すという処理をします。

「セグ木に乗る」とは

やりたい演算がセグメント木に乗るとか乗らないとかいう話は、結局のところこれらの関数 op mapping composition を適切に定義できるかどうか?という点に尽きます。単位元と恒等写像はどうにでもなるので。

op は通常のセグメント木にも存在する取得クエリの演算で、これが結合法則を満たすことがまず必要です。この説明はこちらの記事に詳しく書いています。

遅延伝播を行う時にはそれに加えて、以下の2つの性質を満たすような関数を見つける必要があります。

  • mapping:操作を、全てのノードが持つ data に同じ計算式で作用させることができること。このとき区間幅など必要な情報を data 側に持たせて補うのはOK。
  • composition:複数の操作を連続して行うという操作(合成写像)を、あたかも1回の操作であるかのように扱って lazy に持たせることができること。

最後に

かなりの分量になりました。セグメント木として実現したい機能をどういう風に分解して関数を作っていけば良いか、理解する助けになれば幸いです。

Practice Contestの問題では2問とも変なものを乗せていますが、まずは整数列に対する単純な演算を実現できるよう色々練習していくのが良いと思います。AOJの区間クエリ問題集などが良いでしょうか。徐々に慣れていって、いずれは変なものを乗せられるようになりましょう。

Educational Codeforces Round 11 E. Different Subsets For All Tuples

お題箱より。

Problem - E - Codeforces

公式解説より楽な解法があるのでそっちを紹介します。記事最後に、リクエストにあった公式解説の補足についても説明します。

問題概要

整数列  a に対して、 f(a) を「 a の部分列(連続でなくても良い)として登場する長さ  0 以上の相異なる数列の個数」と定義する。

各要素が  1, ..., m のいずれかであるような長さ  n の数列は  m^{n} 個ある。その全てについて  f(a) の値を合計した値を  \bmod 10^{9}+7 で求めよ。

制約

  •  1 \le n, m \le 10^{6}

解法

※解説中の「数列」という言葉は、特に断らない限り各要素が  1, ..., m のいずれかであるようなものを指すことにします。

数え方についての考察

 f(a) の計算ルールとして、相異なる部分列の個数を数えるので、例えば  \lbrack 1, 2, 1, 3, 1, 2, 3\rbrack \to \lbrack 1, 2, 3\rbrack のように複数の取り出し方で同じ部分列ができる場合にも  1 通りとして数える必要があります。このときによく使うのが、「その部分列を取り出す位置の組み合わせのうち、最も左側から取り出すようなものだけを数える対象とする」、という考え方です。先ほどの例の場合は(先頭を  0 番目として) 0, 1, 3 番目が最も左側から取り出す位置になります。

これを踏まえて、ある長さ  k の数列  s があった時に、それを部分列として含む長さ  n の数列  a を数える方法を考えます。まず、先ほど考えた「最も左側から取り出す」取り出し方で  s の各要素に対応する  a の位置を決めたとします。そうすると  a の各要素の値の候補数は、

  •  s の要素に対応している: 1 通り
  •  s の要素に対応していない&それ以降に  s に対応する要素がまだ存在する: m-1 通り
  •  s の要素に対応している&それ以降に  s に対応する要素がもう存在しない: m 通り

となります。 2 番目が  m-1 通りとなる理由は、もし  s における次の要素と同じ値を採用してしまった場合、そこから取り出したほうがより左側になってしまうので、「最初に決めた位置が最も左側から取り出す位置である」という決め事に反するからです。

この  a が何通りあるかは、 s の要素に対応する最後の位置が何番目であるかによって変わってきます。公式解説ではこの「 s の長さはいくつか」「 s の要素に対応する最後の要素は  a の何番目か」を組み合わせた2重和を考えていますが、別の方法があります。DPをしましょう。

DPをする

取り出し元の数列  a と部分列として取り出す数列  s の組  (a, s) をDPで数えます。 a の要素数 1 つずつ増やしていきながら、 s の要素数を増やすパターン、増やさないパターンのそれぞれの遷移をします。

先ほど見たように、 s の要素に対応していない  a の要素の候補数は、まだ  s に対応する要素が残っているかどうかで変化します。なのでこれを考慮し、次のような状態定義をします。

  •  dp\lbrack i\rbrack\lbrack 0\rbrack = 長さ  i の数列  a と、その部分列である長さ  0 以上の数列  s の組であって、今後  s の要素を増やす予定のもの
  •  dp\lbrack i\rbrack\lbrack 1\rbrack = 長さ  i の数列  a と、その部分列である長さ  0 以上の数列  s の組であって、もう  s の要素を増やさないもの

その時点での  s の長さは持たなくても良い、という点が1つの注目ポイントです。

 dp\lbrack i\rbrack からの遷移は以下のように列挙できます。

  •  dp\lbrack i\rbrack\lbrack 0\rbrack から、 a の要素を末尾に  1 つ増やし、 s の要素としては採用しない: m-1 を掛けて  dp\lbrack i+1\rbrack\lbrack 0\rbrack に遷移
  •  dp\lbrack i\rbrack\lbrack 0\rbrack から、 a の要素を末尾に  1 つ増やし、それを  s の要素としても末尾に追加する: m を掛けて、 dp\lbrack i+1\rbrack\lbrack 0\rbrack(まだ終わらない)と  dp\lbrack i+1\rbrack\lbrack 1\rbrack(これで終わり)の両方に遷移
  •  dp\lbrack i\rbrack\lbrack 1\rbrack から、 a の要素を末尾に  1 つ増やし、 s の要素としては採用しない: m を掛けて  dp\lbrack i+1\rbrack\lbrack 1\rbrackに遷移

初期条件は  dp\lbrack 0\rbrack\lbrack 0\rbrack = dp\lbrack 0\rbrack\lbrack 1\rbrack = 0 とすれば良いです。後者は  s として何もない状態からもう要素を増やさない、つまり空数列に対応します。答えは  dp\lbrack n\rbrack\lbrack 1\rbrack になります。

これなら  O(n) で解くことができます。

ACコード

Submission #93359107 - Codeforces

おまけ:公式解説の式変形について

元々のリクエスト内容である公式解説の式変形についても触れておきます。まず、最初に立式された

 \displaystyle \sum_{k=1}^{n}\sum_{j=0}^{n-k}\cdots

という2重和は、 k, j を2軸とする2次元平面において以下のような三角形の領域について値を全て合計しています。

f:id:betrue12:20200921043132p:plain

この領域を、 s=j+k と置いた  s が一定の領域、つまり斜めに切って和を取るように変形しています。その上で元々の  k 1 ずらすと、次の式である

 \displaystyle \sum_{s=1}^{n}\cdots\sum_{k=0}^{s-1}\cdots

という形になります。式の中身も「 s=j+k である」「 k は元々の  k から  1 ずれている」と思うと変形を追いやすくなると思います。

あとは最後の二項係数の計算

 \displaystyle \sum_{k=0}^{n} {}_{r+k}C_{k} = {}_{r+n+1}C_{n}

ですが、これはグリッド上の経路数の問題として理解することができます。 (r+1) \times n マスのグリッドで左下から右上に行く経路を直接計算したものが右辺、図のように分解して足し合わせたものが左辺です。

f:id:betrue12:20200921043116p:plain

キーエンス プログラミング コンテスト 2020 D - Swap and Flip

お題箱より。

D - Swap and Flip

解法

この問題のように「操作する場所を選んで、決められたルールに従って操作する」ということを繰り返す問題では、1回目の操作の選択、2回目の操作の選択…といった分岐パターンを直接探索していくのは非常に大変です。操作の途中過程を考えなくて良いような戦略をいかに立てるかが重要です。例えば、

  • 操作の過程に関わらず、常に成り立っている性質や不変な量が存在する。
  • 最終状態だけが分かれば、操作の過程を考えなくても、操作について求めたい値(最小の操作回数や操作コストの合計値、その最終状態が実現できるかどうかのYes/No判定など)が分かる方法が存在する。

というような嬉しい性質がないかを考察してみましょう。

考察1

「隣り合う2枚のカードを選び、位置を入れ替え、それぞれ裏返す」という操作の特徴を考察します。どのカードも位置が1つ移動するごとに表裏が入れ替わるので、元々あった位置と最終的な位置の差(移動距離)が偶数ならば表向き、奇数ならば裏向きになります。これはつまり、どのような操作過程を辿ったとしても、最後の各カードの位置を決めれば全てのカードの向きが一意に決まることを意味します。

考察2

最後の各カードの位置を決めたとします。初期状態からその位置に並べ替えるための操作回数の最小値は、各カードの番号(=初期位置の並び順)を最後の位置に並べてできる順列の転倒数という値になります。すなわち「2つのカード番号  (i, j) の組であって、 i \lt j かつカード  i よりもカード  j のほうが左にあるものの個数」です。

転倒数の求め方として、左から順番に要素を見ていきながら「自身より左側に登場済みで、かつ自身より小さい要素」の個数を合計していくという方法があります。図のように今見ている要素を  i、左側に登場済みで  i より大きい要素を  j とすると、組  (i, j) は先ほどの条件を満たします。これを合計していくことで転倒数を求めることができるため、各ステップでは既に登場した要素の集合だけを覚えておけば転倒数の増加分を計算することができます

f:id:betrue12:20200917185311p:plain

DPを組む

ここまでの考察を使って答えを求める方法を考えます。考察1、2で確認したように操作の途中経過については考える必要がないので、最終状態の並び順をいきなり考えてしまって良いです。

 N が小さいことから、「今までどのカードを置いたか」の集合を持ちながら1つずつ順に置くカードを決めていく、いわゆるbit DPを考えることができます。左から順番に置くカードを決めていくとすると、必要な情報は

  • 今までどのカードを置いたか?
  • 最後に置かれたカードはどれか?
  • そこまでの転倒数はいくつか?

の3点です。以下のようにDPの状態を定義します。

 dp\lbrack s \rbrack\lbrack x\rbrack = 既に置いたカードの集合が  s であって、最後に置かれたカードが  x で、既に置いたカードの表向きになっている値は広義単調増加になっているときの、そこまでの転倒数の最小値

 dp\lbrack s \rbrack\lbrack x\rbrack からの遷移として、次に置くカードの候補  y を全て試します。このとき調べる必要があるのは

  • 単調増加性は守られるか?(=その遷移をしてもよいか?)
  • 転倒数はいくつ増加するか?

の2点です。単調増加性については考察1より、最後に置かれたカード  x と次に置くカード  y の向きが移動距離の偶奇から決まるので実際に値を比較して判定できます。転倒数の増加分については考察2より、既に置かれたカードの集合  s の中で  y よりも番号の大きいものを数えれば良いです。遷移先は  dp\lbrack s\cup \lbrace y\rbrace \rbrack\lbrack y\rbrack で、bit DPの代表例として紹介される巡回セールスマン問題に似た実装をすることになります。

このDPを計算し終わったら、カード全体の集合を  U=\lbrace 1, 2, ..., N\rbraceとして、 \min_{x} dp\lbrack U \rbrack\lbrack x\rbrack が答えです。

ACコード

Submission #9569271 - Keyence Programming Contest 2020

時間計算量は  O(N^{2}2^{N}) です。転倒数の増加分を計算する時に毎回全要素を見ていると  O(N^{3}2^{N}) になるので少し工夫しましょう。予め全ての  (s, y) に対して「集合  s の中で  y よりも番号の大きいものの個数」を前計算しても良いですし、上記リンク先のコードでは次に置くカード  y を小さい番号から順に見ていきながら、増加分の変化を管理しています。

AtCoder Beginner Contest 178 F - Contrast

F - Contrast

解法が色々ある問題。シンプルで実装も楽な解法1と、私が本番で解いた解法2を証明付きで紹介します。前者のほうが断然オススメ。

解法1

まず  A, B 合計で  N 個を超える値が存在する場合、どのように並べても  A_{i} = B_{i} となる箇所が存在してしまいます。この場合は No を出力して終了します。以降は、どの値の登場数も  A, B 合計で  N 個以下であるとします。

突然ですが  B を反転させて降順ソート状態にします。この状態で  A B を並べてみると、 A_{i} = B_{i} となっている値は高々1種類だけであることが言えます。もし2種類以上の異なる値がそれぞれ同じ位置にある場合、それらは  A B において同じ位置関係で並んでいるということになり、「片方は昇順、片方は降順」という前提に反するからです。

 A_{i} = B_{i} となっている値が存在しない場合はこの  B が答えです。もし A_{i} = B_{i} となっている値が存在する場合、その値を  x として、 A_{i} B_{i} x でないような両端の領域を探します。この領域内の  B_{i} と、 x が被っているところの  B_{i} を1つずつ組にしてスワップしていけば完成です。スワップする両者の位置はどちらも「 A_{i}, B_{i} のうち片方は  x で、もう片方は  x でない」という状態になるのでこれで条件を満たします。

f:id:betrue12:20200914232651p:plain

この両端の領域の要素数が、 x が被っている領域の要素数以上であることを示します。上の図のように長さ  a, b, c, d, e を定めると、

  • 図より、 a+b+c+d+e = N
  •  x の登場数が合計で  N 個以下であることから、 b+2c+d \le N

であるので、不等式を変形することで  a+e \ge c を示すことができます。以上でこの構築の正当性が証明されました。

ACコード1

Submission #16762957 - AtCoder Beginner Contest 178

解法2

 A, B 合計で  N 個を超える値が存在する場合は No である、という点は同じです。

 A B も並び替えができる、と想定して解きます。最後に出力する時に、 A の各要素が元々並んでいた位置に合わせて対応する  B の要素を並べれば良いです。

各値について  A, B それぞれの出現数を調べます。そして以下の図に示すように、 B のほうが多い値を左側に、 A のほうが多い値を右側に、同じ順序で  A, B ともに並べ替えます。そして各値について「 A B についてその値が被っている長さ」を調べ、その長さだけ  B を右に巡回シフトすれば完成です。

f:id:betrue12:20200914225731p:plain

この解法の正当性を証明します。左にある値から順に見ていくと、 B の方が多い値を全部先に使っているので、各値を入れる前後では常に  B の要素数のほうが多く(または等しく)なっています。より具体的には、全ての値について

  • (その値が  A に登場する左端) \le (その値が  B に登場する左端)
  • (その値が  A に登場する右端) \le (その値が  B に登場する右端)

が成立しています。図の①のほうの状況です。

この状態で被っている長さが最大であるような値を  x とします(図では青く塗っている  x=2 2 つ被っています)。その長さだけ  B を右シフトすると、全ての値について元々被っていた領域は切断されて被らなくなります。また1周して  B 側の右端と  A 側の左端がくっつくこともありません。 x 以外の値が1周してくっつくためには  x が被っていた領域を超える必要があり、これは無理です。また  x についても、その登場数が合計  N 個以下であることからあり得ません。

以上でこの構築の正当性が証明されました。

ACコード2

Submission #16762983 - AtCoder Beginner Contest 178

Codeforces Round #670 (Div. 2) E. Deleting Numbers

Problem - E - Codeforces

問題概要

インタラクティブ問題である。

まず正整数  n が与えられる。ジャッジは  1 以上  n 以下の整数  x を持っている。また集合  s があり、初期状態では  s=\lbrace 1, 2, ..., n\rbrace である。

以下のクエリを合計  10000 回まで投げることができる。 x の値を特定し、Cクエリで解答せよ。

  • A  a s に含まれる  a の倍数の個数が返答される。
  • B  a s に含まれる  a の倍数の個数が返答される。その後、 s に含まれる  a の倍数のうち  x でないものが  s から消去される。 a \gt 1 でなければならない。
  • C  a x の値は  a であると解答する。このクエリは  1 回しか発行できない。

制約

  •  1 \le n \le 10^{5}

解法

 x を絞り込んでいく基本方針としては、まずBクエリを投げて集合を変化させます。このとき「もし今までBクエリで投げた値の倍数が全部消えていれば、集合にはこの値が残っているはず」という状態を自分で管理しておきます。そしてAクエリ(Bクエリでも可)を投げて、返ってくる値が自分で管理している値と合わないならば、「これまで投げたBクエリの中に  x の約数が存在し、今投げたAクエリの値も  x の約数である」ということが分かります。このように情報を得るには「消去を試みる→残っているかチェック」という2段階が必要です。

クエリ数  10000 は潤沢に見えますが、実際はほとんどの個数を「素数へのBクエリ」に使わないといけません。なぜなら  x素数である場合、それを識別するためにはその素数そのものについてBクエリを投げる必要があるからです。10万以下の素数 9592 個なので、残り  400 回程度しか使えません。

また素数についてのBクエリを投げた後、その結果を確認するAクエリも必要です。再び素数全部についてAクエリを投げ直す余裕はないので、これは必然的に A 1 というクエリでまとめて確認することになります。

そのため素数をいくつかのグループに分けて、「1グループの素数全てについてBクエリを投げる→A 1 でチェック」という処理を繰り返すことにします。冒頭に書いた方法でAクエリの結果を照合し、自分で管理している値と合わないのであれば、このグループの中に  x の素因数が存在します。そのためグループ内の素数  p 全てについて改めて A  p というクエリを投げて  x の素因数かどうかを判定します。

そして  x の素因数が1つ見つかれば、以降のグループの素数については、既に  x がBクエリに当たっているのでいきなりAクエリを投げて素因数かどうかの判定をすることができます。これで  x の素因数が全て分かります。

素因数が全て分かれば、あとは各素因数について  p^{2}, p^{3}, ..., をAクエリで投げることでその重複度が分かります。

この解法のクエリ数は

  •  9592素数全てについて投げるBまたはAクエリ)
  • 1グループの素因数の個数(ヒットした後の投げ直しパート)
  • グループ数(A 1 を投げる回数)
  •  16 (重複度の合計の最大値)
  •  1 (Cクエリ)

を合計したものと見積もることができます。1グループの素因数の個数を  \sqrt{9592} に近い  100 程度にしておくことで、合計クエリ数が  9800 程度になります。

時間計算量はBクエリに応じて集合を管理するところが一番重く、それぞれの数を高々1回しか投げないとすると調和級数 O(n \log n) です。私の実装だと複数回 A 1 を投げるたびに  n 要素を見ているので正確にはこれに収まっていないのですが、収まるように実装することは可能です。

ACコード

Submission #92678910 - Codeforces

Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps

お題箱より。

Problem - D - Codeforces

問題概要

 n 本のビルがあり、 i 番目のビルの高さは  h_{i} である。

ビル  i からビル  j へは、 i \lt j かつ以下の3条件のいずれか1つを満たす場合にジャンプして移動することができる。

  •  i+1 = j:ビル  i, j は隣り合っている。
  •  \max(h_{i+1}, ..., h_{j-1}) \lt \min(h_{i}, h_{j}):間にあるビルが全て、ビル  i, j の両方より低い。
  •  \min(h_{i+1}, ..., h_{j-1}) \gt \max(h_{i}, h_{j}):間にあるビルが全て、ビル  i, j の両方より高い。

ビル  1 からビル  n に到達するために必要なジャンプ回数の最小値を求めよ。

制約

  •  2 \le n \le 3\times 10^{5}
  •  1 \le h_{i} \le 10^{9}

解法

「間にあるビルが全て、ビル  i, j の両方より低い」という状況を図示します。

f:id:betrue12:20200911165521p:plain

ビルの組  (i, j) が条件を満たしていて、図のように  i のほうが低い場合、もう一方のビル  j はビル  i から見て「自身より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」になっているという性質があります。そうでないもの、例えば  (i, x) (i, y) については条件を満たしません。

もしビル  j のほうが低ければ、逆にビル  i が「自身より左側にあり、自身以上の高さを持つビルのうち、最も近いもの」となります。ビル  i, j の高さが等しい場合は左右どちらから見た性質も成り立ちます。

そしてこの性質が成り立つことが、 「間にあるビルが全て、ビル  i, j の両方より低い」という条件を満たすことの必要十分条件になっています。

よってこれらの性質を満たすビルの組  (i, j) を探すことにします。逆パターンの「間にあるビルが全て、ビル  i, j の両方より高い」という条件も含めると、結局全てのビル  k について

  • ビル  k より右側にあり、自身以上の高さを持つビルのうち、最も近いもの
  • ビル  k より左側にあり、自身以上の高さを持つビルのうち、最も近いもの
  • ビル  k より右側にあり、自身以下の高さを持つビルのうち、最も近いもの
  • ビル  k より左側にあり、自身以下の高さを持つビルのうち、最も近いもの

を探せば良いことになります。これらを全て求めると「隣り合っているビルの組」も自動的に含まれるので、これでジャンプ可能なビルの組を網羅できます。

4パターン全てほぼ同様に解くことができるので、一例として「ビル  k より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」の求め方を考えます。これはスタックを使って解くと効率的です。

ビルを左から順番に見ていきます。ビル  j を新しく見る時には、以下の処理をします。

  1. スタックの先頭にあるビル  k h_{k} \le h_{j} を満たす限り、 k をスタックから取り除く。このときビル  k にとってビル  j が「ビル  k より右側にあり、自身以上の高さを持つビルのうち、最も近いもの」に該当する。
  2. スタックの先頭にビル  j を追加する。

この処理の過程で、スタックの中にあるビルは常に高さでソートされ、底にあるものほど高いビルになっています。そのため優先度付きキューなどではなくスタックで処理することができます。

このように列挙したジャンプ可能なビルの組の個数は  O(n) であることが分かります。よって  dp\lbrack i\rbrack を「ビル  i まで到達するためのジャンプ回数の最小値」とするDPを用いて計算量  O(n) で解くことができます。

ACコード

Submission #92486700 - Codeforces