ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AGC029 C - Lexicographic constraints

二分探索

問題
提出コード

解法

x種類以下で問題の条件を満たすような文字列たちを作成できるか？という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、あるxについて問題の条件を満たすかどうか、を見ながら二分探索を行えばよいです。
先頭の文字列から順に見ていったときに、次に作成する文字列は、作成できる文字列の中で辞書順最小のものを選んだ場合が一番得をします。
なので、今作成し終えた文字列の状態を見て、次に作成する辞書順最小の文字列が何か？というのがわかればよいです。
文字列をランレングス圧縮のようにして、
i文字目までがcという文字になっている
という情報で書き換えます。
すると、次に作成する文字列の長さがa_{j}であったとき、

  • i \lt a_{j}であれば、辞書順最小の文字を末尾に追加

  • そうでなければ、すでに作成し終えている文字列の末尾のうち、a_{j}以下でかつx未満の文字を次の文字に置き換え、その後辞書順最小の文字で埋める

という操作をすればよいです。
上記の条件を満たすような文字が存在しなければ、作成できないということになります。

感想

初手で貪欲に走ったので反省…

Typical DP Contest G - 辞書順

動的計画法(DP)

問題
提出コード

解法

まず、

  • m_{i,j} = i文字目の次にjという文字が現れるインデックスの最小値

を計算します。
これは、m_{i-1,j} = m_{i,j}(j \neq s_{i}), m_{i-1,s_{i}} = iという更新を行えばよいです。
さて、

  • dp[i] = i文字目を先頭で使った際にできる、部分文字列の種類数

というDPを考えます。
i文字目を使った際に考えられるパターンは、

  • i文字目の1文字のみ

  • i文字目の次に、jという文字を繋げる

の2つです(後者は最大26通りありますが…)。前者は明らかにトータル1通りです。
後者については、iの直後に現れるjを取ってくると、i番目の文字の次にjを置いたパターンの部分文字列が網羅できます。
なので、結局
dp[i] = 1 + \sum_{j} dp[m_{i,j}]
という遷移になります。
では、最終的に求めたい文字列はどうなるでしょうか。
まず、先頭の文字がa,b,...zであるような部分文字列全てについて足してもKにならない場合は、明らかにEelとなります。
それ以外の場合は、前から貪欲、aから順番に見ていき、総和がK以上になるならその文字を選択…という操作を繰り返します。
実装の際は、先頭にダミーの文字を入れると実装が少し楽になります。

今見ているインデックスをidとして、次に選ぶ文字をaから順番に見ていきます。dp[m_{id,j}]を見て、これがK以上ならばjが次の文字になります。そうでなければ、Kからdp[m_{id,j}]を引き、次の文字をチェックしていきます。
今見ている文字が最後の場合となるパターンをKから引き忘れないようにすれば、答えが求まります。

感想

最近ABCやその他の場所で、ある状態を構成し数え上げる際に重複するパターンを、貪欲にチェックする操作のみ考慮することで重複を消す、という考え方を使ってきたので、それと似たような考え方でできました。
それよりむしろ、メモリ制限が厳しかったです…空間計算量はまだまだ難しいですね

AGC009 C - Division into Two

数え上げ 累積和

問題
提出コード

解法

集合X,Yを、集合0、集合1とし、A,BをL_{0},L_{1}とします。

  • dp[i][j] = i番目の要素まで見て、i番目の要素を集合jに入れるような振り分け方のパターン数

を数えます。
[l,i]という区間が集合jに入り、その前後はもう片方の集合に振り分けられるパターンを考えます。このような操作ができる条件は、

  • S_{i+1} - S_{l-1} \geq L_{1-j}

  • S_{k+1}-S_{k} \geq L_{j} (l \leq k \lt i)

の二つを満たすことです。
逆に、これらの条件を満たすlについて、[l,i]を集合jに入れる、という操作ができるので、
dp[i][j] = \sum_{l} dp[l-1][1-j]
という遷移が考えられます。
1つめの条件は、それぞれのiについて二分探索を用いて計算ができます。
S_{i + 1} - L_{1-j} \lt S_{k}となるようなkを二分探索で求めます。すると、 lとして選べるのはk-1以下です。

