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

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #388 (Div.2)

はい。
http://codeforces.com/contest/749

A. Bachgold Problem

ざっくりと大意

・バッハゴールド
・与えられた整数nはk個の素数の和で表せる。kとのその素数を出力する。

Python3

n=int(input())
print(n//2)
ans=[2 for i in range(n//2)]
if n%2: ans[-1]=3
print(*ans)

処理時間: Python3 171ms, PyPy3 187ms
nが偶数なら全て2で、nが奇数なら最後だけ3にする。

B. Parallelogram is Back

ざっくりと大意

・3点の座標と平行四辺形を構成するような点の座標を全て出力する。

Python3

ax,ay=[int(i) for i in input().split()]
bx,by=[int(i) for i in input().split()]
cx,cy=[int(i) for i in input().split()]
a=bx-ax
b=by-ay
c=cx-ax
d=cy-ay
if a*d-b*c==0:
    print(0)
else:
    print(3)
    print(ax+bx-cx,ay+by-cy)
    print(ax+cx-bx,ay+cy-by)
    print(cx+bx-ax,cy+by-ay)

なんか数学上で?ベクトルの和がAB+BD=AC+CDが成り立つらしい。ちょっとよくわからん。。

C. Voting

ざっくりと大意

・n人の従業員の投票の意思がそれぞれDとRで表されている。
・サンプル1は1番目のDの人が5番目のRの人を消して、2番目のDの人が3番目のRの人を消して、3番目の順番が飛んで4番目のRの人が2番目のDの人を消す。5番目の順番が飛んで1番目のDの人が4番目のRを消す。残ったのが1番目のDなので解がDとなる。

Python3(heapq)

import heapq
n=int(input())
s=input()
r,d=[],[]
for a,i in enumerate(s):
    if i=='R':
        heapq.heappush(r,a)
    else:
        heapq.heappush(d,a)
while len(r) and len(d):
    R=heapq.heappop(r)
    D=heapq.heappop(d)
    if R<D:
        heapq.heappush(r,R+n)
    else:
        heapq.heappush(d,D+n)
print(['R','D'][len(d)>0])

Python3(deque)

from collections import deque
n=int(input())
s=input()
r,d=deque(),deque()
for a,i in enumerate(s):
    if i=='R':
        r.appendleft(a)
    else:
        d.appendleft(a)
while len(r) and len(d):
    R=r.pop()
    D=d.pop()
    if R<D:
        r.appendleft(R+n)
    else:
        d.appendleft(D+n)
print(['R','D'][len(d)>0])

処理時間: Python3 498ms, PyPy3 467ms (heapq)
処理時間: Python3 249ms, PyPy3 171ms (deque) heapqを使って投票の内容をほぼシミュレートするような感じにした。Noteが若干わざと惑わすような例になっていて、反対側を消すのは順番が最も近い人を消すのが最適な行動となる。D,Rのいずれかが連続している中では複数の選び方をしても同じ結果となるはずだが最適な行動はあくまでも順番が最も近い人。nが最大で20万だが1周する毎に半分になっていくのでシミュしてもそれほどは重い処理ではないはず。
deque使うパターンを後から試したらコッチのほうが早かった。dequeは双方向で遅そうな気がして使わなかったけど、使ってみたら逆の結果になった。。