F - Alex's whims / Codeforces Round 909 (Div. 3)

問題

木構造のグラフとは、 ループを含まない 頂点 辺のグラフのことを指す。

頂点の木構造のグラフに対して、 日間で整数 が1日ごとに与えられる。 また、グラフは1日1回までなら、以下の操作を行うことができる。

• ある頂点 と、 に隣接している頂点 と隣接していない頂点 を選び、 と をつなぐ辺を削除して と に新たに辺をつなぐ。

日目の値 について、距離が である葉の組み合わせが存在しなければならないとき、それを与える 頂点の木構造のグラフの初期状態と、 日目にて選択すべき の値をそれぞれ求めよ。 ただし、操作を行う必要のない場合は とすること。

なお、「葉」とは「繋がっている辺が1つしかない頂点」を指す。

入力

まず最初の1行目に、テストケースの個数を表す整数 が与えられる。

その後、 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

• 最初の1行目には、整数 が与えられる。
• 次の 行のうち 行目には、整数 が与えられる。

条件

• 
• 
  • すべてのテストケースにおける の値の合計は を超えない。
• 
  • すべてのテストケースにおける の値の合計は を超えない。
• 

出力

それぞれのテストケースについて、以下のように出力すること。

• まず最初の 行には、初期状態の木構造グラフの辺の状態を出力すること。
  • すなわち、ある辺が頂点 を繋いでいるときには、 の値を1行で出力し、それを 本分行うこと。
• 次の 行には、 日目における の値をそれぞれ1行ずつ出力すること。

解法

頂点の木構造のグラフとして、一番単純な以下の図のようなものをまずは考えます。 なお、図の赤い頂点は葉を表しています。

このグラフは葉同士の距離が であり、 の条件を満たすグラフもこの形のもののみとなります。 そのため、このグラフをもとに辺の位置を変えて、すべての に対応できるような方法を考えます。

与えられる は葉同士の距離を与えるものなので、「ある葉に対して、変更後も葉になるように接続されている辺の変更をする」ことを行うと、条件を満たしやすくなると考えることができます。

例えば、先ほどのグラフに対して、頂点 に接続されている辺の接続先を頂点 から頂点 （ただし、 ）へと変更することを考えます。 このとき、変更後のグラフは以下のようになります。

図から示されるように、ここで頂点 は変更後も葉のままです。 また、頂点 から頂点 までの距離は であるため、頂点 から頂点 までの距離は となります。

以上の考察から、 であるので、 が与えられたら、頂点 の接続先の頂点を に変更することで、条件を満たせると言えます。

従ってこの問題を解くためには、まず「頂点 と頂点 、頂点 と頂点 、……、頂点 と頂点 」がそれぞれ接続されている木構造のグラフを初期状態として与えます。

そこからこのグラフの頂点 を必ず として、与えられた を用いて （直前に頂点 が接続されていた頂点）とし、 とすることで、答えが得られます。 ただし、 となる場合については辺の変更を行う必要がないので、 とします。

最初のグラフを出力する部分については ででき、その後の 個のクエリについても で処理できるため、この問題は の計算量で解くことができ、これは実行時間制限にも十分間に合います。

ソースコード

グラフ及び を出力するための関数 solve() を以下のように実装しました。

int n, q, d[505];

void solve() {
  // 値の入力
  cin >> n >> q;
  for (int i = 1; i <= q; i++) {
    cin >> d[i];
  }

  // 初期状態のグラフの出力
  for (int i = 1; i <= n - 1; i++) {
    cout << i << " " << i + 1 << endl;
  }

  int connected = n - 1; // connected は頂点 n に接続されている頂点を表す

  for (int i = 1; i <= q; i++) {
    if (connected == d[i]) { // 新しい接続先が connected と一致していれば、 u = v_1 = v_2 = -1 となる
      cout << "-1 -1 -1" << endl;
    } else {
      cout << n << " " << connected << " " << d[i] << endl;
      connected = d[i]; // connected の更新
    }
  }
  return;
}

• 提出したコード: https://codeforces.com/contest/1899/submission/237873741
• GitHub

感想

問題文自体が長いので、行うべきことを理解するための時間はかかりましたが、それが分かれば D問題 や E問題 よりも簡単なように思いました。