## A. Ciel and Robot

まあ分かる。なんだか好きな感じの問題。

## 解答

#!/usr/bin/env python3
import operator
table = {
'U' : ( 0,  1),
'D' : ( 0, -1),
'L' : (-1,  0),
'R' : ( 1,  0) }

a, b = map(int,input().split())
s = list(input())

zs = set()
x, y = 0, 0
for c in s:
x, y = map(operator.add, (x, y), table[c])

result = False
for (zx, zy) in zs:
p, q = a - zx, b - zy
if (x == 0 and p != 0) or (x != 0 and p % x != 0) or (x != 0 and p // x < 0): continue
if (y == 0 and q != 0) or (y != 0 and q % y != 0) or (y != 0 and q // y < 0): continue
if x != 0 and y != 0 and p // x != q // y: continue
result = True

print('Yes' if result else 'No')


if文のあたりが怖い。andnotだけじゃなくてimplies論理演算子が欲しいです。でも<=は嫌です。

## B. Ciel and Duel

### 解答

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
typedef long long ll;
using namespace std;
ll strategy_exceeding(vector<int> xs, vector<int> zs) {
{
int n = xs.size();
int m = zs.size();
if (n < m) {
zs.erase(zs.begin(), zs.end() - n);
} else if (n > m) {
xs.erase(xs.begin() + m, xs.end());
}
}
assert (xs.size() == zs.size());
int n = xs.size();
ll result = 0;
repeat (i,n) {
ll acc = 0;
repeat_from (j,i,n) {
if (zs[j] < xs[j-i]) break;
acc += zs[j] - xs[j-i];
}
result = max(result, acc);
}
return result;
}
ll strategy_direct(vector<int> const & xs, vector<int> const & ys, vector<int> zs) {
if (xs.size() + ys.size() >= zs.size()) return 0;
repeat (i,int(ys.size())) {
auto it = lower_bound(zs.begin(), zs.end(), ys[i]+1);
if (it == zs.end()) return 0;
zs.erase(it);
}
ll result = 0;
repeat (i,int(xs.size())) {
auto it = lower_bound(zs.begin(), zs.end(), xs[i]);
if (it == zs.end()) return 0;
result += *it - xs[i];
zs.erase(it);
}
result += accumulate(zs.begin(), zs.end(), 0);
return result;
}
int main() {
int n, m; cin >> n >> m;
vector<int> xs; // atk
vector<int> ys; // def
repeat (i,n) {
string a; int b; cin >> a >> b;
(a == "ATK" ? xs : ys).push_back(b);
}
vector<int> zs(m);
repeat (i,m) cin >> zs[i];
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
sort(zs.begin(), zs.end());
cout << max(strategy_exceeding(xs, zs), strategy_direct(xs, ys, zs)) << endl;
return 0;
}


## C. Ciel the Commander

これの解法を木の重心分解とか呼ぶらしいというのは通してから知った。

### 解法

まずそのような記号の振り方の存在に関して、必ず存在する。明らかに一番厳しい場合である直線状の木を考えても、

A
BAB
CBCACBC
EDECEDEBEDECEDEAEDECEDEBEDECEDE
FEFDFEFCFEFDFEFBFEFDFEFCFEFDFEFAFEFDFEFCFEFDFEFBFEFDFEFCFEFDFEF
...


とすれば$10^5 \ll 2^{26}-1$なので十分記号は足りる。

このような記号の振り方を求める。まず最も遠い頂点との距離が最小であるような頂点Pを求め、そこに記号'A'を振る。その頂点を除いて木を分割し、小さくなった木々を対し再帰的に処理する。木の直径(頂点間の距離で最大のもの)が、適当な点から最も遠い点Aとその点Aから最も遠い点Bの距離で与えられる、という事実を使ってそのような点Pを求めた。

O(n \log n)。 グラフの頂点数が必ず半分以下になるとは限らないので、$n \log n$よりちょっと大きくなるかも。

### 解答

#include <iostream>
#include <vector>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
using namespace std;
std::pair<int,int> deepest_node(int i, int p, vector<vector<int> > const & g, vector<char> const & used) {
int result = i; int depth = 0;
for (int j : g[i]) if (j != p and not used[j]) {
auto q = deepest_node(j, i, g, used);
if (depth < q.second + 1) {
result = q.first;
depth = q.second + 1;
}
}
return make_pair(result, depth);
}
int find_by_depth(int target, int current, int i, int p, vector<vector<int> > const & g, vector<char> const & used) {
if (target == current) return i;
for (int j : g[i]) if (j != p and not used[j]) {
int k = find_by_depth(target, current + 1, j, i, g, used);
if (k != -1) return k;
}
return -1;
}
void f(int i, char c, vector<vector<int> > const & g, vector<char> & result) {
assert ('A' <= c and c <= 'Z');
assert (not result[i]);
int j = deepest_node(i, -1, g, result).first;
int diameter = deepest_node(j, -1, g, result).second;
int k = find_by_depth(diameter / 2, 0, j, -1, g, result);
assert (k != -1);
result[k] = c;
for (int l : g[k]) if (not result[l]) {
f(l, c+1, g, result);
}
}
vector<char> solve(vector<vector<int> > const & g) {
vector<char> result(g.size(), '\0');
f(0, 'A', g, result);
return result;
}
int main() {
int n; cin >> n;
assert (n < (1<<26)-1);
vector<vector<int> > g(n);
repeat (i,n-1) {
int a, b; cin >> a >> b; -- a; -- b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<char> s = solve(g);
cout << s[0]; repeat_from (i,1,n) cout << ' ' << s[i]; cout << endl;
return 0;
}


# Codeforces Round #190 (Div. 1)

• Fri Sep 4 21:31:03 JST 2015
• 重心じゃなかったので訂正