kmjp's blog

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

AtCoder ABC #023 : Python練習編

無駄WAが無ければ…と思ったけど、無くても順位1個しか変わらなかった。
http://abc023.contest.atcoder.jp/assignments

A - 加算王

2桁の整数Nが与えられる。
両桁の和を答えよ。

題意の通り和を取ればよい。

N=input()
print N/10+N%10

B - 手芸王

初期状態で文字列Tは"b"である。

  • 3n+1手目ではTの先頭に"a"、末尾に"c"を付与する。
  • 3n+2手目ではTの先頭に"c"、末尾に"a"を付与する。
  • 3n手目ではTの先頭に"b"、末尾に"b"を付与する。

上記処理を何手か繰り返して入力文字列Sと一致するなら、その手数を求めよ。

Tの長さは単調増加なので、Sの長さを超えるまでシミュレーションすればよい。
以下のコードでは、先にTが100文字を超えるまでシミュレーションして配列に加え、最後にSと一致するものがあるか探索している。

import sys

L=input()
S=raw_input().strip()
A=["b"]

while len(A[-1])<=100:
	A.append("a"+A[-1]+"c")
	A.append("c"+A[-1]+"a")
	A.append("b"+A[-1]+"b")

for i in range(len(A)):
	if A[i] == S:
		print i
		sys.exit(0)

print -1

C - 収集王

R*Cのグリッド上の異なるN個のセル(r[i],c[i])に飴がある。
プレイヤーはあるセルを選択すると、そのセルと同じ列または同じ行のセルにある飴を回収できる。
回収する飴の数がK個になるような選択セルの数を求めよ。

まず、各行・各列に何個飴があるかをそれぞれ求める。
y行目にある飴をNR(y)個、x列目にある飴をNC(x)個と表現することにする。
セル(y,x)を選択したときの飴の数はNR(y)+NC(x) (厳密には異なる。後述)となる。
NR(y)+NC(x)==Kとなるような(y,x)の数を高速に求めたい。

飴の数pに対し、NC(x)==pとなるxの数(すなわちp個飴がある列の数)をf(p)とする。
すると(y,x)の和は \sum_y f(K - NR_y)となる。

ただしまだ問題があって、(y,x)自体に飴がある場合、NR(y)+NC(x)では同じ飴を2回カウントしてしまっている。
よって飴のある各セル(r[i],c[i])について:

  • NR(r[i])+NC(c[i])==Kは飴の二重カウントが無ければK-1個なので、前述のsumの処理で余分に答えに加えてしまった分を1減らす
  • NR(r[i])+NC(c[i])==K+1だったら飴の二重カウントの影響を考慮するとちょうど飴がK個となるので答えを1増やす
R,C,K = map(int,raw_input().strip().split(" "))
N = input()

NR = [0]*R
NC = [0]*C
cand = []

for i in range(N):
	r,c=map(int,raw_input().strip().split(" "))
	cand.append((r-1,c-1))
	NR[r-1] += 1
	NC[c-1] += 1

CS = [0]*101000
for nc in NC:
	CS[nc] += 1

ret = 0
for nr in NR:
	left = K - nr
	if left >= 0:
		ret += CS[left]

for (r,c) in cand:
	if NR[r] + NC[c] == K:
		ret -= 1
	if NR[r] + NC[c] == K+1:
		ret += 1

print ret

D - 射撃王

N個の風船がある。
i番目の風船は、初期状態で高さH[i]にあり、1秒毎にS[i]上昇する。
プレイヤーは(0秒から初めて)1秒毎に1個風船を割ることができる。
その際、割った時点での高さの最大値がプレイヤーのスコアになる。
最適な順で風船を全て割ったとき、プレイヤーの最小スコアを求めよ。

二分探索を用いてスコアの最小値を求める。
最終的なスコアがVと仮定すると、各風船は(V-H[i])/S[i]以内に割らなければならない。

プレイヤーは当然早く風船を割った方が有利なので、0~(N-1)秒の間に1個ずつ風船を割る。
逆に0~(N-1)秒の間に1個ずつ風船を割って間に合うなら、スコアVを達成できる。

「0~(N-1)秒の間に1個ずつ風船を割る」が成り立つには、i秒目までに割らなければいけない風船がi個を超えなければ良い。

N=input()
B=[]

def ok(v):
	D=[0]*N
	for (h,s) in B:
		if v < h:
			return False
		t = (v-h)/s
		if t < N:
			D[t] += 1
	
	x = 0
	for i in range(N):
		if x > i:
			return False
		x += D[i]
	return True

for i in range(N):
	h,s=map(int,raw_input().strip().split(" "))
	B.append((h,s))

ret = (1<<51)-1
for i in range(50,-1,-1):
	if ok(ret - (1<<i)):
		ret -= 1<<i

print ret

まとめ

Cの難易度が徐々に上昇している?

広告を非表示にする