arc108

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


A
考えたこと
値の範囲が10^12まであるが、約数を求めるのは平方根オーダーなので10^6
すべての約数xに対してx+P/x=Sが成り立つかチェックすれば良い
pythondef 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
pythondef 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
考えたこと
シンプルなグラフで考察
適当な全域木を根からたどって、親からの辺のラベルを頂点ラベルにつければ良い(誤り)
本当にそれで良いか？
よくない、辺ラベルに同じ物が来た場合に辺の両端が同じだから消えてしまう
そこで根と「親のラベルと親との辺ラベルが一致する点」に関して「子への辺ラベルに出現しない物」を点ラベルにする
70AC 16TLE
公式解説
根のラベルを適当に決めてしまう
「親のラベルと親への辺ラベルが一致する点」にはそのラベル以外の任意の数を書けばその辺は消えない
一致しない場合には辺ラベルと等しい値を書けばその辺は消えない
解説を読むと、Cは適当な木を根から塗っていけば良いってところまでは同じなんだが、僕は「親は子への辺ラベルに使われてない数値にする」ってやってるせいで子供の数のループが発生してて間に合わなくなってた。実際は適当に決めても子供の側で辺が消えないようにできる。なるほど。
しかしこれでも1TLEする。
PyPyではなく生Pythonで提出したらACした
つまりPyPyで関数呼び出しが遅いことが問題になるレベルの際どい状況だったということか
僕の元々の方法でもオーダーは変わらないだろう(各頂点が接続先についてループするのは必須だから)と思ってたのだが定数倍の遅さで負けているようだ
pythondef 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の長さの任意の列になる: 2^{N-3}通り
N-3個の1/0の列で任意個が0、ただし0は連続しない、ってものの数え上げ
1と10を組み合わせてN-2の長さの列を作る
N-2から0個、N-3から1個…を選んで10にする
\sum_i \binom{N-2-i}{i}通り
公式解説
この二項係数の和はフィボナッチになる
二項係数の和とフィボナッチ
1個進むか2個進むかを組み合わせてN-2にするから
pythondef 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個取り除いたグラフについて同じ議論ができる？
この方針では間に合いそうにないが…
半分ずつ塗り分けられているケースが一番スコアが低い
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:27:51 PM[Edit]
Related Pages
