ABC380振り返り

前回の振り返り

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

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

入緑しました🎉

A

カウンター使ったけど
わざわざそんなことしなくてもいいね…

ソースコード

main.py

from collections import Counter
import sys
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())
def err(*args): print(*args, file=sys.stderr)

def main():
    S = rS()
    c = Counter(S)

    ans = c.get("1",0)==1 and c.get("2",0)==2 and c.get("3",0)==3
    print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

B

最初と最後の文字列を省いて|で分割
各要素の長さを出力

ソースコード

main.py

import sys
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())
def err(*args): print(*args, file=sys.stderr)

def main():
    S = rS()[1:-1].split("|")
    ans = [len(s) for s in S]
    print(*ans)
    
if __name__ == '__main__':
    main()

C

0の連結と1の連結をリストに分割する

順番にマージするが1がK-1入ったときに
入れる順番を交換する

あとはなくなるまで入れ続ける

ソースコード

main.py

import sys
from collections import deque
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())
def err(*args): print(*args, file=sys.stderr)

def main():
    N, K = rLI()
    S = rS()
    k0 = deque([s for s in S.split("1") if s != ""])
    k1 = deque([s for s in S.split("0") if s != ""])
    d = {"0":k0,"1":k1}
    cur = S[0]
    T = []
    for s in S:
        if cur != s:
            T.append(cur)
            cur = s
    T.append(cur)
    cnt={"0":0,"1":0}
    ans = []

    for t in T:
        ans.append(d[t].popleft())
        cnt[t]+=1
        # err(cnt["1"],ans)
        if cnt["1"]==K-1:
            ans.append(d["1"].popleft())
            # err(ans)
            ans.append(d["0"].popleft())
            # err(ans)
            while any(len(d[k])>0 for k in "01"):
                if len(d["0"]) > 0:
                    ans.append(d["0"].popleft())
                # err(ans)
                if len(d["1"]) > 0:
                    ans.append(d["1"].popleft())
                # err(ans)
            break
        
    print("".join(ans))
    
if __name__ == '__main__':
    main()

D

初期文字列の長さをNとして
KをNで割った商pとあまりqを求める

大文字・小文字が反転する場合を1
反転しない場合を0としたとき
01101001100101110...
p番目がわかればいい

色々検索して出てきたらThue-Morse列とかいう概念を使えばいいみたい

ソースコード

main.py

import sys
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())
def err(*args): print(*args, file=sys.stderr)

def main():
    S = rS()
    Q = rI()
    K = rLI1()
    N = len(S)
    d = [S,S.swapcase()]
    
    # err(d)
    ans = []
    for k in K:
        p,q = divmod(k,N)
        c = bin(p).count('1') % 2
        ans.append(d[c][q])
    
    print(*ans)
    
if __name__ == '__main__':
    main()

E

UnionFindを使う発想まではできた
残り30分では間に合わなかったorz

F

ゲーム理論ですか…

G

期待値ですか…

まとめ

E問題のUnionFindを使う発想まで出たのは勉強の成果だと思いたい。
あとは何問か解いて自力をつけたい。

お詫び

次回は11/22(金曜日)開催予定らしいですが
予定が重なってしまって参加できなさそうですorz

奇跡的に入緑したので来週は色変記事書きます