OUPC2022 B「CD Collector」解説

はじめに

「CD Collector」 writerのkotamanegiです。導入文はほぼ実話です。

for文で解くことができる、一番簡単な問題枠として出題しました。
OUPC2022で少なくとも2問は「解けた！」をお届けするために置いています。

問題の概要

問題ページ

$K$ 個の店舗をめぐって $N$ 種類すべてのCDを揃える問題です。 各店舗が取り扱っているCDの種類は異なるため、複数の店舗を巡る必要があります。 店舗は店舗 $1$ から $K$ まで順番に数直線上に配置されており、距離は等間隔で $D$ メートルです。 店舗 $1$ から出発するとき、全てのCDを揃えるために何メートル歩く必要があるかを求めてください。

解法

重要な性質として、店舗 $i$ を訪れるならば道中で店舗 $i-1$ にも訪れることができるという性質があります。 店舗は直線状に並んでいるため、店舗 $1$ から店舗 $i$ までの通り道の中に店舗 $i-1$ が必ず含まれています。 この性質を利用すると、以下のように問題を言い換えることができます。

店舗 $1$ から店舗 $k$ までの店舗を訪れることで $N$ 種類のCDが揃うような最小の $k$ を求め、$D \times (k-1)$ を出力せよ。

各CDは店舗 $1$ から一番近い店舗で買うとして良いです。そのため、この問題は $N$ 種類のCDのうちすでに購入したCDの種類をフラグで管理することによって $\mathrm{O}(NK)$ で解くことができます。疑似コードは以下の通りです。

# 入力: N,K,D:整数, shop_CD_list: 各店舗が取り扱っているCDのリスト 
# 出力: 答え

flag を長さ N の配列として 0 で初期化する

for k = 1 to N do
  for CD in shop_CD_list[k] do
    flag[CD] = 1 # 店舗 k が扱っているCDを購入したとしてflagを立てる
  end for
  if flag の各要素が全て 1:
    return D(k-1) # 店舗 k までで K 種類のCDが全て揃った
end for

raise Error # N個の店舗を巡れば必ずK種類のCDが手に入るはずなため、エラーを出す