全国統一プログラミング王決定戦予選(日経コン)　参戦記

ABCD4完でした。予選突破はなりませんでしたが、本選トークショーの参加権(500位以内)は無事てにしました。以下提出コードとやったことです。

A問題 (Subscribers)

N, A, B = map(int, input().split())
print(min(A, B), max(0, A + B - N))

はい。ベン図使いましょう。

B問題 (Touitsu)

N = int(input())
A = input()
B = input()
C = input()
Change = 0
for i in range(N):
    if A[i] == B[i] == C[i]:
        continue
    elif A[i] == B[i] or B[i] == C[i] or C[i] == A[i]:
        Change += 1
    else:
        Change += 2
print(Change)

i番目とj番目を変える操作はそれぞれ独立です。なので順に頭から処理していけばよいです。i番目の文字の取り得る状態としては、(1)A, B, Cいずれも同じ, (2)A, B, Cの内２つが同じ, (3)全て違う、のいずれかです。(1)の場合は何もしなくてもよいです。(2)の場合、一つだけ違う文字を変更すればよいです。(3)の場合はどれか一文字選んで、他の二つの文字をそれに変更すればよいです。

C問題 (Different Strokes)

N = int(input())
Takahashi = [None] * N
Aoki = [None] * N
Used = [False] * N
for i in range(N):
    a, b = map(int, input().split())
    Takahashi[i] = (-a-b, -a, i)
    Aoki[i] = (-b-a, -b, i)
Takahashi.sort()
Aoki.sort()
TotalPoint = 0
 
usedDish = 0
tnum, anum = 0, 0
while usedDish < N:
    if usedDish % 2 == 0:
        while Used[Takahashi[tnum][2]]:
            tnum += 1
        TotalPoint -= Takahashi[tnum][1]
        Used[Takahashi[tnum][2]] = True
        usedDish += 1
    else:
        while Used[Aoki[anum][2]]:
            anum += 1
        TotalPoint += Aoki[anum][1] 
        Used[Aoki[anum][2]] = True
        usedDish += 1
print(TotalPoint)

実験するとAとBの和が大きい順に貪欲にとっていけばいいことがわかります。提出コードでは高橋君と青木さん別々の配列を用意して処理していますが、実際には手番の偶奇で判断すれば良いです。

D問題 (Restore the Tree)

import queue
N, M = map(int, input().split())
ParentNum = [None] * N
EdgeFrom = [[] for _ in range(N)]
EdgeTo = [[] for _ in range(N)]
for _ in range(N - 1 + M):
    A, B = map(int, input().split())
    EdgeFrom[B-1].append(A-1)
    EdgeTo[A-1].append(B-1)
 
for i in range(N):
    if not EdgeFrom[i]:
        ParentNum[i] = 0
        ParentNode = i
        break
 
Q = queue.Queue()
Q.put(ParentNode)
while not Q.empty():
    currentNode = Q.get()
    for node in EdgeTo[currentNode]:
        if len(EdgeFrom[node]) > 1:
            EdgeFrom[node].remove(currentNode)
        else:
            ParentNum[node] = currentNode + 1
            Q.put(node)
for item in ParentNum:
    print(item)

問題文中の「書き足された各辺u→vは、ある頂点からその子孫であるような頂に向かって伸びています。」という文が肝になります。この文により根に向かう辺は追加されないことが保障されるので、向かってくる辺がないノードが根であることがわかります。次に順番に辺が追加されたものか否かを判定していきます。根を初期ノードとして、キューに確定させた子ノードを入れていくことで上位から順に確定させていきます。キューの先頭をcurrentNodeとして、currentNodeから出る辺を順に判定してきます。辺の先のノードをnextNodeとすると、nextNodeに入る辺が一つしかない時はnextNodeがcurrentNodeの子ノードであることがわかるので、nextNodeをキューに入れます。もしnextNodeに入る辺が二つ以上あるときは、この辺が追加された辺になるので削除します。キューで上位ノードから確定させていることからcurrentNodeは未確定ノード群で最上位のノードになるので(キュー待ちのものも含む)、もしcurrentNode → nextNodeが最初からある辺であるとすると、その他の辺が親に向かう辺もしくは兄弟に向かう辺となってしまい条件に矛盾します。このように上位ノードから辺の判定をし、追加された辺を取り除いていくことで、各辺一回判定するだけで元の木を復元することが出来ます。

アールグレー特売所

ゲームやら競プロやらのメモ書き

全国統一プログラミング王決定戦予選(日経コン)　参戦記