AtCoder Beginner Contest #014 ooox

Welcome to AtCoder Beginner Contest #014 - AtCoder Beginner Contest #014 | AtCoder
知り合いとLINEで会話してゲームのテストプレイに付き合いながら参加。
D問題が解けたと思ったらPythonが遅すぎてTLEだった

公式の解説

AtCoder Beginner Contest 014 解説 from chokudai

A: けんしょう先生のお菓子配り - AtCoder Beginner Contest #014 | AtCoder

a個あるものをb人に均等に配るには追加で何個必要か

bで割り切れない時は、aをbで割ったあまりをbから引いたものを答えればよい

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

def n():
    return int(raw_input())

a = n()
b = n()

print (b - a % b if a % b != 0 else 0)

B: 価格の合計 - AtCoder Beginner Contest #014 | AtCoder

入力のビットが1になっている部分の要素の総和を求める

Pythonには数値を二進文字列に直すbin関数があるのでビット演算を陽にやらなくてもよい

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

def ln():
    return map(int, raw_input().strip().split())

N, X = ln()
a = ln()
b = bin(X)[::-1]

s = 0
L = len(b)
for i in xrange(N):
    if i >= L:
        break
    if b[i] == '1':
        s += a[i]
print s

C: AtColor - AtCoder Beginner Contest #014 | AtCoder

複数の区間が与えられる
いずれかの場所で最大何個の区間が重複しているかを答える

いわゆるいもす法を使った

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

def n():
    return int(raw_input())
def ln():
    return map(int, raw_input().strip().split())


P = [0] * 1000002
N = n()
for i in xrange(N):
    a, b = ln()
    P[a] += 1
    P[b + 1] -= 1

cur = 0
M = 0
for i in xrange(1000002):
    cur += P[i]
    if cur > M:
        M = cur

print M

D: 閉路 - AtCoder Beginner Contest #014 | AtCoder

木構造に辺を一本足すと閉路ができる
追加の辺の位置が複数与えられるので、それぞれの閉路の長さを答える

頂点同士の距離がわかれば、閉路はそれに+1すればよい
単純に全点間の距離を求めると時間が足りないので、木構造であることを利用する

2つの頂点から根\(root\)の方にたどっていった時の最初の共通の祖先を( \(LCA\) , Lowest Common Ancestor)と呼ぶ
2つの頂点\(p, q\)間の距離は次のように求められる
$$ d(p, q) = d(p, root) + d(q, root) - 2 \times d(LCA, root) $$

LCAはいくつか求める方法があるらしいが、蟻本の上級編4-3 グラフマスターへの道のところに載っていたダブリング(二分探索？)を使った方法を実装した
この方法は2つの頂点\(p, q\)が与えられた時に頂点数の対数のオーダーで\(LCA\)が求められる

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

以下のコードはTLEになるので注意

# -*- coding: utf-8 -*-
import heapq,collections,sys,random,math

sys.setrecursionlimit(200000)
def ln():
    return map(int, raw_input().strip().split())

d = collections.defaultdict(dict)
N = input()
for i in xrange(N - 1):
    x, y = ln()
    d[x-1][y-1] = 1
    d[y-1][x-1] = 1
Q = input()
query = [ln() for i in xrange(Q)]
 
z = [10000000] * N
def dijkstra(s):
    dist = z[:]
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        dv = dist[v]
        if dv < dd:
            continue
        for i in d[v]:
            dvi = d[v][i]
            if dist[i] > dv + dvi:
                dist[i] = dv + dvi
                heapq.heappush(heap, (dist[i], i))
    return dist

MAX_LOG_V = 20

parent = [[-1] * N for i in xrange(MAX_LOG_V)]
dep = [0] * N
def depth(v, p, de):
    parent[0][v] = p
    dep[v] = de
    for i in d[v]:
        if i != p:
            depth(i, v, de + 1)

depth(0, -1, 0)
result = dijkstra(0)

for k in xrange(MAX_LOG_V - 1):
    for v in xrange(N):
        if parent[k][v] < 0:
            parent[k + 1][v] = -1
        else:
            parent[k + 1][v] = parent[k][parent[k][v]]

def lca(u, v):
    if dep[u] > dep[v]:
        u, v = v, u
    for k in xrange(MAX_LOG_V):
        if (dep[v] - dep[u]) >> k & 1 :
            v = parent[k][v]
    if u == v:
        return u
    for k in xrange(MAX_LOG_V - 1, -1, -1):
        if parent[k][u] != parent[k][v]:
            u = parent[k][u]
            v = parent[k][v]
    return parent[0][u]

for a, b in query:
    print result[a - 1] + result[b - 1] - 2 * result[lca(a - 1, b - 1) ] + 1