kmjp's blog

競技プログラミング参加記です

AtCoder ABC #026 : Python練習編

今回は普通に簡単目でした。
とはいえFAは1個も取れず。
http://abc026.contest.atcoder.jp/assignments

A - 掛け算の最大値

正の偶数Aが与えられる。
x+y=Aとなる正整数x,yに対し、x*yの最大値を求めよ。

x=y=A/2が最大。
以下のコードは無駄にAが奇数でも良いように書いてしまった。

import math

A=input()
print (A/2)*(A-A/2)

B - N重丸

原点を中心にN個の異なる半径R[i]の円を描いた。
そして弓道の的のように、円と円の間を赤白で塗った。
赤く塗った領域の面積を求めよ。

Rを降順にソートする。
(1-originで)奇数番目の面積を答えに足し、偶数番目の分を引けばよい。

import math

N=input()
R=[]
for i in range(N):
	R.append(input())

R.sort()
R.reverse()

ret=0
for i in range(len(R)):
	if i & 1:
		ret -= R[i]*R[i]*math.pi
	else:
		ret += R[i]*R[i]*math.pi

print ret

C - 高橋君の給料

1~N番の社員番号を持つN人の社員がいる。
1番以外のi番の社員は、自分より小さい番号B[i]の上司を持つ。

  • 部下のいない社員の給料は1である。
  • 部下のいる社員の給料は、1+(直接の部下中の給料最大値)+(直接の部下中の給料最小値)である。

1番の社員の給料を求めよ。

愚直に大きな番号の社員から給料を確定させればよい。

import sys
import math

N=input()
B=[0]
C=[[0 for i in range(0)] for j in range(55)]

for i in range(N-1):
	B.append(input()-1)

for i in range(N-1,-1,-1):
	P = 1
	if len(C[i])>0:
		C[i].sort()
		P += C[i][0] + C[i][-1]
	
	if i==0:
		print P
	else:
		C[B[i]].append(P)

D - 高橋君ボール1号

正整数A,B,Cに対し、 f(t)=A \times t + B \times \sin (C \times t \times \pi)とする。
f(t)=0となる正のtを一つ答えよ。

f(t)はsinを含むのでf'(t)は局所的にはマイナスになるが、全体的にはプラスである。

以下のコードは最小なt値を求めているケース。
よって0.001区切り位でf(x)≦100かつf(x+0.001)≧100となるxを総当たりで求め、あとはxとx+0.001の間で二分探索をしてf(t)を求めればよい。

最小でなくても良いなら、単にtを0と大きな数字の間で二分探索すればよい。

import sys
import math

def func(t):
	return A*t+B*math.sin(C*t*math.pi)

A,B,C=map(int,raw_input().strip().split(" "))

L=R=0.0
i = 0
while 1:
	if func(i/1000.0)<=100 and func((i+1)/1000.0)>=100:
		L = i/1000.0
		R = (i+1)/1000.0
		break
	i += 1

for i in range(100):
	M = (L+R)/2.0
	if func(M) < 100:
		L = M
	else:
		R = M

print L

まとめ

この記事書こうとしてA問題の入力が偶数固定であることに気づいた…。