TopCoder SRM 635 Div2 oo- 1077->1168

41st, 729.46pts, +0/-0 challenge
Volatility: 515->501

1000点は解けそうな問題だったけど解けず
部屋で誰も1000点を説いている人がいなかったので部屋1位だった

• SRM 635 - Togetterまとめ

250: IdentifyingWood

文字列s, tが与えられる
tがsのsubsequenceであるかどうか判定する(sの任意の文字を削除してtと一致するかどうか)

手前から順に文字が一致するか確認していけばよい

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class IdentifyingWood:
    def check(self, s, t):
        idx = 0
        for c in s:
            if c == t[idx]:
                idx += 1
                if idx >= len(t):
                    return "Yep, it's wood."
        return "Nope."

500: QuadraticLaw

正の整数\(d\)が与えられる
\(t^2+t \leq d\)となる最大の整数\(t\)を求める

\(t=\sqrt d\)からスタートして条件をみたすかチェックしながら\(t\)を1ずつ減らしていけばすぐに見つかる
二分探索とか解の公式とかでも求められるっぽい
誤差(？)で死んでる人が結構いた

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class QuadraticLaw:
    def getTime(self, d):
        u = int(math.sqrt(d) + 1)
        for t in xrange(u, -1, -1):
            if t**2 + t <= d:
                return t
        return 0

1000: LonglongestPathTree

\(N\)個のノードを持つ木が与えられる(\(N-1\)個の辺を持つグラフ)
辺を一つ付け替えてもよいという条件のもとで木の直径(最も遠い2つのノードの距離)の最大値を答える

木の直径は以下のURLのように、あるノードから深さ優先探索して一番遠い点\(p\)を求めて、同様に\(p\)からもう一度深さ優先探索をして一番遠い点\(q\)を求めると、\(p, q\)が直径の端のノードとなっている

• Spaghetti Source - 木の直径

木から任意の辺を取り除くと2つの木に分かれるので、それぞれの辺を取り除いた場合について、2つの木と直径と取り除いた辺の長さを足したものの最大値を求めればよい
すべての辺それぞれを取り除いた場合についてグラフの直径を求めるので計算量は\(O(N^2)\)

以下のコードはTLE
他の言語で書き直せば間に合うはず(？)

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

class LonglongestPathTree:
    def getLength(self, A, B, L):
        sys.setrecursionlimit(10000)
        
        edge = collections.defaultdict(dict)
        l = len(A)
        for i in xrange(l):
            edge[A[i]][B[i]] = L[i]
            edge[B[i]][A[i]] = L[i]

        def visit(p, v, f):
            distance = 0
            cur = v
            for e in edge[v]:
                if e == p or (e in f and v in f):
                    continue
                temp = visit(v, e, f)
                temp[1] += edge[v][e]
                if distance < temp[1]:
                    distance = temp[1]
                    cur = temp[0]
            return [cur, distance]
        
        diameter = 0
        for i in xrange(l):
            cut = edge[A[i]][B[i]]
            f = set([A[i], B[i]])
            a1, b1 = visit(-1, A[i], f)
            c1, d1 = visit(-1, a1, f)
            a2, b2 = visit(-1, B[i], f)
            c2, d2 = visit(-1, a2, f)
            diameter_new = d1 + d2 + cut
            if diameter < diameter_new:
                diameter = diameter_new
        return diameter