[日記] 今日の AtCoder 過去問 (ABC142)

今日は ABC142 の問題を解きました。

問題文がむずいとか、実装がむずいとか、ちょっと独特な問題が多くて面白かった。

# ABC142
## ABC142 A Odds of Oddness

`N <= 100` 以下の正整数をランダムに選んだ時、奇数である確率はいくらか

### 印象

タイトルがおしゃれ

`N` が偶数の時は五分五分だが、奇数の場合は偶数に対して奇数がひとつ多くなるので、計算が必要。

A 問題にしてはちょっと頭使う感じ。

### 解法

`N / 2` (切り捨て) が偶数の数なので、奇数の数は残りの `N - (N / 2)`。したがって

```
{ N - (N / 2) } / N
```

を計算すれば ok

誤差が `10^-6` 以下になるようにしろということなので、たとえば `printf` なら `"%.7f"` のように桁数を指定して出力する

## ABC142 B Roller Coaster

`N <= 10^5` 個の整数と `K` が与えられるので、 与えられた整数たちのうち `K` 以上のものがいくつあるか数える

### 印象

やるだけ

### 解法

問題文通り、整数が与えられるたびに `K` 以上かどうかを確認して、 `K` 以上ならカウント＋１。

## ABC142 C Go to School [ソート]

`N <= 10^5` 人いるクラスの各生徒に `1` ~ `N` の出席番号がついている。各生徒について、「生徒 `i`  が登校した時、すでに `A[i]` 人が登校済みだった」という形式の記録が与えられるので、登校した順に出席番号を表示する。

### 印象

生徒多すぎワロタ。

「登校済みだった人数」順に並べ替えれば ok

### 解法

印象通り。

「出席番号 `i` と `A[i]` のペア」を配列にしておいて、この配列を `A[i]` の昇順にソートする。あとは先頭から順に出席番号を表示すれば ok

`N` が最大で `10^5` なので、 `O(N^2)` のソートアルゴリズムを選んではいけないことに注意。

## ABC142 D Disjoint Set of Common Divisors [素因数分解]

`A, B <= 10^12` の公約数からいくつかを選ぶ。選んだ公約数たちが互いに素になるようにしたいとき、最大でいくつ選べるか。

### 印象

素因数なら互いに素になるので、 `A, B` に共通する素因数が何種類あるかを数えれば ok

### 解法

印象通り。

`N` の素因数は以下のように見つけられる：

- `i = 2, n = N, 素因数リスト = {1}` とする
- `i <= sqrt(n)` である限り以下を繰り返す：
  1. もし `n` が `i` で割り切れるなら、 `i` を素因数リストに加えて、 `n / i` を新しい `n` とする
  2. 割り切れなければ、 `i` を `1` 増やす

これを `A, B` それぞれに行って素因数を調べたら、共通して出現するものを数えれば答え。同じものは１度しか数えないことに注意

`N` の素因数は `sqrt(n)` まで調べればすべてわかるので、 `N` が `10^12` でも探索範囲は `10^6` となって、間に合う。

## ABC142 E Get Everything [bit DP]

`N <= 12` 個の宝箱と `M <= 10^3` 種類の鍵がある。それぞれの鍵について、

- その鍵の値段 (`<= 10^5`)
- その鍵で開けられる宝箱がどれか (複数の宝箱をいっぺんに開けられる場合もある)

が決まっている。最小いくら払えば全ての宝箱を開けられるか

### 印象

「xx できる予算の最小」なので二分探索…？と思ったけど、予算が与えられたところで、「その予算で宝箱全てが開けられるか」を調べるのがそもそも重い。

二分探索でも重いとなると DP っぽい：

```
dp[<何番目の鍵まで使えるか>][<宝箱の開き具合>] = <その状況を作るために最小いくらかかるか>
```

`<宝箱の開き具合>` は宝箱が高々 `12` 個しかないので、 `2^12 = 4096` 通り。いけそう。

### 解法

およそ印象通り。

`<宝箱の開き具合>` は宝箱が開いていることを `1`、閉まっていることを `0` とすれば、 12bit の二進数ひとつで表せる (bit DP という名前がついていたらしい)。

各鍵で開けられる箱のパターンも同様に二進数で持っておけば、「今の開き具合」と「注目している鍵の開封パターン」の論理和を取ることで、その鍵を使った後の「開き具合」が簡単に計算できる。

漸化式は

```
// 0 番目の鍵を買わない
dp[0][0] = 0

// 0 番目の鍵を買う
dp[0][<0 番目の鍵の開封パターン>] = <0 番目の鍵の価格>

// i+1 番目の鍵を買わない
dp[i+1][j] = dp[i][j]

// i+1 番目の鍵を買う
dp[i+1][j | <i+1 番目の鍵の開封パターン>] = dp[i][j] + <i+1 番目の鍵の価格>
```

