ABC に参加して、E完でした。
AtCoder Beginner Contest 142
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Odds of Oddness
問題概要: 1 以上 N 以下の整数を当確率で1つ選ぶとき、奇数が選ばれる確率を求めよ。
A: 考察
確率は (選べる奇数の個数)/(選べる整数の個数) で求まります。
1 以上 N 以下の整数は N 個で、1 以上 N 以下の奇数は (N+1)/2 個 (切り捨て) です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc142/submissions/7739140
B - Roller Coaster
問題概要: N 人がいて、i 番目の人の身長は H(i) である。身長が K 以上の人の数を求めよ。
B: 考察
for と if を書くだけで解けますが、イテレータを使うとよりシンプルです。
(0..N).filter(|&i| H[i] >= K).count()
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc142/submissions/7737446
C - Go to School
問題概要: N 人の生徒からなるクラスにすべての生徒が登校した。生徒 i が登校したとき、その生徒を含めて A(i) 人の生徒がすでに登校していた。複数の生徒が同時に登校することはない。生徒を登校した順番に並べよ。
C: 考察
- 生徒 i が1番目登校したとき、他に登校している生徒はいないので、A(i) = 1 です。
- 生徒 j が2番目に登校したとき、他に登校している生徒は i だけなので、A(j) = 2 です。
- 同様に、生徒 x が n 番目に登校したとき、他に登校している生徒は n-1 人であり、A(x) = n です。
そういうわけで、生徒の配列 P を用意し、各生徒 x に関して A(x) = n なら P(n) に x を置けばよいです。(配列のインデックスは0番目から始まる点に注意。)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc142/submissions/7735912
D - Disjoint Set of Common Divisors
問題概要: 正の整数 A, B が与えられる。A, B の正の公約数を以下の条件を満たすように選ぶとき、選べる個数の最大値を求めよ。
条件: 選んだ整数のどの異なる2つも互いに素である
D: 考察
1 はどの正の整数とも互いに素なので、無条件で選んでよいです。以下、1 でない A, B の公約数だけ考えます。
整数 n が素数 p で割り切れるとき、整数 n は素因数 p を持つと呼ぶことにします。雑に言えば、2つの整数が互いに素であるとは、持っている素因数が被らないことといえます。
持っている素因数が互いに被らないように整数を選ぶので、素因数を1つしか持たない、素数を選んでいくのがベストです。
したがって、A, B をそれぞれ素因数分解して、共通して含まれる素因数を選ぶ (それと 1 を選ぶ) ことで解けます。N の素因数分解は N を √N 以下の各整数で割っていくことで O(√N) 時間でできます。
もう少し考えると、A, B の公約数である素数は、A, B の最大公約数の素因数です。結局、A, B の最大公約数の素因数の個数に 1 を足せばよいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc142/submissions/7742560
E - Get Everything
問題概要: N 個の宝箱と、M 個の鍵がある。i 番目の鍵は a(i) 円で購入できて、これが1つあれば集合 C(i) に含まれる宝箱をすべて開けられる。すべての宝箱を開けるために必要な鍵の購入費用の最小値を求めよ。
制約: N≤12, M≤10^3
E: 考察
鍵を選ぶ組み合わせは無数にありますが、宝箱の集合は約 4000 通りしかありません。鍵の選び方の多くにおいて、選んだ鍵によって開く宝箱の集合が重複します。動的計画法によりこの重複をまとめることで解けます。
すでに開いた宝箱の集合を状態として持ちながら、各鍵について購入するかしないかを検討します。宝箱の集合はビット集合で持ち、和集合を | で表します。
はじめにDP表を設計します。前から i 個の各鍵について購入するか否かをすでに決定し、それによって開いた宝箱の集合が s であるとき、最小の価格を dp(i, s) と表します。(dp(i, s) に該当する鍵の買い方が存在しないこともあります。)
次に遷移を考えます。i+1 番目の鍵を買うケースでは、買った後は「前から i+1 個の各鍵について購入するか否かをすでに決定し、それによって開いた宝箱の集合が s | C(i)である」状態になります。
このケースでの費用 dp(i, s) + a(i) が、購入後の状態の最小値 dp(i + 1, s | C(i)) と比較して小さければ最小値を更新します。
dp(i + 1, s | C(i)) = min(dp(i + 1, s | C(i), dp(i, s) + a(i))
また、i+1 番目の鍵を買わないケースでは開いた宝箱の集合が変化しないので、
dp(i + 1, s) = min(dp(i + 1, s), dp(i, s))
となります。
最終的に dp(N, 111...1) が存在すれば最小値です。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc142/submissions/7752307
dp(i, s) が存在しないときは無限大にしておく方法もありますが、Rust 的には None を使うのが自然だと思ったのでそうしています。ただ、遷移の記述がちょっとめんどうです。
F - Pure
問題概要: N 頂点 M 辺の単純有向グラフ G が与えられる。G の空でない誘導部分グラフで、頂点の入次数・出次数がすべて 1 であるものが存在するか判定し、存在するなら一例を示せ。
制約: N≤1000, M≤2000
F: 考察
誘導部分グラフは、グラフからいくつか(0個以上)の頂点を選んで削除し、削除された頂点に接続している辺もすべて削除する、残りはそのまま、という手順で作られる部分グラフです。
頂点の入次数・出次数がすべて 1 であるような空でないグラフを「条件を満たすグラフ」と呼ぶことにします。
入力例を見ると、どうやら条件を満たすグラフは閉路のようです。これを確認しましょう。
条件を満たすグラフから適当に1点を取ると、残りの部分との間に2本の辺 (出ていく辺と入る辺) があります。選んだ頂点とそれらの辺を除くと、残りの部分は 1つの頂点だけ入次数が 0 で、1つの頂点だけ出次数が 0 である、空でないグラフ です。入出次数が 0 の頂点が単一なら、全体は閉路になります。
そうでないとすると、それら2つの頂点を削除した残りの部分はやはり 1つの頂点だけ入次数が 0 で、1つの頂点だけ出次数が 0 である、空でないグラフ です。これを繰り返すと、グラフが有限なので全体は閉路であるといえます。
有向グラフの閉路は深さ優先探索により O(N + M) 時間で列挙できます。それぞれの閉路が条件を満たすか確認すれば、全体として O(N(N + M)) 時間で間に合います。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc142/submissions/7800194
ところで、閉路上の2点の間に、閉路に含まれない(有向)辺があると、より小さい閉路が存在します (たぶん)。そのため、単に最短の閉路を見つければよいと思ったんですが、1ケースだけ WA するのでダメなようです。反例はなんだろう？
提出 (Rust, WA): https://atcoder.jp/contests/abc142/submissions/7771863