B - Sports Festival

問題

atcoder.jp
かなり考察したのに解けなかった。悔しいのでここで供養します。

考察

・を使いたいとすると、用いることができるスポーツはを満たすような
ただし、その他の行で何が一番になるか比較するのは計算量的に怪しい(と思う)
・あるに着目してから実験するのはかなり難しい。

正解

最も参加人数の多いスポーツがスポーツ P で、その参加人数が Q 人だとします。当
り前ですが、この段階で、参加人数の最大値が Q の解が得られています。よって、あと考えるべき
は、参加人数の最大値が Q 未満の解です。そして、そのような解において、スポーツ P は必ず実
施されません。なので、Q 未満の解を求めるには、スポーツ P を候補から外した上で、もう一度
同じ問題を解きなおせばよいです

悔しすぎる。単純に、参加者が多いスポーツを候補から外せばいいという事がわかる。
できないと感じながら実装したのが間違いだった &　そうなったときに新しい切り口を見つけるのが今後の課題かも。

解答

#include<bits/stdc++.h>
using namespace std;
set<int>S;
int ans = 1e8;
void simulate(vector<vector<int>>&g){
    map<int,int>cnt;
    for(int i = 0; i < g.size(); ++i){
        for(int j = 0; j < g[i].size(); ++j){
            auto crt = g[i][j];
            if(S.find(crt) == S.end()){continue;}
            cnt[crt]++;
            break;
        }
    }
    int maxim = -1, num = -1;
    for(auto itr : cnt)
        if(maxim < itr.second)
            maxim = itr.second, num = itr.first;
    ans = min(ans,maxim);
    S.erase(num);
    if(not S.empty()) simulate(g);
}
int main(){
    int N,M; cin >> N >> M;
    vector<vector<int>>g(N,vector<int>(M));
    for(auto& v : g)
        for(auto&  e: v) cin >> e;
    for(int i = 1; i <= M; ++i){
        S.insert(i);
    }
    simulate(g);
    cout << ans << endl;
}