'Unfair
'を出力せよA=5, B=7, C=9 1回目 A=16 B=14 C=12 2回目 A=26 B=28 C=30 3回目 A=58 B=56 C=54
各回の操作後の $A,B,C$ の値は、$xA+yB+zC$ で表せる。ここで、その値を $(x,y,z)$ で表すと、
0回目 A=(1,0,0) B=(0,1,0) C=(0,0,1) A-B=( 1,-1, 0) 1回目 A=(0,1,1) B=(1,0,1) C=(1,1,0) A-B=(-1, 1, 0) 2回目 A=(2,1,1) B=(1,2,1) C=(1,1,2) A-B=( 1,-1, 0) 3回目 A=(2,3,3) B=(3,2,3) C=(3,3,2) A-B=(-1, 1, 0) 4回目 A=(6,5,5) B=(5,6,5) C=(5,5,6) A-B=( 1,-1, 0) ...
で、結局 $K$ 回の操作後の $A-B$ の値は、$A,B$ の初期値を $A_0,B_0$ として、
となる。ちなみに、$A_0,B_0 \le 10^9$ なので、答えの絶対値は $10^{18}$ を超えない。
a, b, c, k = list(map(int, input().split())) if k % 2: print(b - a) else: print(a - b)
2 5 3 6 4 1 → 1 2 5 3 6 4 (1を先頭に移動) → 1 2 3 6 4 5 (5を末尾に移動) → 1 2 3 4 5 6 (6を末尾に移動)
3回で並び替えられた。
まず、1ずつ増加して昇順に並んでいる最長部分列を探す。
2 5 3 6 4 1 → 2 _ 3 _ 4 _
そしたら、その部分は動かさず、それ以外の要素を適切な順で先頭または末尾に移動するのが最良となる。
┌───────┐ ↓ │ 2 5 3 6 4 1 │ │ ↑ └──┴───┘
なので、回数を求めるだけなら $N-(最長部分列の長さ)$ を求めればよい。
n = int(input()) tmp = [0] * (n + 1) for p in map(int, (input() for _ in range(n))): tmp[p] = tmp[p - 1] + 1 print(n - max(tmp))
A = { 0 1 2 3 3 4 2} ↓ X { 0 0 0 0 0 0 0} { 0 0 1 0 0 1 0} (i=2,5に操作を適用) { 0 0 1 2 0 1 2} (i=3,6に操作を適用) { 0 0 1 2 3 1 2} (i=4に操作を適用) { 0 1 2 3 3 1 2} (i=1→2→3の順に操作を適用) { 0 1 2 3 3 4 2} (i=5に操作を適用)
9回で同じに出来た。
まず、無理なケース。
それ以外は可能。
$A_i$ と $A_{i+1}$ を比べた時、$A_i+1=A_{i+1}$ なら、$X_{i+1}$ は $X_i$ を目標の値にしてから1回の操作で $A_{i+1}$ にできる。
逆にそうで無い場合、その値を作るために0 1 2 3 …
と“1から積み上げて”いかないといけない。$A_i=v$ だった場合、$v$ 回かかる。
“1から積み上げる”必要のある値だけを末尾から作ることを考えると、自然と $X$ は $A$ と同じにできる。
A = { 0 1 2 3 3 4 2} ~ ~ ~ ←1から積み上げる必要のある数字 X { 0 0 0 0 0 1 2} 2回の操作で1,2を作る(2が残る) { 0 0 1 2 3 4 2} 4回の操作で1~4を作る(3,4が残る) { 0 1 2 3 3 4 2} 3回の操作で1,2,3を作る
def solve(n, aaa): if aaa[0] > 0: return -1 if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])): return -1 ans = 0 a0 = 0 for a1 in aaa[1:]: if a1 - a0 != 1: ans += a0 a0 = a1 return ans + a0 n = int(input()) aaa = list(map(int, (input() for _ in range(n)))) print(solve(n, aaa))
木が同型とは、こんな木があったとして、
○ /\ ● ● /\ /\ ○○○○
●の頂点を根としたら、どちらも
● /|\ ○ ○ ○ | ○ /\ ○○
という形になる。
過不足のないように説明しようとすると本家の問題文にあるような難しい書き方になるが、要はこの頂点のつながり方が同じならよい。
$T$ がどのような木なら、根とした時に同型となる頂点をうまく増やし、色数を減らせるだろうか。
ある中心となる頂点または辺を1つ決めて、そこに繋がる部分木が同じであれば、中心からの距離が等しい頂点同士は、同じ色に出来そう。部分木の途中で枝分かれがあったら、その枝分かれ以下も各木でみんな等しくする。
○ ←中心となる頂点 /|\ ○ ○ ○ ←同じ色に出来る /\ /\ /\ ○○○○○○ ←同じ色に出来る
↓中心となる辺 ○─────○ ←同じ色に出来る /|\ /|\ ○ ○ ○ ○ ○ ○ ←同じ色に出来る /\ /\ /\ /\ /\ /\ ○○○○○○○○○○○○ ←同じ色に出来る
逆に中心からの距離が異なる頂点同士は、根とした時の木の深さが必ず異なるため、同型にならない=同じ色に出来ない。
よって、中心はなるべく深さが浅くなるような頂点または辺を選ぶべき。つまり、木の直径を求め、その真ん中を採用すればよい。中心さえ決めれば、部分木が同じになるように頂点を追加するのは何とでもなる。
最小の色数は、直径の頂点数の半分(切り上げ)となる。
次に、葉の個数を求める。
中心となる頂点や辺を決めたら、$G$ に存在する各頂点の子の数を調べ、各深さで最大のものを取得する。
G ○─────○ ←3 /\ /|\ ○ ○ ○ ○ ○ ←2 /\ | | /\ ○○ ○ ○ ○○ ←(0)
この場合、$T$ の葉の個数は、$3 \times 2 \times 2$(中心が辺の場合、部分木が2つあるので2倍)で、12個となる。
G に頂点を追加した結果 ○─────○ /|\ /|\ ○ ○ ○ ○ ○ ○ /\ /\ /\ /\ /\ /\ ○○○○○○○○○○○○ ←12個
from collections import deque from functools import reduce from operator import mul def diameter(links): q = deque([(v, 0) for v in links[0]]) v = 0 while q: v, a = q.popleft() q.extend((u, v) for u in links[v] if u != a) anc = [-1] * len(links) q = deque([(u, v) for u in links[v]]) u = 0 while q: u, a = q.popleft() anc[u] = a q.extend((w, u) for w in links[u] if w != a) path = [u] a = u while a != v: a = anc[a] path.append(a) return path def calc(links, v, a, l): ans = [1] * l q = deque([(u, v, 1) for u in links[v] if u != a]) ans[0] = len(q) while q: u, a, c = q.popleft() ans[c] = max(ans[c], len(links[u]) - 1) q.extend((w, u, c + 1) for w in links[u] if w != a) return ans def solve(n, links): if n == 2: return 1, 2 path = diameter(links) c = len(path) l = (len(path) + 1) // 2 if c % 2 == 0: u, v = path[c // 2 - 1], path[c // 2] ans1 = calc(links, u, v, l) ans2 = calc(links, v, u, l) leaves = 1 for a1, a2 in zip(ans1, ans2): leaves *= max(a1, a2) return len(ans1), leaves * 2 v = path[c // 2] ans0 = calc(links, v, None, l) leaves = reduce(mul, ans0, 1) for u in links[v]: ans1 = calc(links, u, v, l) ans2 = calc(links, v, u, l) tmp = 1 for a1, a2 in zip(ans1, ans2): tmp *= max(a1, a2) leaves = min(leaves, tmp * 2) return len(ans0), leaves n = int(input()) links = [set() for _ in range(n)] for _ in range(n - 1): a, b = map(int, input().split()) a -= 1 b -= 1 links[a].add(b) links[b].add(a) print(*solve(n, links))