【アルゴリズム問題】yukicoder no.11 カードマッチ (level ☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】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

2種類のマークと5つの数字の組み合わせのトランプを使用する。
この場合
「マーク1の1以外の4種類」と、「マーク2の1」がマッチする。


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

https://gist.githubusercontent.com/yuki2006/5bfcbe0ff507276a5c8b/raw/0b0c777590f5f0f197a2df030171f2a6aba663a0/yukicoder11.txt


想定解法 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

広告
×
デジネイさんの撃墜入力 http://melpon.org/wandbox/permlink/z5zijQ3Ka2yHudih
縦横のuniq数がそれぞれ違うサンプルがあるとよかったかも。
65ヶ月前
×
すいません、ありがとうございます!
チャレンジポイント加算しました。

ありがとうございます!
次回は意識していきたいと思います。
65ヶ月前
コメントを書く
コメントをするには、
ログインして下さい。