プロコン問題ボツ作品シリーズ「買い物(NP)」

たまに自分の過去記事見まわったりするんですが、

プロコン問題ボツ作品シリーズ「買い物(未解決)」が有ったので、これを解決しよう。


http://www20.atpages.jp/lives/cnt/pcpp/index.php
取りやめた問題 > おかいもの
に、同じ問題があります。
問題文

maiさんは%$N$%個の欲しいものがある。
maiさんの住む町の周囲には%$M$%店舗の店があり、
それぞれの店には%$L$%種類の商品がある。

欲しいものリストには商品の重複は無い。
また、それぞれの店舗の商品は重複しない。
それぞれの店舗は、maiさんの欲しい物以外の商品は置いていない。
maiさんはすべての店舗を回ればすべての欲しい物が手に入ることが保障される。

maiさんが全ての欲しい物を手に入れるために必要な最小の訪問すべき店舗数を求め、出力する。


商品名は0からN-1までの自然数で表現される。

入力

N M
L0
B00 B01 B02 ...
L1
B10 B11 B12 ...
...

%$N$%:欲しい物の数
%$M$%:店の数
%$L$%:店で取り扱う商品の種類
%$B_{ij}$%:商品名%$(0 \le B_{ij} \le N-1)$%

出力

maiさんが全ての欲しい物を手に入れるために必要な最小の訪問すべき店舗数を出力する。


ケース
3 3
2
0 1
2
1 2
3
0 1 2


'商品0' '商品1' '商品2'が欲しい物。
店0には'商品0' '商品1'が置いてある。
店1には'商品1' '商品2'が置いてある。
店2には'商品0' '商品1' '商品2'が置いてある。
店0と店1の2店舗に行くことでも、欲しい物を全て手に入れることができるが、
店2の1店舗に行くことでも欲しい物を手に入れることができる。
よって、最小の訪問すべき店舗数は1





ここから本題

当時は投げ捨ててしまった問題なので、とりあえず解いてみる。


全探索解法


計算量は%$O(2^MN)$%
小さな入力N=M=10ならば短時間で結果が得られますが、N=M=50だとTLE(手元PC:4s)が目立ってくる。


店の商品数、商品が置いてある店舗数による貪欲法は不可能。テストケースと解が合わない。


部分問題に分割できないので、分割統治法(動的計画法)を適応することは出来ない。
(証明が必要)


訪問する店舗数を二分探索する、というのはどうだろう。
この方法なら全探索よりは高速になりそう。

訪問する店舗数を%$k$%と置くと、「k店舗回れば全部買えるか?」の判定には%$_mC_kn$%に比例する計算量が必要。
%$k$%が%$m/2$%に近いほど指数的に大きくなるのは仕方が無いかも。



気が向いたら二分探索の実装等の追記をするかもしれません。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : 俺ルール

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1467位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
265位
アクセスランキングを見る>>