AGC018 B : Sports Festival(700)
作成日：2017.07.24
最終更新日：2017.07.24
問題概要
$1$から$M$までの順列$A_{i1},A_{i2},...,A_{iM}$が$N$個ある。
$1$から$M$の空でない部分集合$S$において、各順列を頭から見たときにはじめて出てくる$S$の要素を挙げていく。
$S$を適切に選んだ時、同じ要素が挙げられた回数の最大値の最小値を求めよ。
制約
$1 \leq N \leq 300$
$1 \leq M \leq 300$
考え方
愚直にやると計算量が$O(2^M N)$になって間に合わないので工夫したい。
とりあえず、ある$S$で問題概要の2文目の操作を行った後、$S$に要素を加えたり取り除いたりするとどうなるかを考える。
要素を加えたときは、再び頭から見ていく必要がある。しかし要素を取り除いたときは、今挙げた要素から順番に見ていけば良い。
つまり、はじめは$S$として$1$から$M$すべてを入れた集合をとり、その後次々に要素を取り除いていくときの計算量は$O(NM)$であると期待できる。
では、どのような要素を取り除いていけば良いだろうか。
問題では最小値を求められているのだから、これを更新するように要素を取り除けば良い。
すなわち、その時点で挙げられた回数が最も多い要素を取り除けば良い。
というのも、その要素を取り除かない限り挙げられた要素は挙げられたままなので、最大値は決して減らないからである。
ソースコード
マクロ等はこちら
const int MC = 333;
int N,M;
int A[MC][MC];
int x[MC]; //現在挙げられている要素の位置
bool b[MC]; //Sに入っていない要素
int c[MC]; //要素が挙げられている回数
int p,ans; //pはその時点で挙げられた回数が最も多い要素を保持
int main(){
scanf("%d%d" , &N , &M);
repp(i,0,N){
repp(j,1,M+1){
scanf("%d" , A[i]+j);
}
x[i] = 1;
++c[A[i][1]];
}
repp(j,1,M+1) if(c[p] < c[j]) p = j;
ans = c[p];
repp(k,1,M){
b[p] = 1;
repp(i,0,N){
while(b[A[i][x[i]]]){
--c[A[i][x[i]]];
++x[i];
++c[A[i][x[i]]];
}
}
p = 0;
repp(j,1,M+1) if(c[p] < c[j]) p = j;
ans = min(ans , c[p]);
}
printf("%d\n" , ans);
return 0;
}解法まとめ
はじめは$S$として$1$から$M$すべてを入れた集合をとる。(15-19行)
あとは毎回、その時点で挙げられた回数が最も多い要素を取り除いて計算し直す。(20-32行)
このコードでは計算量は$O(NM + M^2)$である。