水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

ARC056に参加しました。

arc056.contest.atcoder.jp


いわゆる不正?が発生した。(A問題がWAなのに100点 *1 )

140点の169位。微妙。今回B問題の部分点は取れたけど、C、Dも部分点があったのでもっと早く通せていればという気持ち。



A問題

A: みんなでワイワイみかん - AtCoder Regular Contest 056 | AtCoder

とりあえず、int(k / l) まではまとめ買いするとして、その後に1個ずつ買ったほうが良いのか、もう1個まとめ買いをするのかを判断すればOK。


本番は1つ条件式を読み飛ばしていてサンプルだけWAするという不思議な事が起こった。(そして多分このような状況の時、サンプルのWAをとるためにsubmitしてしまうと、1WA扱いになって順位下がるよなこれと読んで、コンテスト後にACしました。)

整形後のコード。

Submission #781418 - AtCoder Regular Contest 056 | AtCoder

a, b, k, l = map(int, input().split())
t = k // l
print(min((t + 1) * b, t * b + (k % l) * a))

B問題(部分点)

B: 駐車場 - AtCoder Regular Contest 056 | AtCoder


ひたすら幅優先探索する。この時、すでに車が入っているところはすでに訪れた扱いにして遷移しないようチェックする。また、入り口を塞がれてしまうとそれ以降車は入らないので、処理を終了してもよい。


なおpythonでこの部分点を考えていた時のことであるが、アルゴリズムというより、言語仕様に苦しめられた。どのデータ構造体を使えば高速化できるのかわからず、非常に苦労。最終的にdefaultDictやdequeに救われ、余分なsetの計算を省いたらなんとかなった。



Submission #780337 - AtCoder Regular Contest 056 | AtCoder


from collections import deque, defaultdict
 
def solve():
    n, m, s = map(int, input().split())
 
    if m > 2000:
        return 0
 
    loads = defaultdict(list)
    for _ in range(m):
        a, b = map(int, input().split())
        loads.setdefault(a, []).append(b)
        loads.setdefault(b, []).append(a)
 
    parking = set()
    for i in range(1, n+1):
        if i == s:
            print(i)
            break
 
        que = deque()
        visited = set([s]) | parking
        que.append(s)
 
        while len(que) > 0:
            idx = que.pop()
            nextidxs = set(loads[idx]) - visited
            if i in nextidxs:
                print(i)
                parking.add(i)
                break
            visited |= nextidxs
            que += nextidxs
 
if __name__=="__main__":
    solve()

**********************************

追記

余談であるが、pypy3だと上記コードで40点取れるが、python3だとTLEしてしまい、点数が取れない。
ある意味、悩ましい問題である。

**********************************


一応、正しい方針としてはダイクストラかUnion-Findみたいです、全く思いつきませんでした…。


C問題の部分点も結構総当り系なのかなあと思っていたので、手を出せなかったのは残念です。(Dは問題文ちら見したけどよくわからなかった…)


最近解説を読んで解き直す、ということをする時間があまりないので伸びていませんが、ARCは継続的に出て考察力、実装力の維持に役立てたいですねえ…。

*1: サンプルのみWAだとこういうことがある