AtCoder Beginner Contest 139 E - League 誤答コード(Resolved)

#include <bits/stdc++.h>
using namespace std;

vector<int> oneDay(vector<vector<int>> &order) {
  vector<int> erased;
  vector<int> used(order.size());

  for(int i=0;i<order.size();i++) {
    if(used[i]) continue;
    int size1 = order[i].size();
    if(size1 == 0) {
      continue;
    }
    int opponent = order[i][size1-1] - 1;
    if(opponent < i || used[opponent]) {
      continue;
    }
    int size2 = order[opponent].size();
    if(size2 == 0) {
      continue;
    }
    int opponentOpponent = order[opponent][size2-1] - 1;

    if (opponentOpponent == i) {
      erased.emplace_back(i);
      erased.emplace_back(opponent);
      used[opponent] = true;
    }
  }

  return erased;
}

int main() {
  int N;
  cin >> N;
  vector<vector<int> > order(N, vector<int>(N-1));

  for(int i=0;i<N;i++) {
    for(int j=0;j<N-1;j++) {
      cin >> order[i][j];
    }
  }

  int days = 0;

  int left = N * (N-1) / 2;

  int times = 0;

  while(left > 0) {
    times++;
    bool can = true;
    vector<int> erased = oneDay(order);

    if(erased.size() == 0) {
      can = false;
    } else {
      for(int i=0;i<erased.size();i++) {
        order[erased[i]].pop_back();
      }
    }

    left = left - (erased.size() / 2);

    if(!can || times > N*(N-1)/2) {
      days = -1;
      break;
    } else {
      days++;
    }
  }

  cout << days << endl;

  return 0;
}

 問題はこちら。

atcoder.jp

TLEが一つだけなくならない。おそらく1日に1試合しかできないかつN＝1000の時にTLEしてる。具体的には以下。(N=4の時)

1: 2, 3, 4
2: 3, 4, 1
3: 4, 2, 1
4: 3, 2, 1

どうやってTLEがなくなるか考える。（毎回order.size()でfor文を回しているつまり最悪1000回for文を回している。上の具体例かつN=1000だとN*(N-1)/2日つまり500000日かかるので、合計で500000000回for文を回すことになるのでTLEになって当然か。毎回order.size()の探索をしなくて良いような方法を考えるのが良さそう。）

追記用

(2020/04/03)追記。

TLEをなくすことができた。上のコードではoneday関数の中でorderを全て探索しているがその必要がないと気づいた。前日に試合を行った選手に関してだけ探索してやれば良い。なぜなら前日試合をしていない選手の最優先に対戦しなければいけない選手は変わっていないからである。beforeという前日に試合をした選手のvectorを作り、その中で探索をすれば良い。結果AC。

提出したコードはほとんど変わっていない。リンクはこちら。

atcoder.jp