今日は 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 与えられているので、余裕っぽい。