kmjp's blog

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

AtCoder ABC #017 : Python練習編

ARC

ABCは本選不参加。
本選でてたらDで何回かWA出して微妙な順位に終わってそう。
http://abc017.contest.atcoder.jp/assignments

A - プロコン

３つの課題の配点と、高橋君が得た評価が与えられる。
評価は１０段階で、１につき配点の１割が与えられる。
高橋君の得点を答えよ。

得点*評価/10を足すだけ。

import sys
import math

N,K=map(int,raw_input().strip().split(" "))
R = N*K/10
N,K=map(int,raw_input().strip().split(" "))
R += N*K/10
N,K=map(int,raw_input().strip().split(" "))
R += N*K/10

print R

B - choku語

choku語とは以下のルールで構成される文字列である。

  • 空文字列はchoku語である。
  • choku語の末尾に"ch""o""k""u"のいずれかの文字列を付与したもの。

文字列が与えられるので、choku語か答えよ。
先頭なり末尾から"ch""o""k""u"を取り除けるだけ取り除き、空文字になるか判定する。

import sys
import math

S=raw_input().strip()

while len(S) > 0:
	if S.startswith("ch"):
		S=S[2:]
	elif S.startswith("o") or S.startswith("k") or S.startswith("u"):
		S=S[1:]
	else:
		print "NO"
		sys.exit(0)

print "YES"

C - ハイスコア

N個の遺跡がある。それぞれは探索してもしなくても良く、探索するとL[i]～R[i]番の宝石と、S[i]の得点を得ることができる。
宝石は1～MのM種類あり、全種類取得してしまう事は許されない。
全部の宝石をそろえない範囲で得られる最大得点を答えよ。

ある宝石を取らないことで失う(得ることができなくなる)得点を1～Mまで求め、そのうちの最小値を得点の総和から引けばよい。
失う得点の求め方は、累積和を用いてO(N+M)で行う方法と、BITを2つ使う方法もある。

自分は最初後者で解いたらPythonで3.3秒もかかったが、前者なら1秒かからない。

import sys
import math

N,K=map(int,raw_input().strip().split(" "))
val=[0]*101000
tot=0

for i in range(0,N):
	x,y,z=map(int,raw_input().strip().split(" "))
	tot += z
	val[x]+=z
	val[y+1]-=z

ret = 0
for i in range(1,K+1):
	val[i]+=val[i-1]
	ret = max(ret, tot-val[i])

print ret

D - サプリメント

N種類のサプリメントを順に摂りたい。
１日あたり、最低１つのサプリメントを摂らなければならない。
また、１日に複数のサプリメントを摂ることができるが、味F[i]が重複する複数のサプリメントは同日に取ることができない。
各サプリメントの味F[i]が与えられるとき、サプリメントの摂り方の組み合わせを答えよ。

x個目までのサプリメントの摂りかたの組み合わせをdp[x]とし、dp[1]～dp[x]の総和をS[x]とする。
x個目のサプリメントの摂り方は、x個目と同時に取れるサプリメントの番号の最小値をM[x]として
dp[x]=dp[M[x]]+dp[M[x]+1]+...+dp[x-1]=S[x-1]-S[M[x]-1]
とおくことができる。
直前に味pのサプリメントが登場した番号をnum[p]とすると、
M[x]=min(M[x-1], num[F[x]])
でM[x]を更新できる。

両方合わせて、O(N)のDPで解ける。

import sys
import math

N,M=map(int,raw_input().strip().split(" "))
dp=[0]*(N+2)
S=[0]*(N+2)

dp[1]=S[1]=1
mo=1000000007
prev=[1]*100003

le=1
for i in range(0,N):
	f=input()
	le = max(le, prev[f])
	
	dp[i+2]=(S[i+1]-S[le-1]+mo)%mo
	S[i+2]=(S[i+1]+dp[i+2])%mo
	prev[f]=i+2

print ((dp[N+1]%mo)+mo)%mo

まとめ

Cで無駄にBIT解書いてしまったのがもったいなかった。
WAこそ出てないけど、PythonのBITライブラリ持ってなかったので時間を食った。