ARMERIA

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

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

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

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

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

お題箱より。

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

POJ NO.3686 The Windy's

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

お題箱より。蟻本に載っている問題です。

3686 -- The Windy's

※ライブラリをC++98に対応させる気になれなかったのでACコードはありません。蟻本に載っているのでそちらを…

問題概要

M 個のおもちゃ工場があり、 N 個のおもちゃの注文を受けた。おもちゃ i を工場 j で製造すると Z_{ij} の時間がかかる。1つの工場は、1つのおもちゃを製造し始めると終わるまで別のおもちゃの製造を始められない。

時刻 0 に全ての工場が同時に利用可能になったとして、おもちゃ i の製造が完了した時刻を T_{i} としたときの、 T_{1}, ..., T_{N} の平均の最小値を求めよ。

制約

  • 1 \le N, M \le 50
  • 1 \le Z_{ij} \le 100000

解法

要求されているのは製造完了時刻 T_{1}, ..., T_{N} の平均ですが、合計を最小化することを考え、答えとしては合計を N で割って出力すれば良いです。以降、 N 個のおもちゃの製造完了時刻の合計を「合計コスト」と呼びます。

ある1つの工場 j で作るおもちゃの集合とその順番を決めたとします。製造の途中に休みを入れることは損でしかないので、ある1つのおもちゃの製造完了時刻は、自身を含むそれまでに製造したおもちゃの所要時間合計と等しいです。具体的にその工場で作るおもちゃが k 個であり、それらの所要時間を製造順に z_{1}, ..., z_{k} とすると、製造完了時刻の合計は

z_{1} + (z_{1}+z_{2}) + (z_{1}+z_{2}+z_{3}) + \cdots + (z_{1} + \cdots + z_{k})

となりますが、これはまとめ方を変えると

kz_{1} + (k-1)z_{2} + (k-2)z_{3} + \cdots + z_{k}

と書くことができます。

これはつまり、その工場で作るおもちゃの所要時間が、後に作るものから順番に 1 倍、 2 倍、 3 倍…という重み付きで合計コストに加算されるということです。

このことから1つの工場 j を、以下のように1枠につきおもちゃ1つの製造枠に分けることができます。

  • 工場 j で最後から 1 番目に作る枠。おもちゃ i を割り当てると Z_{ij} の 1 倍が合計コストに加算される。
  • 工場 j で最後から 2 番目に作る枠。おもちゃ i を割り当てると Z_{ij} の 2 倍が合計コストに加算される。
  • …
  • 工場 j で最後から N 番目に作る枠。おもちゃ i を割り当てると Z_{ij} の N 倍が合計コストに加算される。

これを全ての工場について考えると、結局 NM 個の枠に N 個のおもちゃを最大1つずつ割り当てて合計コストを最小化するという問題になります。これは以下のようなグラフで最小費用流問題として解くことができます。

f:id:betrue12:20200910194510p:plain

AtCoder Library Practice Contest I - Number of Substrings

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

お題箱より。

I - Number of Substrings

解法

※この問題における文字列 S の部分文字列とは、 S の連続な部分を取り出した文字列であることに注意してください。慣習的に、「部分列」と書くと連続とは限らない取り出し方、「部分文字列」と書くと連続な取り出し方を指すことが多いです。意味不明ですね。

「相異なる部分文字列の個数」を求めるために、全ての部分文字列の取り方（左端と右端のインデックスの選び方）から、文字列として重複している分の個数を引くことを考えます。

ここで全ての部分文字列の取り方は、「全ての接尾辞を考えて、それぞれについて全ての接頭辞を考える」ことで列挙できます。そして「接尾辞同士の接頭辞がどの程度共通しているか」ということを考えるのにうってつけの手法が存在します。全ての接尾辞を辞書順ソートした結果を示す接尾辞配列（Suffix Array）と、このソート順において隣り合う接尾辞同士の最長共通接頭辞（Longest Common Prefix）の長さを示すLCP配列というものを使います。

これらを求めるアルゴリズム自体は蟻本や様々な記事で解説されているので省略しますが、一例として acabaca という文字列について計算した接尾辞配列とLCP配列を図に示します。AtCoder Libraryの仕様に合わせ、長さ N の文字列の接尾辞配列の長さは N、LCP配列の長さは N-1 となるよう定義しています。

f:id:betrue12:20200909124851p:plain

