AtCoder ABC #002 : Python練習編

ABC002も不参加。後で練習した際ノーミスで10分切れたので、出ていれば上位に入れたかも…。
今回はABC001より難易度が低め。やはりPythonで復習。
http://abc002.contest.atcoder.jp/assignments

A - 正直者

２値の大きい方を返せ。
書くだけ。

import sys
print "%d" % max(map(int,raw_input().strip().split(" ")))

B - 罠

文字列から母音を除いて返せ。
正規表現などでもいいのだろうけど、まじめに書いてみた。

import sys

w=raw_input()
s=""
for c in w:
	if c=='a':
		continue
	elif c=='i':
		continue
	elif c=='u':
		continue
	elif c=='e':
		continue
	elif c=='o':
		continue
	s += c

print s

C - 直訴

３点が与えられるので３角形の面積を返せ。

１点が原点の時、面積はになる。
ただ、これだといったん３点をずらして原点にもっていかないといけない。
１点が原点でないとき、と書けることを知った。

import sys

a=map(int,raw_input().strip().split(" "))

s=a[0]*(a[3]-a[5])+a[2]*(a[5]-a[1])+a[4]*(a[1]-a[3])
print "%f" % (abs(s)/2.0)

D - 派閥

最大N<=12点の最大クリーク問題。
クリークに入れる点を総当たりでBitDPしてもループ回数は2^N * N^2程度なので問題なく終わる。

import sys

ma=[[0 for j in range(12)] for i in range(12)]
N,M=map(int,raw_input().strip().split(" "))

for i in range(0,M):
	x,y=map(int,raw_input().strip().split(" "))
	ma[x-1][y-1]=ma[y-1][x-1]=1

re=0
for mask in range(0,1<<N):
	bi=0
	ng =0
	for x in range(0,N):
		if (mask & (1<<x)) == 0:
			continue
		bi += 1
		
		for y in range(0,N):
			if x==y:
				continue
			if (mask & (1<<y)) == 0:
				continue
			if ma[x][y]==0:
				ng = 1
	
	if ng==0 and bi > re:
		re = bi

print re

まとめ

えらく簡単だけどABC001で難しいという意見があったのだろうか。