AtCoder Beginner Contest 408 D,E,F,G問題メモ

AtCoder Beginner Contest 408

D - Flip to Gather

• 長さ $N$ の '0' と '1' のみからなる文字列 $S$ が与えられます。
• あなたは以下の操作を何回でも( $0$ 回でもよい)行うことができます。
  • $1 \leq i \leq N$ を満たす整数 $i$ を選び、$S_i$ が '0' のときは '1' に、'1' のときは '0' に変更する。

• あなたの目標は $S$ に含まれる '1' が高々 $1$ 個の区間をなすようにすることです。
• より厳密には以下の条件をともに満たすような整数の組 $(l,r)$ が存在するような $S$ にすることが目標です。
  • $1 \leq l \leq r \leq N+1$
  • $1 \leq i \leq N$ を満たす整数 $i$ に対し、$S_i=$ '1' と $l \leq i \lt r$ は同値である。

• 目標を達成するために必要な操作回数の最小値を求めてください。なお、有限回の操作で必ず目標が達成できることが証明できます。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \leq T \leq 20000$
• $1 \leq N \leq 2 \times 10^5$
• $S$ は '0' と '1' のみからなる長さ $N$ の文字列
• 各入力ファイルについて、すべてのテストケースの $N$ の総和は $2 \times 10^5$ 以下である。
• $T,N$ は整数

俗に耳DPと呼ばれるもののシンプル版。

まず、全て'0'の場合は答え $0$ である。
以降、$S$ に'1'は少なくとも1つ含まれるとする。この場合、最終形でも'1'は1つ以上残る。

便宜上、$S$ の両端に '0' を追加しておく。

• $\mathrm{DP}[i,j]:=S_i$ までの時点で Phase $j$ にあるためのコストの最小値
• ただし、Phaseは $j \in \{0,1,2\}$ で、それぞれ以下を意味する。
  • $0$: 最終形において、先頭から'0'が継続中
  • $1$: 最終形において、先頭から'0'を連続後、どこかで'1'にして以降、'1' が継続中
  • $2$: 最終形において、'1' の連続を終了し、'0'が継続中（これ以降も全て0にする）

Phase0,2では、'1'が出てきたら'0'にするためにコスト+1となる。
Phase1では、'0'が出てきたら'1'にするためにコスト+1となる。

また、Phase0で'1'が出てきたとき、Phase1に移行できる。Phase1で'0'が出てくるとPhase2に移行できる。

$\mathrm{DP}[N,2]$ が答え。

Python3

E - Minimum OR Path

• 頂点に $1$ から $N$ の、辺に $1$ から $M$ の番号がついた $N$ 頂点 $M$ 辺の自己ループを持たない連結な無向グラフが与えられます。辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでおり、ラベル $w_i$ がつけられています。
• 頂点 $1$ から頂点 $N$ までの単純パス（同じ頂点を $2$ 度以上通らないパス）のうち、パスに含まれる辺につけられたラベルの総ビット単位 $\mathrm{OR}$ としてあり得る最小値を求めてください。

• $2\le N\le 2\times 10^5$
• $N-1\le M\le 2\times 10^5$
• $1\le u_i \lt v_i\le N$
• $0\le w_i\lt 2^{30}$
• 与えられるグラフは連結である
• 入力される値は全て整数

あるパスについて、使用した辺の重みの総ORをそのパスの「コスト」と表現する。

Dijkstra的に「頂点 $v$ までの最小コスト」みたいにして 頂点 $1$ からのコストが安い方からDPで求める、ということはできない。
反例として用意されているサンプル2が優しい。

   ,-1-,              dijkstraでは②までの最小コストは1だが、
  /--2--\             その辺を使うと③までのコストは 5 になる。
