問題一覧 > 通常問題

No.679 不思議マーケット

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 : 👑 horiesinitihoriesiniti / テスター : はむこはむこ
1 ProblemId : 1897 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-04-28 02:39:35

問題文

不思議マーケットは一直線の通路からなるスーパーである。
このマーケットでは商品には$1$~$n$までの番号が一つずつ振られており同じ商品は2つ以上は存在しない。
通路の入り口から出口までに$n$個の棚が通路に順番に置かれている。
一つの棚には$1$~$n$までの商品をどれか一種類置ける。

不思議マーケットでは、通路の入り口から出口までの棚を戻らずに順番に訪れる必要があり、また以下の不思議なルールが存在する。

  • $h_{(i,1)}$~$h_{(i,r_i)}$が全てかごに入っていた場合、商品$g_i$をその棚の前を通った際には必ずかごに入れないといけない。
  • そういった条件がない商品は、その棚の前を通った際に必ずかごに入れないといけない。
棚と商品の数$n$、商品$g_i$の必要な商品のリストが$m$件与えられる。
商品を適切に配置した時、最大何種類の商品を客のかごに入れさせることができるだろうか?

入力

$n$ $m$
$g_1$ $r_1$
$h_{(1,1)}$ $\dots$ $h_{(1,r_1)}$
$\vdots$
$g_i$ $r_i$
$h_{(i,1)}$ $\dots$ $h_{(i,r_i)}$
$\vdots$
$g_m$ $r_m$
$h_{(m,1)}$ $\dots$ $h_{(m,r_m)}$

$n$は商品の種類数と棚の数である。 $m$は特定の商品が全て買い物かごに入っている時にかごに入れないといけない商品の種類数である。

$1 \le n \le 500$

$0 \le m \le n$

$g_i$ $r_i$

$g_i$は商品の番号 $r_i$は$g_i$を買い物かごに入れさせる必要な商品の数

$1 \le g_i \le n$

$1 \le r_i \le 32$

$h_{(i,1)}$ $\dots$ $h_{(i,r_i)}$

$1 \le h_{(i,j)} \le n$

商品$g_i$を買い物かごに入れさせるための必要なグッズのリストである、その棚にたどり着くまでに$h_{(i,1)}$~$h_{(i,r_i)}$までを全て買い物かごに入れていたら客は商品$g_i$を買い物かごに入れないといけない
$i$が同じ$h_{(i,j)}$に重複はないと仮定してよい。
$g_i = g_j$ということもないと仮定してよい
$g_i = h_{(i,j)}$ということもない。

$m$件のデータに現れなかった商品($g_i$にない)は無条件で買い物かごに入れさせる商品である。

出力

適切に商品を並べた時、かごに入れさせる事ができる商品の種類数の最大値を答えよ。 最後に改行してください。

サンプル

サンプル1
入力
10 8
7 1
8
10 1
3
9 3
3 4 10
5 2
8 4
2 3
7 1 10
4 2
7 6
6 2
1 3
1 2
7 3
出力
10

適切に並べることで全商品をかごに入れさせることができる。

サンプル2
入力
8 7
2 1
1
8 1
1
3 2
2 8
4 1
3
5 2
3 6
6 3
3 4 7
7 1
5
出力
5

適切に並べた時最大5個の商品をかごに入れさせることができる。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。