読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

AtCoder ARC #001 : Python練習編

Pythonを勉強しよう…ということで、難易度がお手頃なARCのA~C相当の問題にチャレンジ。
手順としては、AとBを全部やった後Cをやってる。
本当はPython3系を使いたかったけど、AtCoderは2.7系なので2.7系で解いてみた。
なお、コード上からimport文は省略してます。

1回やった問題なので説明は最小限に。ではARC#001から。
http://arc001.contest.atcoder.jp/assignments

A - センター採点

記念すべき最初のPythonプログラム。
1~4の登場する数を連想配列でカウントしてみた。

N=input()
str=list(raw_input())
a={"1":0,"2":0,"3":0,"4":0}
for s in str:
	a[s] = a[s] + 1

print "%d %d"%(max(a.values()),min(a.values()))

B - リモコン

一度に1度・5度・10度動かせるボタンを使って、最小の操作で目的の温度に動かす。
面倒なので、5度と10度動かす回数を列挙して最小操作回数を求める。

A,B=map(int,raw_input().split(" "))
mi=999
for x10 in range(-10,10):
	for x5 in range(-10,10):
		mi=min(mi,abs(x10)+abs(x5)+abs(A+x10*10+x5*5-B))

print mi

C - パズルのお手伝い

8クイーン問題において3個クイーンが与えられたとき、あと5個を答える。
DFSするだけなんだけど、まだ関数の使い方に慣れていないのでちょっと苦戦。

M=[]
for y in range(8):
	M.append(list(raw_input()))

def check(y,x):
	for i in range(8):
		if i!=x and M[y][i]=='Q':
			return 0
		if i!=y and M[i][x]=='Q':
			return 0
	
	for i in range(1,8):
		if y-i>=0 and x-i>=0 and M[y-i][x-i]=='Q':
			return 0
		if y-i>=0 and x+i<8 and M[y-i][x+i]=='Q':
			return 0
		if y+i<8 and x-i>=0 and M[y+i][x-i]=='Q':
			return 0
		if y+i<8 and x+i<8 and M[y+i][x+i]=='Q':
			return 0
	return 1

def dfs(left,cy):
	if left == 0:
		for m in M:
			print("".join(m))
		exit()
	for y in range(cy,8):
		for x in range(8):
			if M[y][x]=='Q':
				continue
			if check(y,x)==0:
				continue
			M[y][x]='Q'
			dfs(left-1,y+1)
			M[y][x]='.'

for y in range(8):
	for x in range(8):
		if M[y][x]=='Q' and check(y,x)==0:
			print("No Answer")
			exit()

dfs(5,0)
print("No Answer")

まとめ

やはりC++より行数が短くなるのはよい。

広告を非表示にする