AtCoder Beginner Contest 132 D,E,F 問題メモ

AtCoder Beginner Contest 132

• AtCoder Beginner Contest 132 解説放送 - YouTube

D - Blue and Red Balls

• $N$ 個の赤と青のボール、うち青は $K$ 個
• $N$ 個を横一列に並べる
• 連続する青を1箇所と数えるとき、青がちょうど $i$ 箇所に分かれて存在する並べ方の個数を、$i=1..K$ のそれぞれについて求めよ
• 同色のボールは区別しない
• $1 \le K \le N \le 2000$

赤いボールをr, 青いボールをb, 並びを“rrbbbbrr…” と表現すると、このランレングス圧縮表現 “r2b4r2…” にbが $i$ 箇所現れる並べ方の個数を求める。

$i=j$ の時の問題を解く。これが $O(N)$ くらいで解ければ、全体で $O(NK)$ となり、間に合いそう。

まず、青の連続する箇所が $j$ 箇所あることをイメージする。各箇所に1個以上は必要。

   (b)   (b)   (b)

ここに赤を差し込む。赤は、両端を含む $j+1$ 箇所に差し込める。この時、青と青の間の $j-1$ 箇所は、青を分割しなければならないので1個以上必要。

   (b)   (b)   (b)
 ^     ^     ^     ^
 r     r     r     r

こうすると、「青の決め方」×「赤の決め方」を計算すれば、$i=j$ の時の答えとなる。

1個以上必要な箇所についてはあらかじめ1つずつ配っておき、残りを重複組み合わせで求める。

• 青
  • 置ける箇所は $j$ 箇所
  • 全体で $K$ 個、$j$ 箇所に1個ずつ配るので、残り $K-j$ 個
• 赤
  • 置ける箇所は $j+1$ 箇所
  • 全体で $N-K$ 個、$j-1$ 箇所に1個ずつ配るので、残り $N-K-j+1$ 個
  • $N-K \lt j-1$ の場合、青を $j$ 箇所に分割できないので、答えは「0」

$ans = {}_{j}H_{K-j} \times {}_{j+1}H_{N-K-j+1}={}_{K-1}C_{K-j} \times {}_{N-K+1}C_{N-K-j+1}$

E - Hopscotch Addict

• $N$ 頂点 $M$ 辺の有向グラフが与えられる
• ある頂点から「移動できる頂点に移動することを3回繰り返す」ことを1回の操作とする
• 頂点 $S$ から頂点 $T$ に移動することができるか、できる場合は何回の操作で移動できるか求めよ
  • 「$T$ に移動できる」とは、操作の終了時に $T$ にいることを示し、操作の途中で $T$ を訪れることは含まない
• $2 \le N \le 10^5$

グラフ探索だが、頂点をグラフそのままの頂点では無く、「状態」で置き換えましょう、という問題。

3回の移動を「けん1」「けん2」「ぱ」で表すと、同じ頂点でも「けん1」で踏んだときと「けん2」で踏んだときと「ぱ」で踏んだときは区別しないといけない。

こんなグラフがあったとき、

Ｓ → ○ → ○ → ① → Ｔ
                  ⇅
                  ○

通常のグラフ探索では1回訪れた頂点は2回目以降に訪れた時はスキップする（しないと無限ループに陥る）が、上の場合は①を2回踏むことでＴにたどり着けるので、探索をスキップしてはいけない。

一方で、こんなグラフを考えると、

Ｓ → ○ → ① → ○ → ...
          ↗  ↘
        ○←○←○

①は、ループを通ることで何回でも訪れられる。 1回目は「けん2」、2回目は「ぱ」、3回目は「けん1」で訪れ、それぞれでこの先の操作終了時に止まれる頂点が異なるので、3通りは探索する必要がある。

しかし4回目の「けん2」で訪れた際は、1回目と止まれる頂点が変わらず、しかも確実に1回目より操作回数がかかるので、 この場合は探索を停止しないと無限ループに陥るか、無駄に時間がかかってしまう。

よって、「頂点①を【けん1】で訪れた」「頂点①を【ぱ】で訪れた」などの「状態」を1つの頂点と見なしてグラフを作る。

頂点 $v$ を、$S$ からの距離 $d$ で訪れたとすると、Tupleなどのデータで $(d \% 3, v)$ を頂点のIDとすればよい。$(0,T)$ がゴールとなる。

F - Small Products

• 正の整数 $K$ 個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積も $N$ 以下であるものの個数を $\mod{10^9+7}$ で求めよ
• $1 \le N \le 10^9$
• $2 \le K \le 100$

$N$ が小さいなら、以下のようなDPで計算量 $O(KN \log{N})$ で解ける。

• $DP[i][j]=i$ 個までを一列に並べて、右端が $j$ であるような数列の個数

$i-1$ 番目の数字が $j$ なら、$i$ 番目には1から $floor(\frac{N}{j})$ までの数字を置けるので、以下のループで遷移できる。