2つめの条件は前計算ができます。
S_{m + 1} - S_{m} \lt L_{j}となるようなmで区間を区切っていきます。 i番目の要素についてみると、lとして選べるのは、その要素が所属している区間の要素のみになります。

以上で、ある要素iについて選べるlの区間が求まったので、その区間の総和を求めてあげればDPの遷移が行えます。
区間和による遷移なので、累積和やセグ木で簡単に高速化ができます。
答えはdp[N][0] + dp[N][1]です。

オイラーツアー、HLD解いた問題まとめ

提出場所見失いそうなので個人用まとめです
もう少し解法の中身っぽいところを後で加えたいです(加えてください)

HLD

Submission #12187038 - 2010年 日本情報オリンピック春合宿OJ

Aizu Online Judge

Submission #12180953 - AtCoder Beginner Contest 133

#491538 (C++17(1z)) No.529 帰省ラッシュ - yukicoder

Aizu Online Judge

HLDのupdate関数を使うこと！！！

オイラーツアー

頂点

Aizu Online Judge

辺

Submission #12180082 - AtCoder Beginner Contest 133

Submission #12331777 - AtCoder Beginner Contest 163

Waseda Orientation Programming Contest 2020 J - トレジャーハンター

ダイクストラ法 動的計画法(DP) 最大公約数(GCD)

問題概要

N種類のはしごがあり、i番目のはしごの長さはA_{i}です。
0以上M以下の値Pで、以下の条件を満たさないものの個数を求めてください。

  • N種類のはしごを上手く使い、長さの総和をPにすることができる(ただし、同じはしごは何回でも使用可能、1度も使わなくても可)

T個のテストケースが与えられるので、全てに答えてください。

Med:

  • T = 50

  • 1\ \leqq N \leqq 30

  • 1 \leqq M, A_{i} \leqq 1000

Large:

  • T = 50

  • 1 \leqq N \leqq 30

  • 1 \leqq M \leqq 10^{18}

  • 1 \leqq A_{i} \leqq 3 \times 10^{4}

Largeの制約では、最悪でも1分程度で答えが出る想定で、
Python、Javaでは1分以内に全ての答えが出力されることを確認しています。

解法

どの解法でも、1つ1つのテストケースに対して計算し、T回繰り返すことを考えます。

Med

dp[i] = 合計距離がiとなるような組み合わせができるか(bool値)
として、
初期値:dp[0] = 0
遷移:dp[i] = dp[i] \ or \ dp[i-A_j]
という計算をすると、O(NM)で計算可能です。
個数制限無しナップサックを用いたもの。

Large

上記の解法だとメモリ、時間ともに足りません。
[1,M]について全て調べたいですが、それぞれについて考えると、状態数が多くメモリと時間が足りなくなってしまうので、うまく状態数を減らしていくことを考えます(一般に、bool値のDPはより多くの情報を持たせて遷移させることができるはずです、例えば上記のbool値はできるかどうか、だけでなく、ほぼ同じ遷移で使用するはしごの最小個数をそのまま持たせることができます)。
min(A_i) = Xとします。
距離Xのはしごのみを適切な回数用いることで、Xの倍数については必ず達成できることは明らかです。
Xの倍数ではないときも、ある距離Dが達成できた場合に、その後に距離Xのはしごを繰り返し使うことで、D以上の、 距離をXで割った余りがD\%Xとなる地点は全て達成できます。 なので、距離をXで割った余りそれぞれについて、可能な最小値を探せば、その最小値未満の値ができない、ということになります。ということで、

  • dp[i] = D \% X がiになるような合計距離Dの中で、作成可能な最小値

を考えていきます。
dp[0] = 0,dp[i] = \inftyで初期化をします。
dp[i]より小さい値の個数をそれぞれのiについて計算してあげると、その総和が答えです。ここはO(X)です。

1つめ:01ナップサックに帰着

