UVa 13037 - Chocolate

Source

A Bangladeshi Contest at SUST（20151212）
UVa 13037

問題概要

Leju，Rony，Sujonという人たちがそれぞれ $L, R, S$ 個のチョコレートを持っている．
チョコレートにはタイプが有り，
　Lejuが持っているチョコレートのタイプは $A_1,A_2,\ldots,A_L$
　Ronyが持っているチョコレートのタイプは $B_1,B_2,\ldots,B_R$
　Sujonが持っているチョコレートのタイプは $C_1,C_2,\ldots,C_S$
である．
Leju，Rony，Sujonのそれぞれに対して，その人しか持っていないタイプはいくつあるか，その人だけが持っていないタイプはいくつあるかを求める問題．

• テストケースの数 $T$ は $T \leq 15$ を満たす
• $1 \leq L, R, S \leq 100000\ (10^5)$
• $0 \leq A_i,B_,C_i < 100000\ (10^5)$
• $i \neq j$ に対して $A_i=A_j$ などということもありうる

解法

各タイプについて，誰が持っているかを求めてやって，各タイプが出力する $6$ パターンのどれかにあたるなら，その答えをインクリメントしていけば良い．
時間計算量は $O(L+R+S+\max(A_i,B_i,C_i))$ 程度．

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります．

Current time: 2024年04月17日00時31分20秒
Last modified: 2015年12月16日01時46分10秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)