このように接尾辞を辞書順ソートしてから共通接頭辞を考えることの利点は、接頭辞が長く共通しているような接尾辞同士が近くに集まることです。具体的には、ソート順で l 番目と r 番目の接尾辞の先頭 k 文字が一致している場合、間に存在する l, l+1, ..., r-1, r 番目の全ての接尾辞において先頭 k 文字が一致します。

この性質を頭に入れて、重複している「接尾辞の接頭辞」の個数を数えましょう。接尾辞配列において前にあるものから見ていって、今見ている接尾辞と1つ前の接尾辞の間の最長共通接頭辞が k 文字であったとします。すると今見ている接尾辞が持つ接頭辞のうち k 文字以下であるものは全て登場済みです。そして逆に k+1 文字以上のものは全て未登場であるということも言えます。先ほど確認した性質から、1つ前のものと一致していないのにそれよりも前のものと一致することはあり得ないからです。

つまり各ステップにおいて、ちょうどLCP配列の値と同じ数だけ登場済みの「接尾辞の接頭辞」が見つかります。よって結局、全ての部分文字列の取り方からLCP配列の総和を引くことで答えを求めることができます。

ACコード

AtCoder Libraryを使ったコード例は配布ライブラリ内のドキュメントを参照してください。以下提出では使っていません。

Submission #16589668 - AtCoder Library Practice Contest

AtCoder Regular Contest 092 C - 2D Plane 2N Points

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

お題箱より。

C - 2D Plane 2N Points

以前の自分が解法の正当性を理解するのにすごく悩んだ問題で、印象深いです。

解法

考察

2次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば x 座標でソートして小さい順番に見ていき、もう一方の y 座標についてはデータ構造などを用いて処理していくテクニックです。軸に平行な直線をスライドさせて平面全体を走査していくので、Codeforcesなどの英語解説では「scanline algorithm」と書かれたりします。

f:id:betrue12:20200907223931p:plain

また赤と青、左端と右端など2種類の要素をペアにする問題では、平面走査や数列の走査と合わせて以下のテクニックがよく使われます。

  • 赤い点が登場したら、その点を「ペア待ち点の集合」に入れる。
  • 青い点が登場したら、ペア待ち点の中から最適な頂点とペアを作る。

このとき「青い点が登場したときに、その都度（何らかの基準で）最適な赤い点を選んでペアにする」という方法が存在して、かつそれが全体最適であることが証明できる場合、正しい解法として成立します。今回の問題の場合はどうか、考えてみましょう。

まず x 座標でソートして小さい順番に見ていった場合、ペアにする2点が赤い点→青い点の順番に登場することが、 x 座標についての条件を満たす必要十分条件になります。つまり x 座標についての条件は自動的に解決し、今後考慮する必要がなくなります。

赤い点が登場したら、その点を「ペア待ち点の集合」に入れます。青い点が登場した時にとり得る選択肢は

  • ペア待ちになっている赤い点のどれか1つとペアにする。
  • どの赤い点ともペアにしない。

の2通りです。ここでもしペアにする場合は、ペアにできる条件を満たす点の中で最も「今後使いにくい」点を使ってしまうのが最適です。赤い点は y 座標が小さいほうがペアにしやすいので、選ぶのは「青い点の y 座標よりも小さいもののうち、最も y 座標が大きいもの」になります。

一方ペアにできる赤い点が存在するのに「あえてペアにしない」という選択も考えられますが、この選択は絶対に得にはならないことが証明できます。ペアにしないことを選んだ時点で1つペア数を損していて、この赤い点1つを温存したことによって今後2ペア以上のアドバンテージを得られることはないからです。

証明は以下のようにできます。あえてペアにしないことで温存した赤い点を p として、その後 p を残した場合の最適なペアの作り方を考えます。このペア構成に p が使われていれば、そのペアを1つ解消することで p を使わないペアの作り方が得られます。また使われていない場合は p が無くても同一数のペアが作れます。つまり p の有無でその後作られる最適なペア数は高々1つしか変わらないことが示されました。

これまでの考察により、以下のアルゴリズムで最適解が得られることが分かりました。

  1. まず全ての点を x 座標でソートする。
  2. 点を順番に見ていきながら、以下の処理をする。
    • 赤い点 (a_{i}, b_{i}) が登場したら、その y 座標 b_{i} を「ペア待ち点の y 座標の集合」に入れる。
    • 青い点 (c_{i}, d_{i}) が登場したら、ペア待ち点の中で「 y 座標が d_{i} より小さいものの中で最も大きいもの」を探し、存在するならばペアにする。

