閉じる
閉じる
×
【アルゴリズム問題】yukicoder no.11 カードマッチ (level ☆)
2014-08-05 18:35
- 2
Jenはトランプゲームをしている。
Jenは(表面を見ることができる)手札にあるいずれかのカードと、手札以外にあるカードのマッチするカードの枚数を知りたくなった。
このトランプは、マークがW種類あり、数字は1からHで構成されており、組み合わせの重複はないとする。
ここでいうマッチするとは、マークまたは数字のどちらかが一致するカードのことである。
（今回の場合、どちらともに一致する場合はそのカードそのものである）
つまり、すべてのカードはW*H枚のカードが有る。
今、手札にはN枚のカードがあり、「手札のカード以外」のマッチするカードの枚数を求めてください。
W*H がintに収まらない場合があります。
入力
W
H
N
S1 K1
S2 K2
・・
Si Ki
・・
SN KN (半角スペース区切り）
制約
1<=W<=1,000,000
1<=H<=1,000,000
1<=i<=N<=min (W*H,100)
1<=Si<=W
1<=Ki<=H
ideoneでTLEしなければよいです。(5秒以内）
sample1
2
5
1
1 1
ans1
5
２種類のマークと５つの数字の組み合わせのトランプを使用する。
この場合
「マーク１の１以外の４種類」と、「マーク２の１」がマッチする。
sample2
4
13
3
1 1
2 1
2 5
ans2
27
普通のトランプのセットと同様である。
この時マッチするのは
「マーク1の1以外」と「マーク2の1,5以外」と「マーク3とマーク4の1と5」である。
sample3
4
13
4
1 5
2 6
3 7
4 8
ans3
48
sample4
3
2
2
1 1
2 1
ans4
3
なおさんに提供いただきました。
q
想定解法 python
http://ideone.com/2iS4YT
また、色々あって申し訳ないです。
1st . なおさん C++
http://ideone.com/ETciYf
2nd. myonさん Haskell
http://melpon.org/wandbox/permlink/fsMRlfpDlY7gjQn7
3rd.nanashiさん Java
http://ideone.com/N5n1WX
広告
