今日は 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)である限り以下を繰り返す：- もし
nがiで割り切れるなら、iを素因数リストに加えて、n / iを新しいnとする - 割り切れなければ、
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 与えられているので、余裕っぽい。