Codeforces Round #656 (Div. 3)
ABCD4完.Eはコンテスト後にnok0さんに教えてもらって通した!
以下問題ごとの感想とACコード.
A問題
サンプルが親切なので,じっと見ると大きい方から2個が一致していればよさそうなことに気づく. 解は,小さい数を2個と大きい数が1個の組である.小さい数が2個ないと,その小さい数が作れないので. コンテスト中は"any order"に気づかなくて,順番考えて解を出力してた.Bより難しい….1
コード
def main():
T = int(input())
for _ in range(T):
A = [int(i) for i in input().split()]
B = sorted(A)
if B[1] == B[2]:
print("YES")
print(B[0], B[0], B[2])
else:
print("NO")
if __name__ == '__main__':
main()
B問題
こどふぉあるある,inputとoutputとサンプルだけ見て問題を読んでいない.
でも"It is guaranteed that the answer exists and is unique."に安心してコーナーとかなさそう!wと思って提出した.
set()を用意して,初めに現れたときだけリストに追加.for文回し終わったらリストを出力.
コード
def main():
T = int(input())
for _ in range(T):
_ = int(input())
A = [int(i) for i in input().split()]
B = set()
ans = []
for a in A:
if a in B:
continue
ans.append(a)
B.add(a)
print(*ans)
if __name__ == '__main__':
main()
C問題
こどふぉあるある,問題文を4,5回読んだ(他の人にとってはあるあるではないですか?僕に限られるかもしれません). 与えられた数列の先頭から,要素をいくつか取り除いて,残った数列から単調増加数列を作れるようにしたい. 最小で取り除かなければいけない要素はいくつか?という問題.
後ろから,単調減少している長さか,単調増加してから単調減少している数列の大きさを求める. その数列が,"残った数列"であり,これなら単調増加数列を作れる. (与えられた数列の大きさN) - ("残った数列"の大きさ)が,求める取り除く要素数になるのでクエリごとにこれを出力. なんかAtCoderのある問題をコンテスト中に思い出した.
コード
def main():
T = int(input())
for _ in range(T):
N = int(input())
A = [int(i) for i in input().split()][::-1]
flag = False
pre = A[0]
cnt = 1
for a in A[1:]:
if not flag:
if a >= pre:
pass
else:
flag = True
else:
if a <= pre:
pass
else:
break
pre = a
cnt += 1
print(N - cnt)
if __name__ == '__main__':
main()
D問題
これ解けたの嬉しい. 再帰で一番少ない数を計算する.
思考過程としては,問題文を読んでいて,*-good(*は任意の英小文字)の定義がまず再帰っぽいなと思った.操作はを好きな文字に変えること,答えは必ず存在することを確認し,方針を考え始めた.であり,'a'から(k+1)種類文字を使うんだな~と気づき(k = 3ならa, b, c, dまで使う),とりあえずascii_lowercaseをimportしながら続きを考える.k = 3のときのサンプルを書きだして,どこが'a'になるかから決めるのか,どこが'd'になるかから決めるのかをちょっと悩む.もし'aaaa'を前半にするなら,後半で'dcbb'みたいなのを作らなきゃいけなくて~,辺りまで考えて,「これ再帰でやればいいんじゃない?」と気づく.前半を'a'で埋める場合に変更する要素数を数えて,後半については再帰の次の処理で考える.同じように,後半を'a'で埋める場合に変更する要素数を数えて,前半については再帰の次の処理で考える.深さを持っておけば,その時点で何の文字にしたいか,も割と簡単に持てるし,これだ!!と実装する.終了条件を最初N == 0にしてサンプルが合わなくて,N == 1のときに分岐して返すようにしたら上手くいった.
コード
def main():
from string import ascii_lowercase
dic = {i: a for i, a in enumerate(ascii_lowercase)}
T = int(input())
def dfs(N, S, i=0):
if N == 1:
return 1 if dic[i] != S[0] else 0
ret1, ret2 = 0, 0
ret1 = sum(dic[i] != s for s in S[N//2:])
ret2 = sum(dic[i] != s for s in S[:N//2])
ret = min(dfs(N//2, S[:N//2], i+1)+ret1,
dfs(N//2, S[N//2:], i+1)+ret2)
return ret
for _ in range(T):
N = int(input())
S = [s for s in input()]
print(dfs(N, S))
if __name__ == '__main__':
main()
E問題
トポソは思いつけたのに~~~!解けなかった悔しい!
無向辺は大胆に消してしまおう!
コード
def main():
from collections import deque
T = int(input())
for _ in range(T):
N, M = (int(i) for i in input().split())
edge = [[] for _ in range(N)]
edges = []
direct = [0]*M
deg = [0]*N
for m in range(M):
t, a, b = (int(i) for i in input().split())
a -= 1
b -= 1
if t == 1:
edge[a].append(b)
deg[b] += 1 # in-degree
direct[m] = t
edges.append((a, b))
que = deque()
order = 0
ans = []
for i in range(N):
if deg[i] == 0:
que.append(i) # root
ans.append((i, order))
order += 1
while que:
u = que.popleft()
for v in edge[u]:
deg[v] -= 1
if deg[v] == 0:
que.append(v)
ans.append((v, order))
order += 1
ans.sort(key=lambda p: p[1])
# トポソできなければ閉路がある
# トポソできれば,トポソでつけた頂点の順番にそって無向辺に向き付けすればOK
if len(ans) == N:
print("YES")
dic = {a: s for a, s in ans}
for m, (x, y) in enumerate(edges):
if direct[m] == 1:
print(x+1, y+1)
else:
if dic[x] < dic[y]:
print(x+1, y+1)
else:
print(y+1, x+1)
else:
print("NO")
if __name__ == '__main__':
main()
-
なんかpiddyさんがもっと簡単そうにやってた.https://twitter.com/87___ka/status/1284191965412646912?s=20↩