ABC139E

自分の考えたことを文字として残して置きたかったので、ブログを始めてみました。

主にAtCoderの問題について書いていけたらと思っております。

手始めに、ABC139EをACできたので、それについてです。

（実行時間、メモリ共に良い結果ではありません）

（参考程度にお願いします）

解法としては、ほぼ解説（editional.pdf）の通りです。

ABC139Eは、各選手毎に試合する相手の選手の順番が決められているため、それ通りにトーナメントを組むことができるか、また組めた場合何日かかるかという問題です（ざっくり）

まず、試合数をmとします。

  int n; cin >> n;
  int m = n * (n-1) / 2;

次に、各試合に一意の値を割り当てる関数を定義します。

対戦する選手のpairとそれをキーにしたmapを使用して実装もしてみたのですが、見事にTLEし、メモリも爆発していたので難しそうです。上手くやればできるのかもしれません。

今回は、気になってしまったので選手の組合せから0～m-1の値を一意に計算する関数にしてみました。ただ、コンテスト中に考えてる暇はない気がするので、この後の処理が多少面倒になりますが、i*m+jとかで良いと思います。

ちなみに、計算式は書き出したものから導き出したものなので、意味は良くわかってないです（中途半端）

  auto make_game = [&](int i, int j) {
    if (i > j) swap(i, j);
    return (n-1+n-i)*i/2 + (j-i-1);
  };

関数が定義出来たら、隣接リストに、試合をノードとした有向グラフを読み込んでいきます。変数名のtは、tournamentの頭文字です。

degreeは、ここでは各試合の入次数を表しています。良い名前が思いつかなかった模様。

  vector<int> t[m];
  int degree[m] = {};
  for (int i = 0; i < n; i++) {
    int a[n-1];
    for (int j = 0; j < n-1; j++) {
      cin >> a[j];
      a[j]--;
    }
    for (int j = 0; j < n-2; j++) {
      int g = make_game(i, a[j]);
      int h = make_game(i, a[j+1]);
      t[g].push_back(h);
      degree[h]++;
    }
  }

グラフを読み込めたら、入次数が0の試合だけをキューに入れます。入次数が0の試合は、一日目に試合ができるということですね。

distは試合が何日目であるかを保存しておく配列です。

  queue<int> que;
  int dist[m];
  for (int i = 0; i < m; i++) {
    if (degree[i] == 0) {
      que.push(i);
      dist[i] = 1;
    }
  }

入次数が0の試合をキューに入れたら、その試合が指している試合の入次数を減らしていきます。

減らした時に入次数が0になった場合、試合可能になったということなので、何日目かを記録して、その試合をキューに入れます。

ついでに、答えで必要になるdistの最大値も計算します。

余談なのですが、この処理、トポロジカルソートと呼ばれるものなんですね。DAGの最長経路を求めるプログラムを探している時に知って、勉強になりました。

  int ans = 0;
  while (!que.empty()) {
    int g = que.front(); que.pop();
    for (int h : t[g]) {
      if (--degree[h] == 0) {
        que.push(h);
        dist[h] = dist[g] + 1;
        ans = max(ans, dist[h]);
      }
    }
  }

後は、グラフに閉路がないかどうかを確かめるだけです。

今回は、入次数が0になっていない試合がある場合、ループがあるということなので、degreeを見ていけば良いです。

  for (int i = 0; i < m; i++) {
    if (degree[i]) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;

以上で説明終了です。

書いてみた感想ですが、面倒ですし、説明するのは難しいですね。恐らく3日坊主になるでしょう。

あと、文章が酷すぎるので、いつか書き直したい。

では。