実装

実装ですが、実現したい計算量に応じていくつかの方針があります。今回の場合点の個数が 100 以下かつ座標値も 200 未満なので、配列などで管理して全部の座標値を見ていく方針で良いです。

Y\lbrack b\rbrack を「ペア待ち点の y 座標の集合に値 b が含まれていたらtrue、そうでなければfalse」である配列とします。まず座標点を x 座標で全てソートして順番に見ていきます。赤い点 (a_{i}, b_{i}) が登場したら Y\lbrack b_{i}\rbrack をtrueにします。青い点 (c_{i}, d_{i}) が登場したら Y\lbrack d_{i}-1\rbrack から下に順番に見ていって、trueであるものが見つかったらペアにする、つまり答えに1加算してその値をfalseにすれば良いです。

今回の問題に関してはこれで O(N^{2}) が達成できて十分です。もし O(N\log N) などで解きたい場合は、C++であれば std::set などを用いて集合を管理し、「 y 座標が d_{i} より小さいものの中で最も大きいもの」を二分探索で探す必要があります。

ACコード

この2提出の実行時間だと O(N\log N) のほうが長いんですが、そういうこともあります。 N が小さいし、std::set は定数倍が重いので。

Educational Codeforces Round 94 F. x-prime Substrings

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

Problem - F - Codeforces

自分の解法が非想定解っぽいので書き残しておきます。

問題概要

x を正整数とする。 1, 2, ..., 9 の数字からなる文字列が x-primeであることを、以下の2つをともに満たすことと定義する。

  • 全ての数字の和が x である。
  • 任意の連続部分列について、その数字の和は x より小さい x の約数ではない。

1, 2, ..., 9 の数字からなる文字列 s が与えられる。この s からいくつかの文字を取り除くことで、 s のどの連続部分列も x-primeでないようにしたい。そのために取り除く文字数の最小値を求めよ。

制約

  • 1 \le |s| \le 1000
  • s は 1, 2, ..., 9 からなる
  • 1 \le x \le 20

解法

n = |s| とし、文字列ではなく整数の数列 a_{0}, a_{1}, ..., a_{n-1} として解説します。

ある要素を右端とする連続部分列の和として登場する値の集合を考えます。これは以下の図のように列挙することができます。便宜上 0 も含めておきます。

f:id:betrue12:20200826200930p:plain

これらの値のうち考えるべきは x 以下の値だけです。この登場する値の集合を、値 k を含んでいたら 2^{k} のビットが立つようなビット列で表現します。こうすると、この範囲内に存在する連続部分列の和としてあり得るものは、ビット列において立っている2つのビット同士の距離と見なすことができます。

このようなビット列は 2^{x+1} 通り考えられますが、その中で、「 x-primeになるので登場してはいけないNGパターン」がいくつかあります。具体的には x ビット目が立っていて、立っているどの2つのビット同士の距離も x より小さい x の約数ではない場合、そのビット列に対応する連続部分列は x-primeなので登場してはいけません。逆に全ての要素について、その要素を右端としたときのビット列がNGパターンではない場合、そのような数列は x-primeな連続部分列を持ちません。

ということで、このビット列をキーとしたDPをします。

dp\lbrack i\rbrack\lbrack s\rbrack = 数列を a_{i-1} まで見て、最後に採用した要素を右端とする連続部分列の和として登場する値の集合（ビット列）が s であるときの、これまでに削除した文字数の最小値

dp\lbrack i\rbrack\lbrack s\rbrack からの遷移は2通りあります。もし a_{i} を削除する場合、 dp\lbrack i\rbrack\lbrack s\rbrack + 1 が dp\lbrack i+1\rbrack\lbrack s\rbrack の候補になります。もし a_{i} を削除せずに繋げる場合、 s は「左に a_{i} 桁だけビットシフトして、 1 を足して、 2^{x+1} で割った余りを取る」という操作をした値に変化します。この変化後の値を s^{\prime} として、もしこれがNGパターンでなければ dp\lbrack i\rbrack\lbrack s\rbrack が dp\lbrack i+1\rbrack\lbrack s^{\prime}\rbrack の候補になります。

