ABC358振り返り

ABC358開催日だったので適当に参加した結果をまとめる

結果はABCDの4完
いままで3完しかしなかった壁を越えることができて嬉しい

A,Bについてはただやるだけなので省略するとしてC以降の感想を書いていく

C

bit全探索すれば行ける気はしたがやり方がわからないので
色々検索して出てきたのをコピペしてアレンジ
今度からこれをテンプレにしたいね

ソースコード

main.py

import sys
from itertools import product
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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)

p = {"o":1,"x":0}

def prod_or(g):
    x = 0
    for f in g:
        x |= f
    return x
def main():
    N, M = rLI()
    S = [rS() for _ in range(N)]
    target = sum( 1 << i for i in range(M))
    g = [sum(p[k] << i for i, k in enumerate(s)) for s in S]
    ans = N
    for k in product((0, 1), repeat=N):
        chk_g = [g[i] for i, bit in enumerate(k) if bit]
        if prod_or(chk_g) == target:
            ans = min(ans,len(chk_g))
    print(ans)

if __name__ == '__main__':
    main()

D

尺取り法的なやつ使えば行けそうだと思い適当に実行
なんかうまく行った感じがしたので提出したらACでちゃった

今まで解けなかったD問題なのにこんなにあっさり解けていいの？

ソースコード

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,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, M = rLI()
    A = rLI()
    B = rLI()
    A.sort()
    B.sort()
    ans = 0
    j = 0
    for i,a in enumerate(A):
        if a >= B[j]:
            ans += a
            j += 1
            if j == M:
                print(ans)
                break
    else:
        print(-1)
if __name__ == '__main__':
    main()

E

色々考えた結果、DP使えばいけそうな気がしたけど
どうテーブルをいじればいいかよくわからなくて時間切れ

F

Eやる前にチラ見したけど
迷路の出力むずくない？

G

ここもEやる前にチラ見
値が最大のところにいって経路探索すれば行ける気はしたが
そもそもそこら辺のアルゴリズムまだ使いこなせないので撤退

まとめ

とりあえずAtCoder Daily Trainingとかで頑張った成果を出せた気がしてうれしい

これからは4完を安定させていきたい