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

AtCoder Beginner Contest 006 復習

atcoder 復習

はい。
http://abc006.contest.atcoder.jp

A - 世界のFizzBuzz

Python2

n=raw_input()
print 'YES' if n=='3' or int(n)%3==0 else 'NO'

3を含むかはstrで見て、割り切れるかの判定の時にintでキャストしました。

B - トリボナッチ数列

Python2

n=int(raw_input())
l=[0]*(4)
l[3]=1
 
for i in range(4,10**6+1):
    l.append(((l[i-1]+l[i-2])%10007+l[-3])%10007)
print l[n]

最後だけで%10007しようとすると中間で数が大きくなりすぎるのと計算が遅くなったりするので常に余りだけみてれば良いと思う。計算結果も変わらないです。 n番目だけわかれば、解だけわかれば良いので配列で全部持たずに a1, a2, a3=a2, a3, (a1+a2+a3)%10007 でもよかったかな、と。但し、1つのテストケースで複数件のクエリがあるなら配列で持つほうがよいはず。

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

Python2

n,m=map(int,raw_input().split())
tmp=n*3
if tmp==m:
    print 0,n,0
elif n*3<m<=4*n:
    print 0,n-m+tmp,m-tmp
elif  2*n<=m<3*n:
    print tmp-m,n-tmp+m,0
else:
    print -1,-1,-1

前はループで探してたようだが式が思いついてそれで通ってしまった。3本足を基準にして考えて、mの方が大きければ4本足を増やし、mの方が小さければ2本足を増やす感じで。2本足、4本足は同時に使う必要はないはずです。2本足が1人と4本足が1人で合計6本足、3本足が2人で合計6本足。はい、同じですね。

D - トランプ挿入ソート

Python2

import bisect

def lis(c):
    l=[]
    l.append(c[0])
    ans=1
    for i in range(1,n):
        if l[ans-1]<c[i]:
            l.append(c[i])
            ans+=1
        else:
            tmp=bisect.bisect_right(l,c[i])
            l[tmp]=c[i]
    return ans

n=int(raw_input())
N=range(1,n)
c=[]
for i in range(n):
    c.append(int(raw_input()))
print n-lis(c)

最長部分増加列(LIS)を使う。 LISとはなんぞやはabc006の解説資料や、AOJのDPLのD問題:Longest Increasing Subsequenceを参照で。AOJの擬似コードをほぼそのまま使いました。全体の長さ - 最長増加部分列 が解になるのは、増加から外れてる数だけ移動が必要だからかな?多分。
LISが末尾より小さい数であったらLISの長さを変えずに中身を変えるのは極端な例だと1, 5, 6, 2, 3, 4という数列があったとすると、6まで見た時に1, 5, 6となっている時に長さを変えずに5を2に置換して〜〜でないと1, 2, 3, 4を作れないからです。多分。