先ほどのdpについて、個数制限のないナップサック問題を適用することについて考えてみます。
dp[(i + A_{j}) \% X] = min(dp[(i + A_{j}) \% X],dp[i] + A_{j})
という遷移になります。
X = 8,dp配列が\{0,55,1,3,2,2,1,4\}であったときを考えます。
普通、個数制限無しナップサックを考える場合は、dpの添え字0から順番に増やしていきますが、例えばA_{j} = 12だった場合、
次の遷移では
\{0,55,1,3,2,2,1,4\}
になります。しかし、添え字5から始めると、
\{0,14,1,3,2,2,1,4\}
になります。
(dp[1] = min(dp[1],dp[(5 + 12)\%8] + 12) = 14です)。
このように、始まる添え字によって値が変わり、うまくDPを行うことができません。
このことは、個数制限なし、という条件を、
距離Dのはしごの1個セット、2個セット、4個セット....を用意してあげて、
距離Dのはしごp個セットを使う/使わない
という2択にすることで、2進数で任意の個数を表現しつつ、うまく処理することができます。

  • dp[j][i] = j個目のはしごセットについて使用する/しないを決めたとき、D \% X がiになるような合計距離Dの中で、作成可能な最小値

とすると、j個目のはしごセットの距離の総和をHとして、
dp[j][(i + H) \% X] = min(dp[j][(i + H) \% X],dp[j][i] + H)
と遷移することができます。 はしごセットは、それぞれのはしごについて、A_{j} × 2^{p} \leqq Mとなるpについて考えればよいので、N \log Y種類で抑えられます(実は、N \log Xで抑えることもできます) 。
よって、O(NX \log M)で解けました。

2つめ:個数制限なしナップサック

1つめの解法の、個数制限なしナップサックに戻ってみます。
先ほど上手くいかなかったのは、添え字0から、順番に1ずつ増やしていたからです。
ここを賢く走査することで、個数制限なしナップサックでも解けるようにしてしまいます。
i種類目のはしごについて、dpの添え字の遷移は、GCD(X,A_{i})本のループにわかれます。
例えば、X = 10,A_{i} = 14のとき、
0 \rightarrow 4 \rightarrow 8 \rightarrow 2 \rightarrow 6 \rightarrow 0 \ldots
というループと、
1 \rightarrow 5 \rightarrow 9 \rightarrow 3 \rightarrow 7 \rightarrow 1 \ldots
というループにわかれます。
1ずつ添え字を増やして見ていくのではなく、このそれぞれのループについて、個数制限なしナップサックを考えます。
このそれぞれのループについて、現在の最小値を探します。すると、その最小値の部分は、他がどうであれ、今見ている長さA_{i}のはしごをどれだけ使っても、この最小値が更新されることはありません。
なので、この最小値のインデックスpからスタートして、
p \rightarrow (p + A_{i})\% X \rightarrow (p + 2 \times A_{i}) \% X \ldots
と見ていけば、ループを1周するだけでうまく更新できます。 最小値を探すのと、更新それぞれで1周ずつすればよく、それぞれのループにある添え字の個数の合計は結局Xになるため、はしご一種類あたりO(X)で計算できます(最小値を探さなくとも、適当な場所から更新をはじめ、2周する、という方法でもいいです)。
これをN回繰り返すため、O(NX)でこの問題が解けました。

3つめ:ダイクストラ法
  • dp[i] = D \% X がiになるような合計距離Dの中で、作成可能な最小値

に戻ります。 現在の距離がDの際に、はしごA_{j}を新たに用いたとすると、 距離はD + A_{j}に、(合計距離) \% X は (D + A_{j}) \% Xになります。 dp[i]について、添え字iを頂点番号と考え、頂点iではしごA_{j}を使う操作を、コストA_{j}、遷移先の頂点が(i + A_{j}) \% X の辺としたグラフを考えることができ、
それぞれの頂点に行く、最短距離を求める問題としてみることができます。
最短距離といえばダイクストラ法です。
dp[0] = 0から、順にはしごjを使う操作による遷移を行い、dp[i]を埋めることをダイクストラ法を用いて行うと、
頂点数がX、辺の本数が(頂点数X×梯子の種類数N) = NX本なので、 O(NX\log X)で解くことができます。

おまけ(Med解以外の想定TLE,MLE解法)

実は、距離が十分に大きい時、
A_{1} ~ A_{N}すべてについての最大公約数をYとすると、
Yの倍数は全て構築可能、そうでない場合は構築不可能になります。
距離が十分に大きい、というのは、max(A_{i})^{2}以上であればOKです。
つまり、max(A_{i})^{2}までは愚直にMed解法と同じDPで見て、それより大きい部分については、Yの倍数でない数を数えるだけで、この問題に対して答えることができます。O(Nmax(A_{i})^{2})です。