このDPを回すと答えが求められる…と言いたいところですが、全体計算量 O(n2^{x}) はちょっと間に合いません。状態を削減する必要があります。

ここで注目するのが 1 という要素の存在です。 1 という要素を含んだ連続部分列は、 x=1 である場合を除いて絶対に x-primeになりません。そのため与えられた数列を 1 で分割してパーツごとに独立に解き、それぞれの削除すべき最小文字数を全て足したものを答えとしても良いです。

このときDPの対象となる数列は 1 を含まない前提で考えることができるので、 2^{x+1} 通りのビット列のうち多くのものは絶対に登場しません。具体的には隣り合うビットが1組でも同時に立っているものは登場しないと考えることができます。この条件を踏まえると、考えるべきビット列は x=20 のときでも 28657 通りです。これらの状態だけを扱うDPをすると間に合います。

なお x=1 のときは、単に入力に含まれる 1 の個数が答えになります。

ACコード

Submission #90955511 - Codeforces

DDCC 2016 本選 C - 特別講演「括弧列と塗り分け」

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

お題箱より。

C - 特別講演「括弧列と塗り分け」

解法

この問題を考えるにあたって重要なのが、正しい括弧列を根付き木と対応づけることです。

f:id:betrue12:20200817124335p:plain

それぞれの括弧1組ずつを頂点とみなします。そしてその括弧の1つ外側を囲っている括弧を親とみなすように辺を張ります。これは森になりますが、一番外側に根と対応する見えない括弧があると思うと木になります。このようにすると、それぞれの括弧の中はその頂点以下の部分木と対応します。

まずはこの木をグラフとして作りましょう。 S に含まれる括弧の組数を N と置きます。根を頂点 0 とし、括弧に対して左括弧の登場順に頂点 1, ..., N と番号を振ります。スタックを用意し、 S を順番に見ていって左括弧があればスタックにその括弧の頂点番号を入れ、右括弧があればスタックから1つ取り出します。このスタックに入れた時に1つ前にある頂点番号が親です。

木を作ってしまえば、木DPができます。以下のように状態を定義します。

  • sum\lbrack i\rbrack：頂点 i 以下の部分木に含まれる文字の数
  • dp\lbrack i\rbrack\lbrack r\rbrack：頂点 i 以下の部分木に含まれる文字を塗る方法であって、条件に違反せず、赤の個数が r 個であるような塗り方の数

頂点 i について考える時には、まず初期条件をセットします。括弧 i の塗り方 4 通りを考えて、 dp\lbrack i\rbrack\lbrack 0\rbrack = 1、 dp\lbrack i\rbrack\lbrack 1\rbrack = 2、 dp\lbrack i\rbrack\lbrack 2\rbrack = 1、 sum\lbrack i\rbrack = 2 となります。ただし根については括弧がないので dp\lbrack i\rbrack\lbrack 0\rbrack = 1、 sum\lbrack i\rbrack = 0 です。

それから頂点 i の子 j それぞれについて、 dp\lbrack j\rbrack を dp\lbrack i\rbrack にマージしていきます。これは新しい dp\lbrack i\rbrack 用の配列を用意して、組 (r_{i}, r_{j}) それぞれについて古い dp\lbrack i\rbrack\lbrack r_{i}\rbrack と dp\lbrack j\rbrack\lbrack r_{j}\rbrack の積を新しい dp\lbrack i\rbrack\lbrack r_{i}+r_{j}\rbrack に加算していけば良いです。

このとき r_{i} についてはその前までにマージ済みの i 以下の部分木の頂点数、 r_{j} については sum\lbrack j\rbrack までしか見る必要はありません。これは通称「2乗の木DP」と呼ばれる計算量解析テクニックによって、全体 O(N^{2}) で動作します。

全ての子のマージが終わったら、「括弧 i の内部に含まれる赤の個数 r と青の個数 b について |r-b| \le K である」という条件に違反するものを排除します。赤の個数が r であれば青の個数は sum\lbrack i\rbrack - r なので、 |2r-sum\lbrack i\rbrack| \gt K である r について dp\lbrack i\rbrack\lbrack r\rbrack = 0 とすれば良いです。根についてはこの処理は行いません。

根を頂点 0 としていれば、答えは dp\lbrack 0\rbrack\lbrack r\rbrack の総和として計算できます。

ACコード

Submission #15997966 - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選