AtCoder ABC #006 : Python練習編

ABC#006に参加。
ABCまでは順調に解けたけど、Dでちょっと手こずった。
http://abc006.contest.atcoder.jp/assignments

A - 世界のFizzBuzz

1～9のいずれかの数字が与えられる。
その数字が3を含むか3の倍数であるなら"YES"を、違うなら"NO"を返せ。

1ケタなので「3を含む」は3しかなく、結局３の倍数だけ判定するだけ。

import sys

N=input()
if N%3 > 0:
	print "NO"
else:
	print "YES"

B - トリボナッチ数列

A(0)=0, A(1)=0, A(2)=1, A(i)=A(i-3)+A(i-2)+A(i-1) (i >=3 )
とする。Nに対してA(N)を求めよ。

N<=10^6なので地道に求めるだけでよい。

import sys

N=input()
A=[0,0,1]

if N<=3:
	print A[N-1]
else:
	N -= 3
	while N > 0:
		N-=1
		A=[A[1],A[2],(A[0]+A[1]+A[2])%10007]
	
	print A[2]

C - スフィンクスのなぞなぞ

N,Mが与えられたとき、
x + y + z = N
2x + 3y + 4z = M
x,y,z >= 0
を満たす整数z,y,zがあれば答えよ。

xを0～Nで総当たりしつつ、式変形より：

• z = (M-x*2)-3*(N-x)
• y = N-x-z

を求めてy,zが0以上になるのを選べばよい。O(N)で済む。

import sys

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

for x in range(0,N+1):
	z = (M-x*2)-3*(N-x)
	y = N-x-z
	if y >= 0 and z >= 0:
		print "%d %d %d" % (x,y,z)
		sys.exit()

print "-1 -1 -1"

D - トランプ挿入ソート

1～Nのpermutationとなっている数列が与えられる。
1回のオペレーションで、ある数字を別の位置に動かせる。
数列を昇順にする最小処理回数を求めよ。

考えていくと、元々ソートされている部分列は動かさなくていいけど、それ以外は動かさないといけないので、「元々ソートされている最長部分列」、結局Longest Increasing Subsequenceに含まれない数字を動かすのが最小と気づく。

よって後はN-LIS長が答え。
LISを求めるので計算量はO(NlogN)。

C++ならlower_boundやupper_boundを使うところだけど、pythonならbisectなんてモジュールで二分探索ができるのね。

import sys
import bisect

N=input()
LIS = []

for x in range(0,N):
	y = input()
	z = bisect.bisect_left(LIS, y)
	if z >= len(LIS):
		LIS.append(y)
	else:
		LIS[z]=y

print N-len(LIS)

まとめ

DがLISと気づくまでに時間とWAを掛けてしまった…。