🪴 Quartz 4.0

Search

SearchSearch

ARC108

Dec 01, 2023, 8 min read

AtCoder Regular Contest 108 - AtCoder A,B,Dの3問でした。Cは再帰呼び出しで書いてPyPyだと21TLE、生Pythonだと16TLEという際どい感じで、残り数分で自前スタックを使った深さ優先探索に切り替えたのだけどバグらせてたくさんWAが出ちゃって、それを直すのは間に合わなかった

image

image A

  • 考えたこと
    • 値の範囲が10^12まであるが、約数を求めるのは平方根オーダーなので10
    • すべての約数xに対してx+P/x=Sが成り立つかチェックすれば良い python
def solve(S, P):
    i = 1
    while i * i <= P:
        if P % i == 0:
            s = i + P // i
            if S == s:
                return "Yes"
        i += 1
    return "No"

B

  • 考えたこと
    • ネストしないfoxなら3つの状態を持つオートマトンで受理できる
    • 途中でfが出てきたら状態をスタックにプッシュ
    • 受理されたらスタックをポップ
    • 非受理だったら上位の「受理途中」のものも全部非受理なので、スタックをクリア
      • これを単なるポップにしてて1WA python
def solve(N, S):
    i = 0
    state = [0]
    ret = N
    while i < N:
        # debug(i, S[i], state, msg=":i, state")
        if state[-1] == 0:
            if S[i] == "f":
                state.append(1)
        elif state[-1] == 1:
            if S[i] == "o":
                state[-1] = 2
            elif S[i] == "f":
                state.append(1)
            else:
                state = [0]
        elif state[-1] == 2:
            if S[i] == "x":
                state.pop()
                ret -= 3
            elif S[i] == "f":
                state.append(1)
            else:
                state = [0]
        i += 1
    return ret

C

  • 考えたこと
    • シンプルなグラフで考察
    • 適当な全域木を根からたどって、親からの辺のラベルを頂点ラベルにつければ良い(誤り)
      • image
      • 本当にそれで良いか？
      • よくない、辺ラベルに同じ物が来た場合に辺の両端が同じだから消えてしまう
      • そこで根と「親のラベルと親との辺ラベルが一致する点」に関して「子への辺ラベルに出現しない物」を点ラベルにする
      • 70AC 16TLE
  • 公式解説
    • 根のラベルを適当に決めてしまう
      • 「親のラベルと親への辺ラベルが一致する点」にはそのラベル以外の任意の数を書けばその辺は消えない
      • 一致しない場合には辺ラベルと等しい値を書けばその辺は消えない
    • 解説を読むと、Cは適当な木を根から塗っていけば良いってところまでは同じなんだが、僕は「親は子への辺ラベルに使われてない数値にする」ってやってるせいで子供の数のループが発生してて間に合わなくなってた。実際は適当に決めても子供の側で辺が消えないようにできる。なるほど。
    • しかしこれでも1TLEする。
    • PyPyではなく生Pythonで提出したらACした
      • つまりPyPyで関数呼び出しが遅いことが問題になるレベルの際どい状況だったということか
      • 僕の元々の方法でもオーダーは変わらないだろう(各頂点が接続先についてループするのは必須だから)と思ってたのだが定数倍の遅さで負けているようだ python
def solve(N, M, edges):
    vlabel = [None] * N

    def f(cur, parentEdge=None, parent=None):
        if parentEdge is None:
            vlabel[cur] = 1
        else:
            if parentEdge != parent:
                vlabel[cur] = parentEdge
            else:
                vlabel[cur] = (parentEdge % N) + 1
        for child in edges[cur]:
            if vlabel[child]:
                continue
            c = edges[cur][child]
            f(child, c, vlabel[cur])

    f(0, None, None)
    return vlabel

D

  • 考えたこと
    • Nが1000と小さいことに意味はあるのか？
    • DPを検討する
      • あんまりスッキリしない
    • 小さい方から考えてみる
      • AB→AABの時、初期のBは長さ1のまま、Aは2以上の任意の長さに伸ばせる
      • AB→ABBの時、逆にAは長さ1のまま
      • この2つは対称なので前者だけ考える
      • AA→AAAの時、Aの列しか作れないので1通り
      • AA→ABAの時
        • AB→AABかつBA→BAAなら、挿入されたBの長さは増えないので必ず1
          • この計算は後で考える
        • それ以外の場合、Bも任意の長さになれる
          • つまりN-3の長さの任意の列になる: 通り
    • N-3個の1/0の列で任意個が0、ただし0は連続しない、ってものの数え上げ
      • 1と10を組み合わせてN-2の長さの列を作る
        • N-2から0個、N-3から1個…を選んで10にする
      • 通り
  • 公式解説 
def solve(N, S):
    if N < 4:
        return 1
    MOD = 1_000_000_007
    S = [x[0] - ord("A") for x in S]
    AA, AB, BA, BB = 0, 1, 2, 3
    A, B = 0, 1
    c = Combination(N + 10, MOD)
    if S[AB] == A:
        # len(B) = 1
        if S[AA] == A:
            return 1
        if S[AB] == A and S[BA] == A:
            # inserted B = length 1
            M = N - 2
            ret = 0
            for i in range(M):
                if M - i < i:
                    break
                ret += c.comb(M - i, i)
                ret %= MOD
            return ret
        else:
            return pow(2, N - 3, MOD)
    else:
        if S[BB] == B:
            return 1
        if S[BA] == B and S[AB] == B:
            # inserted B = length 1
            M = N - 2
            ret = 0
            for i in range(M):
                if M - i < i:
                    break
                ret += c.comb(M - i, i)
                ret %= MOD
            return ret
        else:
            return pow(2, N - 3, MOD)

ARC108E

F

  • 考えたこと
    • 木を塗り分ける、最も長いパスの両端が同じ色なら他がどう塗られてても同じ
    • 異なっているなら？
      • 1個取り除いたグラフについて同じ議論ができる？
      • この方針では間に合いそうにないが…
      • 半分ずつ塗り分けられているケースが一番スコアが低い

Graph View

Backlinks