AD-TECH
Lab BLOG
アドテクLab ブログ

NEWS
  • リクルートデータ組織のブログをはじめました。※最新情報はRecruit Data Blogをご覧ください。
  • Recruit Data Blogはこちら

【RCO プロコン部活動日誌】Codeforces Round 397 & E 問題 "Tree Folding" レビュー

2017/02/15kenkoooo

このエントリーをはてなブックマークに追加

エンジニアのkenkooooです。最近仕事で Trie を実装しました。

RCOアドテク部には「プロコン部」というサークルがあり、各自でプログラミングコンテストに参加して、 終了後に解法を検討したり、コンテスト中に不正解となったコードをみんなでデバッグしたりしています。今回は Codeforces が開催する Codeforces Round #397 というコンテストに参加しました。

結果は以下のとおりです。


結果

全体順位 ハンドル A B C D E F G Hack 合計
65 uwi 498 987 1060 1830 1834 - - +100 6309
113 tomerun 496 984 1214 1808 1414 - - - 5916
301 shiratty8 496 982 1207 1750 - - - - 4435
589 kenkoooo 368 881 1064 1643 - - - - 3956
870 iehn 444 820 737 1328 - - - - 3329
2558 kobiki 348 643 - - - - - - 991


E 問題 “Tree Folding” レビュー

問題ページ

ツリーの同じ長さの枝を束ねていって最後に1本になればその長さを、ならなければ-1を出力する問題です。コンテスト中は着手の時に「最終的な長さは直径になるのでは？」といった勘違いをして時間を浪費してしまいましたが、コンテスト終了後に考えて理解したので、ここで紹介します。


解法

ツリーを葉から見ていき、同じ長さの枝があれば束ねていきます。このとき、自分より下の枝が全て処理が終わっていることを確認してから進むように注意します。

  • ある頂点vに3種類以上の長さの枝がある場合は、どうやっても直線にするのは不可能です。
  • 2種類の長さの枝がぶら下がっている場合、それら以外に枝が存在しなければ、それらが最後の直線になります。そうでない場合は直線にするのは不可能です。
  • 1種類ぶら下がっている場合、または0種類ぶら下がっている場合（つまり葉である場合）は、その枝+1の長さの枝を親に渡します。

これらの作業を繰り返して上に登っていきます。最後の直線の長さが偶数の場合、さらに2つ折りに出来るので、その仕上げも忘れずに行います。


実装例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.TreeSet;

public class TreeFolding {

  private int solve(BufferedReader in) throws IOException {
    int N = Integer.parseInt(in.readLine());
    ArrayList<Integer>[] tree = new ArrayList[N];

    //branches[v] := vにぶら下がっている枝の数
    TreeSet<Integer>[] branches = new TreeSet[N];

    //done[v] := vより下の枝で処理が終わった物の数
    int[] done = new int[N];

    boolean[] visited = new boolean[N];
    for (int i = 0; i < N; i++) {
      tree[i] = new ArrayList<>();
      branches[i] = new TreeSet<>();
    }

    for (int i = 0; i < N - 1; i++) {
      String[] line = in.readLine().split(" ");
      int u = Integer.parseInt(line[0]) - 1;
      int v = Integer.parseInt(line[1]) - 1;
      tree[v].add(u);
      tree[u].add(v);
    }

    ArrayDeque<Integer> deque = new ArrayDeque<>();

    //葉をキューに詰める
    for (int i = 0; i < N; i++) {
      if (tree[i].size() == 1) {
        deque.add(i);
      }
    }

    while (!deque.isEmpty()) {
      int v = deque.poll();
      visited[v] = true;

      //vに3種類以上の長さの枝がぶら下がっている場合どうやっても不可能なので終了する
      if (branches[v].size() >= 3) {
        return -1;
      }

      //v以外の枝のマージが全て終わったとき、ツリーは直線になっているはずである
      if (done[v] == tree[v].size()) {
        int ans = 0;
        for (int branch : branches[v]) {
          ans += branch;
        }

        //半分に折れる限り折る
        while (ans % 2 == 0) {
          ans /= 2;
        }
        return ans;
      }

      //自分の下にある枝の長さの種類が2のとき、vは中心になっているはずであるが、
      // その場合は既に処理が終わっているはずなので、vは中心でない
      if (branches[v].size() == 2) {
        return -1;
      }

      //vにぶら下がっている枝の長さ
      int length = branches[v].isEmpty() ? 0 : branches[v].first();

      for (int parent : tree[v]) {
        if (visited[parent]) {
          continue;
        }

        done[parent]++;
        branches[parent].add(length + 1);

        //parentより下の枝のマージが終わったらキューに詰める
        if (done[parent] + 1 == tree[parent].size()) {
          deque.add(parent);
        }
      }
    }
    throw new IllegalStateException();
  }


  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int ans = new TreeFolding().solve(in);
    System.out.println(ans);
    in.close();
  }
}


今回のご飯

オフィス近くの八重洲地下街の大丸では色んなお弁当を売っていて、今回は叙々苑の焼肉弁当をチョイスしました。


広告

RCOアドテク部ではプログラミングコンテストが好きなエンジニアも募集しています。

採用ページ

TAGS :

#プロコン部活動
前の記事

ARCHIVE

月別記事リストを見る

CATEGORY

カテゴリ別で見る