SRM685 div1 easy MultiplicationTable2

考えたこと

• ある数字iを削除できるのは(j$k) == iとなるj,kが存在しない事みたいな気持ちになる
• 削除する対象の数字を探索するのにO(n)、削除判定O(n^2)で繰り返すのにO(n)で間に合いそうという気持ちになる
• 数字が削除できるならするを繰り返すコードを書く
• サンプルで落ちる
• よくよく考えると2個以上まとめて削除しないとみたいなのがあるね
• 逆に集合に追加していくみたいな方面で考える
• 数iを追加するなら (i$i)、(i$j)、(j$i) (jはすでに集合に含まれている要素) も集合に含まれていないとだめ
• 集合の要素、集合に追加しないといけない要素をもって最低限必要な要素を追加していく
• 集合に最初に追加する要素をn通り試すのでO(n)
• 集合に追加しうるのは最大O(n)回
• 追加しないといけない要素の判定でO(nlogn)
• O(n^3logn)でいけそう
• 出すと通る

削除するコードを書いてたら遅くなりすぎた
考察したらせめてサンプルくらいは試しましょう（ア）

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool del[55];
class MultiplicationTable2 {
   public:
   int minimalGoodSet(vector <int> table)
  {
    int nn = table.size(), n = sqrt(nn);

    int ret = INF;
    for(int st=0; st<n; ++st) {
      set<int> s;
      stack<int> ns;
      ns.push(st);
      while(ns.size()) {
        int x = ns.top(); ns.pop();
        s.insert(x);
        if(s.find(table[x+x*n]) == s.end()) ns.push(table[x+x*n]);
        for(int i: s) {
          if(s.find(table[i+x*n]) == s.end()) ns.push(table[i+x*n]);
          if(s.find(table[x+i*n]) == s.end()) ns.push(table[x+i*n]);
        }
      }
      chmin(ret, (int)s.size());
    }

    return ret;
  }
};