dp[0][1] = 1
for i in range(1, K + 1):
    for j in range(1, N + 1):
        for k in range(1, N // j + 1):
            dp[i][k] += dp[i-1][j]

ただし、$j$ は $1～N \le 10^9$ の範囲を取り得るので、時間的に足りない。$j$ の範囲を減らしたい。

高速化のためには、数字が大きくなったら両隣に置ける数字は似通ってくることを利用して、情報をまとめることが必要となる。

2数の積なので、$\sqrt{N}$ を超える数字は2つ並べられないことを考えると、平方根を利用するのでは、と当たりを付ける。

$j$ の範囲を $1～\sqrt{N}$ とかにできれば、$\sqrt{10^9}=32000$ くらいなので $O(\sqrt{N}K)$ が間に合いそう。

N=10
   隣に置ける数字
1  1 2 3 4 5 6 7 8 9 10
2  1 2 3 4 5
3  1 2 3
4  1 2
5  1 2
6  1
7  1
8  1
9  1
10 1

たとえば4と5、6～10はまとめてしまえる。

そのため、DPを2つに分ける。以下、$floor(\sqrt{N})$（切り捨てたもの）を単に $\sqrt{N}$ と表現する。

• $DP1[i][j]=i$ 個までを一列に並べて、右端が $j$ であるような数列の個数
• $DP2[i][k]=i$ 個までを一列に並べて、右端が「$\sqrt{N}$ より大きく、隣に $k$ を置けるような数字」であるような数列の個数

$j,k$ の範囲は $1～\sqrt{N}$ とする。こうすると、$1～N$ のうち、$\sqrt{N}$ 以下はDP1で、$\sqrt{N}$ より大きいのはDP2で、重複無く管理される。

N=10 の場合
√10 = 3 より j,k の範囲は1～3（ただし、以下では配列添字の便宜上0も含める）

1番目には $1～N$ の任意の数字を置ける

DP1[1] = [0, 1, 1, 1]  ... 右端が1,2,3であるパターンはそれぞれ1通り
DP2[1] = [0, 7, 2, 0]  ... 3より大きく隣に1を置ける数字は4～10の7通り
                                      隣に2を置ける数字は4,5の2通り
                                      隣に3を置ける数字はない

ここで、2番目の数字を考える。

DP1への遷移を考える。
DP1[2] へは、DP1[1], DP2[1]の両方から遷移する。

まず、DP1[1]からの遷移については、全ての数字が好きなように隣り合えるので、全ての状態から遷移できる。
DP1[2][1] = DP1[1][1] + DP1[1][2] + DP1[1][3] （※暫定）

DP1[2][2]等についても同様のため、DP1[1]の総和3がDP1[2]の全要素に加算される
DP1[2] = [0, 3, 3, 3]（暫定）

ここに、DP2[1]をそのまま加えればよい。
DP1[2] = [0,10, 5, 3]


DP2の遷移は、ちょっとややこしい。
まず、√Nより大きい数字は連続できないので、DP1 からのみ遷移する。

実は、DP2[1] = [0, 7, 2, 0] は遷移のための共通の係数となっていて、これを coef とする。

1の隣には7通りの数字が置ける（3より大きい中では）
2の隣には2通りの数字が置ける
3の隣には0通りの数字が置ける
...これらの倍率を表したものが、coefとなっている

また、以下の相互作用を考えて遷移を行う。

・(A) kの隣に置ける数字は全て、kより小さい数字の隣にも置ける
  
  i-1番目が 2 のパターン（DP1[i-1][2]）の次には、4,5の2通りを置けるため、
    DP2[i][2] += DP1[i-1][2] * 2
  という式で遷移できるが、
  同時に4,5は1の隣にも置けるので、同じパターン数を同様に加算しないといけない。
    DP2[i][1] += DP1[i-1][2] * 2
  
・(B) kより小さい数字の隣に置けるものの中には、coef[k] の数だけ、kの隣に置けるものも含まれる

  i-1番目が 1 のパターン（DP1[i-1][1]）の次には、4～10の7通りを置ける
    DP2[i][1] += DP1[i-1][1] * 7
  ただ、この内4,5の2通りに関しては、2の隣にも置けるので、その分を加算しないといけない。
    DP2[i][2] += DP1[i-1][1] * 2


これらをまとめて累積和で計算できるようにすると、以下のようになる。

DP2[2](a) = [0, 7, 2, 0]  ... DP1[1] の各要素に coef をかける
DP2[2](b) = [0, 9, 2, 0]  ... 後ろから累積和を取る

DP2[2](c) = [0, 1, 2, 3]  ... DP1[1] の累積和を取る
DP2[2](d) = [0, 0, 1, 2]  ... 1つずらす
DP2[2](e) = [0, 0, 2, 0]  ... coef をかける

DP2[2]    = [0, 9, 4, 0]  ... (b)と(e)を足し合わせる

(a)～(b) で (A) のケースを、(c)～(e) で (B) のケースを考慮している。

この遷移を $i=K$ まで行い、「$DP1[K]$ の総計」と「$DP2[K][1]$」の合計が答えとなる。

DP2はその定義上、重複が含まれる。（$N=10$ の場合、たとえば右端が $4$ や $5$ である数列は $DP2[i][1],DP2[i][2]$ の双方に数えられている）

「1に隣り合える数」ならば全ての $\sqrt{N}$ より大きく $N$ 以下の数字のパターン数が数えられているので、それだけを使えばよい。