４番目の式の論理和 (`|`) が不可逆なので (結果から元の `j` を確定できない)、下から上を計算していくように実装した (説明しづらい…)。イメージとしてはこんな感じ：

```
// 上から下
for i:
  dp[i] = dp[i - 1] + x

// 下から上
for i:
  dp[i + 1] = dp[i] + x
```

同じマスが２度計算されることがあるので、その場合は `min` を取る。

## ABC142 F Pure [BFS]

「`N <= 1000` 頂点、 `M <= 2000` 辺の有向グラフが与えられる。このグラフは自己辺や多重辺を持たない。すべての頂点の入次数・出次数がともに１となるような誘導部分グラフを探せ。ない場合もある」

ただし

「グラフ `G = (V, E)` の誘導部分グラフとは、グラフ `(V', E')` であって、 1. `V'` が `V` の空でない部分集合、 2. `E'` が `E` のうち両端点がともに `V'` に含まれるものを全て含む部分集合、となっているようなもの」

とする。

### 印象

CS の知識がないと問題文の解読から始まるので辛そう (そこまで含めた難易度設定なんだとは思うけど)。

問題文を整理すると、以下のような意味だとわかる：

`N` 個の頂点と、 `M` 本の一方通行の辺が与えられる。ここからいくつかの頂点を選んで、選んだ頂点と、それら頂点に繋がるすべての辺を取り除くことを考える。この結果、分岐のない、一本道のループができることはあるか。もしあるなら、どの頂点を残すようにするとそうなるか答えよ。

(「いくつかの頂点を選んで、それら頂点と、それら頂点に繋がるすべての辺を取り除く」は「誘導部分グラフ」の定義から。これが分岐を含んでいる場合、出次数が２以上の頂点を含んでいるということなので、題意に反する。またもしこれがループになっておらず切れ目がある場合、その端点の入次数が０となるため、題意に反する)

ループを検出することは難しくなさそうだけど、検出したループの中からさらに一本道になっているものを探すのがだるそう…？うーん

### 解法

ひとつ大切な性質に気づけていなかった：

```
もしループ中に分岐が存在するなら、そこからいくつかの頂点を取り除いてより短いループが作れる
```

たとえば `A -> B -> ... -> H -> A` というループを見つけたものの：

```
A -> B -> C
^         |
|         v
H         D
^         |
|         v
G <- F <- E
```

ここに一つ分岐 `B -> F` があったとする：

```
A -> B -> C
^    |    |
|    |    v
H    |    D
^    |    |
|    v    v
G <- F <- E
```

このとき、ループから `C, D, E` を除けば分岐を消すことができる：

```
A -> B
^    |
|    |
H    |
^    |
|    v
G <- F
```

分岐の向きが逆向き (`F -> B`) だった場合も同様に：

```
A -> B -> C
^    ^    |
|    |    v
H    |    D
^    |    |
|    |    v
G <- F <- E
```

今度は `G, H, A` を除けば分岐のないループにできる：

```
     B -> C
     ^    |
     |    v
     |    D
     |    |
     |    v
     F <- E
```


「ループ中に分岐があるなら、そこからいくつかの頂点を取り除いてより短いループが作れる」ということは、「一番短いループを見つければ分岐はない」ということでもあるので、結局元の問題は「与えられたグラフから一番短いループを探せ」という問題になる。

一番短いループを見つける方法を考える。

適当な辺 `u -> v` に注目すると、「`u -> v` を通るループの中で一番短いもの」を見つけることは、「`v` から `u` への最短経路」を見つけることと同じになる。これは BFS を使えば `N <= 1000` の時間でできる。辺は高々 `M <= 2000` 本しかないので、これを全ての辺について行えば、グラフ全体の中で最も短いループが見つかる。全体の計算時間は `N * M = 2 * 10^6`。

ループに含まれる頂点が具体的にどれになるか、まで答えに求められているので、経路を保存しながら BFS する必要があることに注意。

重そうなので念のためメモリ消費も考えておく。キューの要素数は最大で `N` を見ておけばよくて、キューに積む各状態には少なくとも

- 今どの頂点にいるか
- 各頂点について、その頂点がルートに含まれているか

の情報が必要。上は 1 ワードで十分だが、下は素朴に実装すると `N` bytes 必要。したがってキュー全体でおよそ `N^2 = 10^6 bytes` の容量が必要そう。今回は 1024MB 与えられているので、余裕っぽい。