AtCoder ABC #004 : Python練習編

ABC004に参加。Dで少し無駄足を踏んでしまったけど、順当に全問ノーミスで解けた。
Pythonで復習。
http://abc004.contest.atcoder.jp/assignments

A - 流行

数Nが与えられるので倍の値を返せ。
書くだけ。

N=input()
print 2*N

B - 回転

4x4の盤面が与えられるので、180度回転せよ。
x,y座標をそれぞれ逆順に出力する。

S=[]
S.append(raw_input())
S.append(raw_input())
S.append(raw_input())
S.append(raw_input())

print S[3][6] + " " + S[3][4] + " " + S[3][2] + " " + S[3][0]
print S[2][6] + " " + S[2][4] + " " + S[2][2] + " " + S[2][0]
print S[1][6] + " " + S[1][4] + " " + S[1][2] + " " + S[1][0]
print S[0][6] + " " + S[0][4] + " " + S[0][2] + " " + S[0][0]

C - 入れ替え

初期状態で1,2,3,4,5,6の順にカードが並んでいる。
ここでN回カードのswapを行うが、i回目には (i mod 5)+1 番目と(i mod 5)+2番目のカードを交換する。
N回後のカードの状態を返せ。

状態は30回ごとにループすることがわかるので、N%30回シミュレートするだけ。

N=input()
N%=30
V=[1,2,3,4,5,6]

for i in range(0,N):
	j = i%5
	V[j],V[j+1] = V[j+1],V[j]

print "%d%d%d%d%d%d" % (V[0],V[1],V[2],V[3],V[4],V[5])

D - マーブル

初期状態で座標-100に赤い石、0に緑の石、100に青い石がそれぞれ複数ある。
コストを１払うと各石を１動かすことができる。

赤・緑・青の石の数が与えられた場合、各座標に最大１個までしか石が来ないように移動する最小コストを答えよ。

赤い石群・緑の石群・青の石群はそれぞれ離れた位置に置く必要もないので、それぞれの群は連続した領域にある。
よって、各群の開始座標を総当たりして、コストを最小化すればよい。

…と本番はそう解いた。500^3位適当に回しても時間内に解けるしね。
Pythonで解くとそうは行かない。そこで高速化することを考える。

各色石がX個ある場合、その色だけに関しては最小コストは-X/2～X/2までの範囲に石を置くことである。
他の石群が邪魔な時、そのような配置はできない場合があるが、-X/2～X/2の範囲に近い程コストが低いのが明らかである。

そこで、真ん中の緑の石群の位置だけ総当たりで決めると、赤と青の最適位置が決まるのでO(N)で解ける。

R,G,B=map(int,raw_input().strip().split(" "))

def calc(x,num):
	if x <= -num:
		return (-x-x-num+1)*num/2
	if x >= 0:
		return (x+x+num-1)*num/2
		
	y=x+num-1
	x=-x
	return (x+1)*x/2+(y+1)*y/2

mi=100000000

for g in range(-400,400):
	r = min(g-R,-100-R/2)
	b = max(g+G,100-B/2)
	mi = min(mi,calc(r+100,R)+calc(g,G)+calc(b-100,B))

print mi

まとめ

Dが最初からC++でもO(N)でないと解けない上限値だったら、もう少し手こずってたかも。