ABC399振り返り

前回の振り返り

今日はABC399開催日だったので参加結果を振り返る

今週はのA,B,C完(0ペナ)

A

各種文字みるだけ

内包表記で横着した

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    S = rS()
    T = rS()
    print(sum(1 for s,t in zip(S,T) if s != t))
    # for _ in range():
    # for i in range(N):
    # for i,a in enumerate(A,start=1):
    # for i,a in enumerate(A):
    #     S = rS()
    #     X, Y = rLI()
    #     A, B = rLI()
    #     if True:
    #         print("Yes")
    #         print("No")
    # else:
    #     print("Yes")
    #     print("No")
    
    # ans = 
    # print(ans)
    # print(*ans)
    # print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

B

言われた通りに順位だすだけなのに
実装に10分かかった

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

import heapq

class Maxheapq:
    def __init__(self):
        self.q = []

    def push(self, v):
        heapq.heappush(self.q, v * -1)

    def pop(self):
        return heapq.heappop(self.q) * -1

    def get(self):
        return self.q[0] * -1

    def values(self):
        for _q in self.q:
            yield -_q

def main():
    N = rI()
    P = rLI()
    q = Maxheapq()
    for p in set(P):
        q.push(p)
    rank = [0]*N
    r = 1
    while len(q.q)>0:
        x = q.pop()
        X = [i for i,p in enumerate(P) if p == x]
        k = 0
        for i in X:
            rank[i] = r
            k+=1
        r += k
    for rnk in rank:
        print(rnk)
    
if __name__ == '__main__':
    main()

C

グラフで閉路ってどうやって判断するのか
わからずに別の問題に逃亡。

一旦冷静になってggったら
UnionFindぶつけるだけだったという話😅

食わず嫌いすぎ男過ぎた…

ソースコード

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * -~n
        self.rank = [1] * -~n
        self.count = n
    def root(self, x):
        while (p:=self.parent[x]) != -1:
            x = p
        return x
    def union(self, x, y):
        xr = self.root(x)
        yr = self.root(y)
        if xr == yr: return
        elif (rx:=self.rank[xr]) < (ry:=self.rank[yr]):
            self.parent[xr] = yr
            self.rank[yr] += rx
        else:
            self.parent[yr] = xr
            self.rank[xr] += ry
        self.count -= 1
    def same(self,x,y):
        # err(self.root(x), self.root(y))
        return self.root(x) == self.root(y)

def main():
    N, M = rLI()
    uf = UnionFind(N)
    ans = 0
    for i in range(M):
        u,v = rLI()
        if uf.same(u,v):
            ans += 1
        else:
            uf.union(u,v)
    print(ans)
    
if __name__ == '__main__':
    main()

D

テストケースの問題久々に見た

E

次の問題が面白そうだったので放置

F

面白そうだから時間使っちまった。

単純解法なら思いついたけどTLEしかしない予感だったので
頭を悩ます展開に…

でも結局わかんなくて時間切れ

G

解けてる人全くいない件

感想

C問題検索すれば一発でわかったのに
グラフでわかんない単語でたらすぐ逃げるクセが無駄な時間でした。
とりあえずggることだけは次からやりたい。