①---3---②---4---③  実際は①→②へは4の辺を使っていくのが正しく、答えは 4 となる。
  `--4--'             ②-③の辺で4のbitはどうしても立つことになってしまうので、
                      ①-②の辺では、他のbitを立てない 4 の辺が最適となる。

後々どの辺を通ることになるかは②までの探索時点では見えないので、DPは無理そう。

上のbitから貪欲に決めていく。

制約から、$2^{29}$ のbitが、答えで1になり得る最大の桁である。
まず、コストの $2^{29}$ のbitが1にならずに済むかどうかを考える。

$2^{29}$ のbitが0の辺だけを使って $1$ から $N$ まで到達可能なら、 そのパスのコストの $2^{28}$ bit目以下がどんなに大きかろうが、 $2^{29}$ のbitが1になるようなパスより優れている。
$2^{29}$ のbitが1の辺は使ってはいけないことになる。

逆に到達不可能なら、答えで $2^{29}$ のbitが立つのは確定。
次に $2^{28}$ bit目以下を最適化するため改めてパスを探索するとき、 $2^{29}$ のbitが立っているかどうかは気にせず使ってよい。

上のbitから「$d$ bit目が0の、その時点で残っている辺だけを使って $1$ から $N$ まで到達可能なら、$d$ bit目が1の辺を取り除く。不可能なら答えの $d$ bit目を1にする」ことを繰り返せばよい。

Python3

F - Athletic

• $1$ から $N$ までの番号がつけられた $N$ 個の足場が一列に並び、足場 $i(1 \leq i \leq N)$ の高さは $H_i$ です。
• 高橋君は足場に乗って移動する遊びをすることにしました。
  • 最初、高橋君は整数 $i(1 \leq i \leq N)$ を自由に選び、足場 $i$ に乗ります。
  • 高橋君はある時点で足場 $i$ に乗っている時、以下の条件を満たす整数 $j(1 \leq j \leq N)$ を選び足場 $j$ に移動することができます。
    • $H_j \leq H_i - D$ かつ $1 \leq |i-j| \leq R$

• 高橋君が移動を行えなくなるまで移動を繰り返すとき、移動できる回数の最大値を求めてください。

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq D,R \leq N$
• $H$ は $(1,2,\ldots,N)$ の順列
• 入力はすべて整数

高橋君が移動する度、足場の高さは下がっていくので、移動は永遠には続かない。

高い足場から確定させていく。
高さが同じ足場同士は遷移できないので、$H_i$ が同じ同士の順番は適当でいい。

区間chmax、1点取得の双対セグメント木 $T$ と、更新クエリを一時保存するキュー $Q$ があればよい。

• 足場 $i$ について処理する時
  • $Q$ に溜まっている、高さ $H_i \le H_j-D$ なる $j$ の更新クエリを処理する。
  • その時点での $T[i]$ が、足場 $i$ までの最大移動回数。
  • 「$[i-R,i+R]$ の区間を $T[i]+1$ で更新する」という更新クエリを $Q$ に積む。

この過程で取得した $T[i]$ の最大値が答えとなる。

双対セグメント木を遅延評価セグメント木で代用したら、定数倍が重く、PythonではTLEを取るのに苦労した。

Python3

考え方はほぼ同じだが、普通の「1点更新、区間MAX取得セグメント木」でできる。

DPの遷移を、先ほどは与える方で考えていたが、逆にもらう方で考えた場合、 「$i$ に直接移動してこられる足場」の範囲は $[i-R,i+R]$ なので、その区間MAXが取得できればよい。

G - A/B < p/q < C/D

• $\displaystyle \frac AB \lt \frac CD$ を満たす正整数 $A,B,C,D$ が与えられます。
• 以下の条件を満たす最小の正整数 $q$ を求めてください。
  • ある正整数 $p$ が存在し、 $\displaystyle \frac AB \lt\frac pq \lt \frac CD$ が成立する。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 2\times 10^5$
• $1\le A,B,C,D\le 10^{18}$
• $\displaystyle\frac AB \lt \frac CD$
• 入力される値は全て整数

まず、$\frac{A}{B},\frac{C}{D}$ を既約分数化しておく（忘れててめっちゃ沼った）。

Stern-Brocot木を考える。任意の正の既約分数はこの木に含まれる。

• Stern–Brocot 木 (有理数木) #アルゴリズム - Qiita

Stern-Brocot木は、ユークリッドの互除法を使えば、 ある既約分数に対して木をどのように辿れば到達できるかを特定することができる。
（上記リンク先参照）

$\frac{A}{B}$ と $\frac{C}{D}$ の、Stern-Brocot木上での位置関係により、場合分けする。

2つのLCA（最小共通祖先）に当たる分数の分母が答えとなる。

LCAに当たる分数を $\frac{p}{q}$ とすると、

• Stern-Brocot木では分数は小さい順に並ぶので、$\frac{A}{B} \lt \frac{p}{q} \lt \frac{C}{D}$ が成り立つ。
• $\frac{p}{q}$ の部分木に含まれる分数の分母は、$q$ 以上である。
  • 既に $\frac{p}{q}$ が条件を満たすことが分かっているので、部分木内の他の分数は最小値になり得ない。
• $\frac{p}{q}$ の祖先から見て $\frac{A}{B}, \frac{C}{D}$ は同じ側にある。
  • つまり、$\frac{r}{s} \lt \frac{A}{B} \lt \frac{C}{D}$ または $\frac{A}{B} \lt \frac{C}{D} \lt \frac{r}{s}$ なので、条件を満たさない。

木を上から辿っていって、分岐するところが答えとなる。
この時、木を左に何回か連続して、または右に何回か連続して辿る場合は、まとめて計算しないとTLEとなるので注意。

$\frac{A}{B}$ が、$\frac{C}{D}$ の祖先だとする。（逆の場合も反転すれば同様に考えられる）

$\frac{C}{D}$ は、$\frac{A}{B}$ から、右に $a_1$ 回、左に $a_2$ 回、右に $a_3$ 回、、、(左/右) に $a_k$ 回辿った先にあるとする。

$\frac{A}{B}$ から右に1回辿った $\frac{p}{q}$ が答えとなる。

A/B
   ＼
    p/q
      ＼
        :
         ＼
          C/D

$\frac{C}{D}$ からさらに左に1回辿ったものが答えとなる。

k=1 のとき   k=2 のとき
A/B          A/B
 `----,       `------,
     C/D             ○
     /               /
   p/q              :
                   /
                 C/D
                 /
               p/q

$a_2$ まで辿った $\frac{p}{q}$ が答えとなる。

A/B
 `----------,
            ○
          ／
         :
      ／
    p/q
     \
      :
       \
       C/D

Python3