B - Share It Now

2 secs 1024 MB

この問題は剰余を問います。

$J_i:=$ 宝石 $i$ の個数 $(1\le i\le M)$ とします。
宝石 $i$ を $S$ 人全員で同じ量ずつ配ることができるのは $J_i\ mod\ S=0$ となるときです。なお $x\ mod\ y$ は $x$ を $y$ で割ったあまりを表します。

$J_i\ mod\ S\neq 0$ のとき、 $S$ 人全員で同じ量ずつ分け合うために必要な宝石 $i$ の個数 $E_i$ は $S-(J_i\ mod\ S)$ 個です。これが正しいことは、あまりの性質を用いて示すことができます。一方 $J_i\ mod\ S= 0$ のとき、明らかに $S$ 人で配り切れるので、 $E_i=0$ とするのが適切です。

また答えが equality となる条件は、すべての $i$ に対し $E_i=0$ が成り立つことであることも明らかです。

以上からこの問題は $O(N\max (L_i)+M)$ で解くことが可能です。以下、解答例(C++,Python)です。

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<P,vector<P>,greater<P>>;
ll inf = 8e18;
int iinf = (int)1e9;
int mod9 = 998244353;
int mod1 = 1000000007;
struct Edge { int to; int cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){return (int)a.size();}
​
int main(void){
    int n,m,s; cin >> n >> m >> s;
    vector<int> J(m,0),E(m,0);
    rep(i,n){
        int l; cin >> l;
        rep(j,l){
            int a; cin >> a;
            J[a-1]++;
        }
    }
​
    bool z = 1;
    rep(i,m){
        E[i] = (J[i]%s == 0 ? 0 : s-J[i]%s);
        if(E[i] > 0) z = 0;
    }
    if(z) cout << "equality";
    else rep(i,m) cout << E[i] << (i == m-1 ? "\n" : " ");
}
​

xxxxxxxxxx
 
n,m,s = map(int,input().split())
​
J = [0 for i in range(m)]
​
ans = 0
for i in range(n):
    d = list(map(int,input().split()))
    L = d[0]
    for j in range(L):
        J[d[j+1]-1] += 1
​
z = 1
E = [0 for i in range(m)]
for i in range(m):
    if J[i]%s != 0:
        z = 0
    
    if J[i]%s == 0:
        E[i] = 0
    else:
        E[i] = s-(J[i]%s)
​
if z:
    print("equality")
else:
  print(*E)
​