ntk log ntk

競プロや非競技プロのやったことを書いています.

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(*は任意の英小文字)の定義がまず再帰っぽいなと思った.操作はS_iを好きな文字に変えること,答えは必ず存在することを確認し,方針を考え始めた.n = 2^kであり,'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()


  1. なんかpiddyさんがもっと簡単そうにやってた.https://twitter.com/87___ka/status/1284191965412646912?s=20