A: Three Times
数字NをN個つなげて得られる文字列を出力します。
コード
N = int(input())
ans = ""
for i in range(N):
ans += str(N)
print(ans)
B: Pentagon
スマートな解法が思い浮かばなかったので地道に全部辺を列挙しました。
短い辺の集合にどちらも存在するかどちらも存在しないかの時だけYesです。
公式の滅茶苦茶スマートな解法はこちら
コード
one = ["AB", "BC", "CD", "DE", "EA", "AE", "ED", "DC", "CB", "BA"]
S = input()
T = input()
if (S in one and T in one) or (S not in one and T not in one):
print("Yes")
else:
print("No")
C: Repunit Trio
入力例３から、あり得る最大の答えがわかります。112222222233(12桁)以上の数を考える必要はないので、13桁のレピュニットまで(1111111111111)を考えます。
レピュニット数をすべて列挙したリストを作り、そこからあり得る和を3重ループで求めてソートすれば問題なく答えが求められます。
コード
N = int(input())
# 13桁までのレピュニット数のリスト
rep = [int("1"*i) for i in range(1,14)]
ans = []
for i in range(len(rep)):
for j in range(len(rep)):
for k in range(len(rep)):
ans.append(rep[i]+rep[j]+rep[k])
ans = sorted(list(set(ans)))
print(ans[N-1])
D: Erace Leaves
頂点１を削除するためには、頂点１が葉である必要があります。従って、頂点１から出ている辺を１にまで減らします。
これは、頂点１を根とする木を一つを残して全て削除することで実現できます。
操作回数を最小にしたいので、残す木は最大のものにしたいです。
よって、頂点１を根とする木のうち最大のもの以外をすべて削除し、最後に頂点１を削除します。これは Union Findで頂点１から出ている辺以外を全て管理し、木の大きさを考えることで求められます。
（木は連結であるのでどの頂点も必ず1を根とする木の中に含めることができます。）
Union Findはアルゴ式に実装例が載っています。
コード
このUnion Findのコードはどこかから頂いたものです…(再発見できず)。
from typing import List
class UnionFind:
"""0-indexed"""
def __init__(self, n):
self.n = n
self.parent = [-1] * n
self.__group_count = n
def unite(self, x, y) -> bool:
"""xとyをマージ"""
x = self.root(x)
y = self.root(y)
if x == y:
return False
self.__group_count -= 1
if self.parent[x] > self.parent[y]:
x, y = y, x
self.parent[x] += self.parent[y]
self.parent[y] = x
return True
def is_same(self, x, y) -> bool:
"""xとyが同じ連結成分か判定"""
return self.root(x) == self.root(y)
def root(self, x) -> int:
"""xの根を取得"""
if self.parent[x] < 0:
return x
else:
self.parent[x] = self.root(self.parent[x])
return self.parent[x]
def size(self, x) -> int:
"""xが属する連結成分のサイズを取得"""
return -self.parent[self.root(x)]
def all_sizes(self) -> List[int]:
"""全連結成分のサイズのリストを取得 O(N)"""
sizes = []
for i in range(self.n):
size = self.parent[i]
if size < 0:
sizes.append(-size)
return sizes
def groups(self) -> List[List[int]]:
"""全連結成分の内容のリストを取得 O(N・α(N))"""
groups = dict()
for i in range(self.n):
p = self.root(i)
if not groups.get(p):
groups[p] = []
groups[p].append(i)
return list(groups.values())
@property
def group_count(self) -> int:
"""連結成分の数を取得 O(1)"""
return self.__group_count
def main():
N = int(input())
uf = UnionFind(N)
for _ in range(N-1):
u, v = map(int, input().split())
# １から出ている辺は無視する
if u==1 or v==1:
continue
uf.unite(u-1,v-1)
# 最大の木を除いたすべての頂点を削除する
print(sum(uf.all_sizes())-max(uf.all_sizes()))
main()
E: Takahashi Quest
kyopuro_friendsさんのユーザー解説にもあるように、後ろから「必要なポーションの種類と数」を辞書で管理します。
まずは、必要ポーションの数と種類を表す辞書portionと、その時に所持しているポーションの数を表す変数num、ポーションを拾ったかを記録するリストactionsを用意します。
ポーションを見つけた時(t=1)、まずはそのポーションが必要かどうか確認します。これはportion[x]が1以上であるかどうかで判断できます。
もしポーションが必要であれば、そのポーションを拾って使います。これにより、この先必要なポーションが1つ減り、所持しているポーションも一つ減ります。
もしポーションが必要でないなら、拾わなくていいです。
これは下記のコードで実装できます。
if t==1:
if portion[x] > 0:
portion[x] -= 1
num -= 1
actions.append(1)
else:
actions.append(0)
モンスターと出会った時(t=2)、対応したポーションが必要なのでそれを必要ポーションに加えます。さらに所持ポーションが増えるので、最大ポーション所持数も更新しておきます。
if t==2:
portion[x] += 1
num += 1
k = max(k, num)
最後に、必要ポーションが全て０になっていることを確認してモンスター撃退完了の確認をします。
必要なポーションが残っているのに拾えていない場合は対応するモンスターが撃退できないので-1を出力します。
if sum(portion.values()) == 0:
print(k)
print(*reversed(actions))
else:
print(-1)
まとめたコードがこちら
コード
from collections import defaultdict
N = int(input())
TX = reversed([list(map(int, input().split())) for _ in range(N)])
portion = defaultdict(int)
k = 0
num = 0
actions = []
for t, x in TX:
if t == 1:
if portion[x] > 0:
portion[x] -= 1
num -= 1
actions.append(1)
else:
actions.append(0)
else:
portion[x] += 1
num += 1
k = max(k, num)
if sum(portion.values()) == 0:
print(k)
print(*reversed(actions))
else:
print(-1)