EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC226をpythonで解いてみた

競技プログラミング Atcoder

目的

  • Atcoderで上を目指すべく頑張っている中でABC226を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

X = input().split(".")

if int(X[1][0]) <= 4:
    print(X[0])
else:
    print(int(X[0])+1)

結果

B問題

atcoder.jp

考察

  • 与えられる中で同じ数列がある場合があるので、それを除外してcntする
    • 今回はsetに対して、tuple型にした数列を入れていき、重複を排除した
    • setの要素としてはimmutableである必要があるためtupleを利用(listだとダメ)

docs.python.org

実装

N = int(input())
ans = set([])

for _ in range(N):
    length, *line = map(int, input().split())
    ans.add(tuple(line))

print(len(ans))

結果

コンテスト中は、謎にlength別にsetを用意して重複排除してた

C問題

1WA出してしまったが、なんとか解くことができた

atcoder.jp

考察

  • 技がN個あり、それらを覚えるためには、事前に覚える必要な技がある

    • i番目の技を覚えるのに必要な技は、i=1, 2, ... , i-1 であることが保証されている
    • そのため、後ろから探索していけば良さそうな気がする

  • 技Nの習得な、技をDFSでたどっていき、習得までに必要な時間をcountしていく

    • 既に覚えた技を2重で習得し、2重で時間をcountしないために、習得した技であるかの状態を保持する

実装

N = int(input())
master = [False]*N
A, T = [], []
ans = 0

for _ in range(N):
    t, k, *a = map(int, input().split())
    T.append(t)
    if k == 0:
        A.append([])
    else:
        A.append(list(a))

ans = 0
stack = [N-1]
while stack:
    cur = stack[-1]
    if not A[cur]:
        stack.pop()
        if master[cur]:
            continue
        master[cur] = True
        ans += T[cur]
    else:
        nxt = A[cur].pop()-1
        if master[nxt]:
            continue
        stack.append(nxt)

print(ans)

結果

コンテスト中は、変数取得が余りよろしくない感じだったw

D問題

C問題に時間使ってしまって解けなかったが、時間あっても解けなかったと思う

atcoder.jp

考察

  • 全ての各点の間を移動できるような、ベクトル(a,b)を数え上げる

    • ベクトルの種類を最小にする必要がある
    • (2,4) みたいな操作は (1,2) を二回実行でも実現できる
      • つまり、(2, 4) は (1, 2)に包含される

  • 傾きが同じ成分のベクトルを1つにまとめることを考える

    • 割り算を使うと誤差が発生する
    • (a,b) の最大公約数(gcd(a,b))で割ることのがいいらしい
      • (2, 4) -> (1, 2) になる

atcoder.jp

実装

from math import gcd

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
ans = set([])

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        dx, dy = P[i][0]-P[j][0], P[i][1]-P[j][1]
        g = gcd(dx, dy)
        ans.add((dx//g, dy//g))

print(len(ans))

結果

gcd使って、傾きの同じベクトルをまとめられることに気づけば、実装は容易

まとめ

  • 絶賛停滞中w

f:id:kazu_0716:20211113185025p:plain
ABC226 結果

  • 解いていた思うのは、下記なので今後修正していきたい

    • B, C解くのでも結構時間がかかっている

      • 問題を読解し、要件(=何をすべきか)を見極めるまでが、結構遅い気がする
      • 立てた方針を実装するのに時間がかかっている
        • どう実装するのか、考えている場合より、作ったものが思った通りの結果が出なくてdebugしている時間が長い気がする

    • 緑diff以下の問題を埋めていて

      • 確かに、解説見ずに解けることも増えてきたが、1時間以上かかる場合も多い
        • 原因はB, Cのところと同じ場合が多い

  • 沼にハマらないようにコードを書くのと、ハマっても抜けられるように鍛錬していくぞ！