[第一回日本最強プログラマー学生選手権-予選-] D - Classified

[Q] https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d

エスパーだけど、貪欲的に解答。
考察

N=4のとき

(NG) BFS的に二部グラフを作ってみると K=3 で構成される
1.
1-2
|\
4 3

2.
1 2
 /|
4 3

3.
1 2

4-3

(OK) DFS的に二部グラフを作ってみると K=2 で構成される
1.
1-2
| |
4-3

2.
1 2
 X
4 3

0. DFSで辺を消費しようと思う。そしてこれがAC。
1. 全頂点への有向グラフを張る。大きい数字へ移動できるとする。
G[0] = {1,2,3,4,..,N-1}
G[1] = {2,3,4,...,N-1}
2. 頂点を赤と黒で塗分けていく。同じ色への移動は許されない。
3. 使用した辺はeraseする。
Q. eraseたくさんするなら、vectorよりlistのほうが早い？
A. vectorのほうが早い。なぜ？？

N=500
vector: 31ms
list: 59ms

N=2000
vector: 875ms
list: 2785ms

vectorでeraseしたら、後ろにある要素を全部コピーしなおすから、最悪O(N)と思ってた。
listでeraseしたら、前後への移動を繋ぎ変えるだけだからO(1)と思ってた。
ところが要素2000以下ならvectorのほうが早いようだ。

実装

vector<ll> G[505];
ll N;
ll ans[505][505];
ll cnts;  // N-1C2になったらおしまい

void dfs(ll v, vector<ll> &col, ll &n) {
 for (auto it = G[v].begin(); it != G[v].end(); ++it) {
   auto u = *it;
   if (col[u] == col[v]) continue;
   col[u] = -col[v];
   ++cnts;
   ans[min(u, v)][max(u, v)] = n;
   G[v].erase(it--);
   dfs(u, col, n);
 }
}

int main() {
 cincout();

 cin >> N;
 ll fin = N * (N - 1) / 2;

 rep(i, N) {
   G[i].reserve(N - i);
   for (ll j = i + 1; j < N; ++j) {
     G[i].push_back(j);
   }
 }
 ll nb = 0;
 while (cnts < fin) {
   ++nb;
   vector<ll> col(N, 0); // 0:default +-1:color
   rep(i, N) {
     if (col[i] == 0) col[i] = 1;
     dfs(i, col, nb);
   }
 }

 rep(i, N) {
   for (ll j = i + 1; j < N; ++j) {
     cout << ans[i][j] << " \n"[j == N - 1];
   }
 }
}

https://atcoder.jp/contests/jsc2019-qual/submissions/30942687