ARMERIA

Rubyと競技プログラミングの話　AtCoderや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 本選

yukicoder No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)

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

お題箱より。

No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder

解法

箱を並び替えても答えが変わることはないので、 A_{i} の昇順に並べておきます。

各箱から玉を1個ずつ取り出し、ある1つの色 c の玉がちょうど p 個選ばれる場合の数が、どのように計算できるか図示してみましょう。

f:id:betrue12:20200811140555p:plain

A_{i} の昇順に並べたことによって、箱は色 c の玉を含まないゾーンと含むゾーンに分かれます。含まないゾーンの取り出し方は A_{i} の積であり、色 c の玉はもちろん 0 個です。

色 c の玉を含むゾーンの取り出し方は以下のDPによって求めることができます。

  • dp\lbrack i\rbrack\lbrack j\rbrack = 箱 i, i+1, ..., N-1 全てに色 c の玉が1個ずつ含まれているとき、これらの箱から玉を1個ずつ取り出し、色 c の玉がちょうど j 個選ばれる場合の数。

この値は、箱 i, i+1, ..., N-1 の全てに含まれている色であればどの色でも同じ値になります。つまりクエリで必要な色 c 全てについて別々に計算する必要がありません。

初期条件は dp\lbrack N\rbrack\lbrack 0\rbrack = 1 で、後ろから求めていきます。遷移は

  • dp\lbrack i+1\rbrack\lbrack j\rbrack を遷移元とし、箱 i から色 c の玉を選ぶ。係数 1 で dp\lbrack i\rbrack\lbrack j+1\rbrack に遷移。
  • dp\lbrack i+1\rbrack\lbrack j\rbrack を遷移元とし、箱 i から色 c でない玉を選ぶ。係数 A_{i}-1 で dp\lbrack i\rbrack\lbrack j\rbrack に遷移。

となります。DPパートの計算量は O(N^{2}) です。

クエリに答えるには「ある1つの色 c の玉がちょうど p 個選ばれる場合の数」をたくさんの (c, p) について求める必要があります。これは以下のように計算することができます。

  1. まず、箱が色 c を含まないゾーンと含むゾーンの境界を二分探索で探す。色 c を含む箱の最小のインデックスを x とする（存在しない場合は x=N）。
  2. 色 c を含まないゾーンの選び方は A_{0}\times A_{1}\times\cdots\times A_{x-1} なので、事前に累積「積」を計算しておいてそれを参照する。
  3. 色 c を含むゾーンの選び方はDPテーブルを参照する。具体的には dp\lbrack x\rbrack\lbrack p\rbrack である。

これは1つの (c, p) あたり O(\log N) で計算できます。必要な (c, p) の個数は \sum_{i=1}^{Q}(r_{i}-l_{i}+1) \le 201\times 5000 なので、ちょっと厳しいですが間に合います。

ACコード

No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder

公式解説では多項式の係数として解説していますが、1次式を掛けた時の係数の計算と今回のDPは全く同じものなので、解法としては同じです。

University of Aizu Programming Contest 2014 (AOJ 1548) Yu-kun Likes a Directed Graph

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

お題箱より。

Aizu Online Judge

解法

重み w の負辺を足してできるだけ重み合計が大きい（ 0 に近い）負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が |w| 未満であるもののうち一番大きいものの重み」が分かれば良いです。

ここで |w| \le 100 であること、さらに元々のDAGにある辺の重みは非負であることに注目します。これらの条件から、最終的に見つけるパスも、その一部となるパスも、重みが 100 以下のものだけを考えれば良いことが分かります。

よって以下のようなDPテーブルを構成し、 0 \le s \le 100 の範囲で計算していけば良いです。

  • dp\lbrack i \rbrack\lbrack s \rbrack：1本以上の辺で構成され、頂点 i で終わるパスであって、重み合計が s となるものが存在するか？（true/false）

トポロジカル順序に基づいて順番に計算していきます。遷移は頂点 i から頂点 j への重み c の辺が存在する時に、

  • i から始まり j で終わるパス： dp\lbrack j \rbrack\lbrack c \rbrack をtrueにする
  • i 以外から始まり j で終わるパス： dp\lbrack i \rbrack\lbrack s \rbrack がtrueである s について、 dp\lbrack j \rbrack\lbrack s+c \rbrack をtrueにする

とすれば良いです。

時間計算量は O((V+E)|w|) となり高速な言語ならそのままでも間に合いそうですが、bitsetを用いて高速化することもできます。

ACコード

Aizu Online Judge