エンジニアの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 |
ツリーの同じ長さの枝を束ねていって最後に1本になればその長さを、ならなければ-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アドテク部ではプログラミングコンテストが好きなエンジニアも募集しています。