kmjp's blog

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

AtCoder ABC #027 : Python練習編

ARC

電車の中で参加しており、途中乗り換えでドタバタしていてだいぶタイムロスした。
http://abc027.contest.atcoder.jp/assignments

A - 長方形

長方形のうち３辺の長さが与えられる。
残り１辺の長さを求めよ。

３辺中２辺は長さが等しいはずである。
よって残りの１辺は、与えられていない辺と同じ長さのはずである。

A=map(int,raw_input().strip().split(" "))
A.sort()

if A[0]==A[1]:
	print A[2]
else:
	print A[0]

B - 島と橋

N個の島が順に並んでおり、それぞれA[i]人がいる。
いくつか隣接する島の間に橋を渡すことを考える。
橋を渡した島の間は自由に人が行き来できる。
各島にいる人数が等しくなるように人が移動できるためには、最低何本橋が必要か。

まず前提としてsum(A)はNの倍数であることをチェックする。
すると1島あたりave=sum(A)/N人の人がいるようにすればよい。

i番の島と(i+1)番の島に橋を渡す必要があるかどうかを考える。
sum(A[0..i])がave*(i+1)に一致しない場合、i番までの島で条件を満たせないので、(i+1)番の島と橋を渡す必要がある。

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

sum = 0
for a in A:
	sum += a

if sum % N > 0:
	print -1
else:
	ave = sum/N
	tot = num = res = 0
	for a in A:
		tot += a
		num += 1
		if tot != ave*num:
			res += 1
	print res

C - 倍々ゲーム

２人で交互にターンが来るゲームを行う。
初期状態で場の数値は1である。
自分の手番で、場の値を倍にするか、倍にして1足すかのどちらかを選ばなければならない。
自分の手番で場の値をNより大きくしたら負けである。
両者最適手を取る場合、勝者はどちらか。

Editorialとは違う解法。
Nを２進数表記して、1xxxxxと表現したとする。
自分の手番で倍にするか倍にして１足すかとは、実質xxxxxの部分を先頭から0で埋めるか1で埋めるか決めることに等しい。
ここでNの２進数表記の桁数より、最後の桁を決める者がどちらか定まる。
もし最後の桁まで埋めたとき、すでにNを超えるなら最後の桁を埋めたものが負け、N以下であれば(次の手番のものが必ずNを超えるので)最後の桁を埋めたものが勝ちである。

よって最後の手番の人は場の値を小さく、最後の手番でない人は場の値を大きくしようとする。
N=1xxxxxとしてxxxxxの部分を上から埋めていく場合：

  • 最後の手番でない側の手番のとき、対応するxが0なら、そこで1を埋めてしまえば最終的にNを超えるので、最後の手番でないほうの勝利である。
  • 最後の手番側の手番のとき、対応するxが1なら、そこで0を埋めてしまえば最終的にN未満になるので、最後の手番のほうの勝利である。
N=input()
step = 0
while 1<<(step+1) <= N:
	step += 1

res = 0
if step % 2 == 0:
	res = 0
	for i in range(step):
		if i%2==0 and (N&(1<<(step-1-i)))==0:
			res = 1
			break
		elif i%2==1 and (N&(1<<(step-1-i)))>0:
			res = 0
			break
else:
	res = 1
	for i in range(step):
		if i%2==0 and (N&(1<<(step-1-i)))>0:
			res = 1
			break
		elif i%2==1 and (N&(1<<(step-1-i)))==0:
			res = 0
			break

ans=["Takahashi","Aoki"]
print ans[1-res]

D - ロボット

数直線上で動くロボットに指令を与える。初期状態でロボットは原点にいる。
指令は"M+-"の３種類の文字で構成された文字列であり、ロボットはこの文字列を先頭から解釈して以下のように動く。

  • コマンド+ : スコアに現在の座標の値を足す
  • コマンド- : スコアからに現在の座標の値を引く
  • コマンドM : ロボットの位置を正か負の方向に1動かす

最終的にロボットが原点にいなければならないとするとき、得られる最高スコアを求めよ。

コマンドMに対しどちらに動かすかが、最終スコアにどの程度影響を与えるかを考える。
その影響は、以後に登場する"+-"の数で決まることは想像がつく。
よってまず各コマンドMに対し、上記その時の選択の影響度合いを求めよう。

最終的にロボットが原点にいるということは、コマンドMのうち半分は正、半分は負の向きに動かさなければならないことになる。
よって、先に求めた影響度合いのうち、大きい順半分を正方向の移動に割り当てればよい。

S=raw_input().strip()[::-1]

V=[]
cur=0
for c in S:
	if c=="+":
		cur+=1
	elif c=="-":
		cur-=1
	else:
		V.append(cur)

V.sort()
res = 0
for i in range(len(V)):
	if i < len(V)/2:
		res -= V[i]
	else:
		res += V[i]
print res

まとめ

解けはしたけどABCにしては考察パートが難しめ。