kmjp's blog

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

AtCoder ARC #018 : Python練習編

Pythonでも練習。Dは行列計算などPythonではちょっと重いのでABCのみ。
http://arc018.contest.atcoder.jp/assignments

AtCoder ARC #018 : A - BMI、B - 格子点と整数 - kmjp's blog
AtCoder ARC #018 : C - 席替え - kmjp's blog

A - BMI

単純に計算するだけ。
毎度入力の受け取り方を忘れる…。

import sys

H,B=map(float,raw_input().strip().split(" "))

print B*H*H/10000.0

B - 格子点と整数

こちらもC++同様O(V^3)のアルゴリズムで間に合います。

import sys

N=input()
X=[]
Y=[]
for i in range(0,N):
	x,y=map(int,raw_input().strip().split(" "))
	X.append(x)
	Y.append(y)

r=0
for x in range(0,N):
	for y in range(x+1,N):
		for z in range(y+1,N):
			ret = (Y[y]-Y[x])*(X[z]-X[x])-(X[y]-X[x])*(Y[z]-Y[x])
			if ret != 0 and ret % 2 == 0:
				r = r + 1

print r

C - 席替え

席の数が10^6と多くPythonでは心配だったけど大丈夫だった。

import sys
import math

N,M=map(int,raw_input().strip().split(" "))
X0,A,P=map(int,raw_input().strip().split(" "))

if A == 0:
	if X0 >= P:
		print 2*(N-1)
	else:
		print 0
	sys.exit(0)

X=[]
for i in range(0,N*M):
	X.append((X0,i))
	X0 = (X0 + A) % P

X.sort()

ret = 0
for y in range(0,N):
	L=[]
	for x in range(0,M):
		ret += math.fabs(X[y*M+x][1]/M - y)
		L.append(X[y*M+x][1]%M)
	L.sort()
	for i in range(0,M):
		ret += math.fabs(L[i]-i)

print int(ret)

まとめ

ここまでの範囲はC++だと間に合うけどPythonだと間に合わないって問題はなかったな。
Dは100x100の行列式計算とか大変そうなのでやめておきます。