唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

AtCoder Beginner Contest 026 ◯◯◯◯

競技プログラミング atcoder

めずらしく全問解けたけど、WAをたくさん出して61位

公式の解説

www.slideshare.net

A: 掛け算の最大値 - AtCoder Beginner Contest 026 | AtCoder

総和が\(A\)になるような\(x, y\)について最大の\(x \times y\)を答える

\(x\)が\(\lfloor A \rfloor\)の時最大になるけど、制約が緩いので適当に総当りしても通る

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

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

N = n()

ret = 0
for i in xrange(N):
    for j in xrange(N):
        if i + j == N:
            ret = max(ret, i * j)
print ret

B: N重丸 - AtCoder Beginner Contest 026 | AtCoder

半径が\(N\)個与えられる
同じ位置からそれぞれの半径で円を書く
外側の円周から交互に赤と白で色を塗っていく時、赤色の部分の面積の総和を答える

半径をソートして、交互に円の面積を足し引きしていけばよい

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

def fn():
    return [int(raw_input().strip()) for i in xrange(input())]

R = fn()

R.sort(reverse=True)

ret = 0
for i, r in enumerate(R):
    if i % 2 == 0:
        ret += math.pi * r * r
    else:
        ret -= math.pi * r * r

print ret

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder

すべての社員についてそれぞれの上司が一人与えられる
部下がいない社員の給料は\(1\)、部下がいる社員の給料は、部下の給料の最大値と最小値に\(1\)を加えた値となる
社員の給料を求める

再帰で計算していくだけ

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

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

N = n()
B = [n() - 1 for i in xrange(N - 1)]
up = [-1] * N
down = collections.defaultdict(list)
for i, b in enumerate(B, 1):
    up[i] = b
    down[b].append(i)

price = {}

def dfs(i):
    if i in price:
        return price[i]
    if down[i]:
        temp = [dfs(j) for j in down[i]]
        p = max(temp) + min(temp) + 1
        price[i] = p
        return p
    else:
        price[i] = 1
        return 1

print dfs(0)

D: 高橋君ボール1号 - AtCoder Beginner Contest 026 | AtCoder

\(f(t) = A \times t + B \sin(C \times t \times \pi)\)の形の関数について、\(A, B, C\)が与えられた時に\(f(t')=100\)となる\(t'\)を求める

\(f(t)\)から\(100\)を引いた\(g(t) = f(t) - 100\)を考えて、\(g(t)=0\)となる\(t\)を求める問題に帰着したほうがわかりやすい
後は二分法を使って解のありうる範囲を狭めていけばよい

本番は最後のケースだけ何度もWAを出し続けてしまったorz
本番ではdecimalを使ってみたら通ったけど、終了後に確かめたら指数表記(1.5e-15とかの形)になっていたかなにかで出力のフォーマットが間違っていたっぽいですね
print '{:.10f}'.format(num) のように小数点何桁まで出力するかを指定すれば通りました

pythonのstr.formatについては昔記事を書いたのでついでに貼っておきますsucrose.hatenablog.com

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

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

A, B, C = ln()

def calc(t):
    return A * t + B * math.sin(t * C * math.pi) - 100

ub = 300
lb = 0

mid = 0
while abs(calc(mid)) > 1e-8:
    mid = (ub + lb) / 2.0
    if calc(mid) >= 0:
        ub = mid
    else:
        lb = mid
else:
    print '{:.10f}'.format(mid)