Ang107kの日記

結果

ノーペナ5完で初の5完＆水パフォ達成できました。

全体を通して、特別な知識を要求されなかったこと、解法を比較的早く思いつくことができ、実装面でもスムーズに行えたのが勝因かなと思います。
年内で入緑できる可能性もあるので、この一週間引き続き精進して来週のABCも頑張ろうと思います。

各問題の解法、感想

A問題

これはそのまま実装するだけです。

strで受け取って、intに変換したものと積を取れば良いです。

以下コード

n = input()

print(n*int(n))

B問題
最初どのように実装すべきか悩みましたが、気合で長さが同じ組になるsetを作って対応しました。5角形であれば、辺となる線分or対角線となる線分の二通りの長さしか存在しません。

以下コード

s = input()

t = input()

l1 ={"AB","BA","BC","CB","CD","DC","DE","ED","EA","AE",}

l2 = {"AC","CA","AD","DA","BE","EB","BD","DB","CE","EC"}

if (s in l1 and t in l1) or (s in l2 and t in l2):

PY()

else:

PN()

C問題

重複アリの組み合わせを考えれば良いことに気づければ、後は実装を頑張るだけした。333番目まで必要な時のレピュニットの最大長が分からなかったため、適当に試して333を超えるラインを探しました。
以下コード

n = II()

l =

for i in range(1,15):

temp = int("1"*i)

l.append(temp)

temp = list(combinations_with_replacement(l,3))

temp1 = [sum(i) for i in temp]

temp1.sort()

print(temp1[n-1])

D問題
 木構造であることから、閉路はないため、頂点1から枝分かれした後、それらが接続することはありえません。よって、頂点1を削除したときに分離される木のそれぞれの合計頂点数を計算し、最も大きいものを除いたものの合計が答えとなります。(頂点1が葉になるには、次数を1にする必要があります。）
以下コード

n = II()

uv = [LMII() for _ in range(n-1)]

for u,v in uv:

dd[u].add(v)

dd[v].add(u)

temp = dd[1]

def bfs(x):

visited = set()

deq = deque()

deq.append(x)

visited.add(x)

while deq:

x = deq.popleft()

for i in dd[x]:

if i not in visited and i != 1:

visited.add(i)

deq.append(i)

return len(visited)

l =

for i in temp:

l.append(bfs(i))

l.sort()

print(sum(l[:len(l)-1])+1)

E問題
ポーションの所持数の最大値を小さくする必要がありますが、これは、ポーションが必要になるタイミングの直前の取得ポイントで拾うことで達成することができます。
そこで、各種のポーションが落ちている場所、使用する場所を保存しておきます。使用する場所の直前の落ちているところを、bisect_leftで取得すれば良いです。複数個同じポーションを所持する必要がある場面もあるため、各種のポーションが落ちている場所をSortedSetで所持し、拾う場所が確定する度に、O(logN)で削除することで対応しました。
また、bisect_leftの取得結果が0の場合、使用前にポーションを拾うことができないことを意味するため、-1を出力して終了させました。
最後に出力用にデータを整形しながら、最大所持数を計算すれば良いです。
以下コード

n = II()

tx = [LMII() for _ in range(n)]

dd = defaultdict(SortedSet)

dd_mons = defaultdict(list)

for i,j in enumerate(tx):

if j[0] == 1:

dd[j[1]].add(i)

elif j[0] == 2:

dd_mons[j[1]].append(i)

ans = [0] * n

for i,j in dd_mons.items():

for p in j:

temp = bisect_left(dd[i],p) - 1

# print(dd[i][temp])

if temp == -1:

print(-1)

exit()

else:

ans[dd[i][temp]] = 1

dd[i].remove(dd[i][temp])

p_max = 0

p = 0

ans1 = []

for i,j in zip(ans,tx):

if j[0] == 1:

# print(i,j)

ans1.append(i)

if i == 1:

p += 1

else:

p -= 1

# print(p)

p_max = max(p_max,p)

print(p_max)

print(*ans1)

結果

各問題の解法、感想