コード

解法1,2についてはこちらにアップしました(2020/05/19)。
main.cが解法1つめ、mainver2.cが解法2つめです。

AOJ 2335 - １０歳の動的計画

数え上げ カタラン数

問題
提出コード

解法

縦方向がN、横方向がMとします(多分問題と逆…？)
移動は必ず全体でN + M + 2K回になります。
縦にi回、横にK-i回寄り道すると決めた時、上記の移動のうち、縦方向に移動するのがN + 2i回、横方向がM + 2(K-i)回になるので、先にその方向を決め打つと、
_{N + M + 2K}C_{N + 2i}
通りになります。
あとは、縦横独立に考えることができるので、
_{N + M + 2K}C_{N + 2i} \times (縦方向の移動パターン) \times (横方向の移動パターン)
を計算すれば、答えになります。
ここからは縦について、つまり元の長さがNで、i回寄り道することを考えます。横方向についても同様に計算できます。
座標が負になることを許容すると、全体で_{N + 2i}C_{i}通りになります。
ここから、

  • j回目に寄り道をした結果、初めて座標が負になる移動の仕方

を1 \leqq j \leqq iについて計算し、全体から引けば、求めたい移動パターン数になります。
j回目に寄り道をして、初めて座標が負になるには、
(正方向に移動した回数) \geqq (負方向に移動した回数)を満たしながら、
正負ともにj-1回ずつ移動し、その後負に移動する、という道筋をたどるしかありません。
これは、p番目のカタラン数をCat_{p}と表記すると、Cat_{j-1}です。
そして、その後は自由に移動できるので、_{N +2(i-j) + 1}C_{N + i - j + 1}通りあります。
よって、j回目に寄り道をした結果初めて負になる場合の移動パターン数は、
Cat_{j-1} \times _{N +2(i-j) + 1}C_{N + i - j + 1}
であり、求めたかった、縦の移動パターン数は、
_{N + 2i}C_{i} - \sum_{j = 1}^{i}(Cat_{j-1} \times _{N +2(i-j) + 1}C_{N + i - j + 1})
となります。
あとは、これを最初の方で求めた式に当てはめれば、答えが求まります。

AOJ 2293 - Dangerous Tower

最小費用流

問題
提出コード

解法

A_{i},B_{i}全て含めて、横の長さと箱が1:1に対応します。
なので、横の長さと箱をマッチングさせていくことを考えます。
箱iについて、

  1. A_{i}とマッチングさせる

  2. B_{i}とマッチングさせる

  3. マッチングさせない

という3つの選択肢が存在します。

それぞれの場合について、高さがどれだけ増えるか、ということを考えると、

  1. A_{i}とマッチングさせる
    →B_{i}増加

  2. B_{i}とマッチングさせる
    →A_{i}増加

  3. マッチングさせない
    →増加なし

となります。
これを、コストに置き換えます。
はじめ、A_{i} + B_{i}だけポイントを貰っていたとすると、それぞれの選択によるコストは、

  1. A_{i}とマッチングさせる
    →A_{i}のコストがかかる

  2. B_{i}とマッチングさせる
    →B_{i}のコストがかかる

  3. マッチングさせない
    →A_{i} + B_{i}のコストがかかる

となります。
あとは、それぞれの箱をマッチングさせ、最小コストになるようにすればよいです。
これを求めるのに最小費用流を用います。
超頂点s,t、箱を表すN個の頂点、横の長さを表す頂点を用意します(横の長さを表す頂点は、A_{i},B_{i}の種類が個数になります)。
sから箱の頂点それぞれにコスト0の辺を張る
箱の頂点から、A_{i}を表す頂点にコストA_{i}の辺を張る
箱の頂点から、B_{i}を表す頂点にコストB_{i}の辺を張る
箱の頂点から、tにコストA_{i} + B_{i}の辺を張る
横の長さを表す頂点から、tにコスト0の辺を張る
という操作を行います。容量は全て1です。
あとは、sからtに、Nだけフローを流すときの最小コストを求めれば、
\sum (A_{i} + B_{i})から引くことで答えが求まります。

感想

これと似ているな、と思って解いたので初めてマッチング問題を自力で解けました。いいですね。