残念、Unratedになってしまった。運営の方々お疲れ様です。
例のごとく、assertの量がドはまり感を醸し出す。 まず、”AB"が含まれている場合はよい。で、単に末尾のAと先頭のBだけでなく、両方とも満たす場合は別に考える必要がある。
ここからABの数を数えるときに両側にあるものを1列に並べることで、並べた個数をCとしたとき、C-1個の"AB"を作ることができる。
ここまではよかった。では、これと残りの末尾のA、先頭のBをどう組み合わせるかで微妙な勘違いをしてはまった。
回答的には単にCを並べているかどうか、a,bがあるかだけで、判断すればよい。
最後にaのみ、bのみを少ないほうに合わせた数でABができるのでそれを足す。
def solve(N, Ss): a = 0 b = 0 both = 0 ans = 0 for s in Ss: ans += s.count("AB") if s[-1] == "A" and s[0] == "B": both += 1 else: if s[-1] == "A": a += 1 if s[0] == "B": b += 1 if both > 0: ans += both - 1 if both > 0 and a > 0: ans += 1 a -= 1 if both > 0 and b > 0: ans += 1 b -= 1 ans += min(a, b) return ans assert (solve(1, ["AB"]) == 1) assert (solve(2, ["AB", "ABABAB"]) == 4) assert (solve(2, ["AB", "ABABAB"]) == 4) assert (solve(2, ["CCB", "CCB"]) == 0) assert (solve(1, ["CABC"]) == 1) assert (solve(2, ["CCA", "BCC"]) == 1) assert (solve(4, ["CCA", "BCC", "CCA", "BCC"]) == 2) assert (solve(3, ["CCA", "BCC", "CCA"]) == 1) assert (solve(200, ["CCA"] * 100 + ["BCC"] * 100) == 100) assert (solve(200, ["CCA"] * 110 + ["BCC"] * 90) == 90) assert (solve(200, ["CCA"] * 90 + ["BCC"] * 110) == 90) assert (solve(200, ["ABA"] * 90 + ["BCC"] * 110) == 90 + 90) assert (solve(200, ["ABA"] * 90 + ["BCC"] * 110) == 90 + 90) assert (solve(200, ["CCA"] * 110 + ["BAB"] * 90) == 90 + 90) assert (solve(200, ["CCA"] * 90 + ["BAB"] * 110) == 90 + 110) assert (solve(2, ["ABA", "BAB"]) == 3) assert (solve(200, ["ABA", "BAB"] * 200) == 3 * 200) assert (solve(2, ["ABB", "AAB"]) == 2) assert (solve(200, ["ABB", "AAB"] * 100) == 200) assert (solve(2, ["ACA", "BCB"]) == 1) assert (solve(2, ["ACB", "BCA"]) == 0) assert (solve(2, ["BCB", "BCA"]) == 1) assert (solve(2, ["BCB", "ACA"]) == 1) assert (solve(4, ["BCA", "BCA", "CA", "BC"]) == 3) assert (solve(6, ["BCA", "BCA", "CA", "BC"] + ["CC", "CC"]) == 3) assert (solve(4 * 2, ["BCA", "BCA", "CA", "BC"] * 2) == 6) assert (solve(6, ["BCA", "CA", "BC"] * 2) == 4) assert (solve(2, ["A", "B"]) == 1) assert (solve(2, ["AA", "BB"]) == 1) assert (solve(2, ["AAB", "BB"]) == 1) assert (solve(2, ["AACB", "BB"]) == 0) assert (solve(3, ["AACB", "BB", "AA"]) == 1) assert (solve(300, ["BA", "BA", "BA"] * 100) == 299) assert (solve(300, ["BABA", "BABA", "BABA"] * 100) == 299 + 300) assert (solve(400, ["BABA", "BABA", "BABA", "AA"] * 100) == 299 + 300 + 1) assert (solve(4, ["AA", "BA", "BA", "BB"]) == 3) assert (solve(3, ["AB", "BB", "AA"]) == 2) assert (solve(3, ["AB", "BA", "AA"]) == 2) assert (solve(3, ["AB", "BA", "BA"]) == 2) assert (solve(4, ["AB", "BA", "BA", "AA"]) == 3) assert (solve(4, ["AB", "BA", "BA", "BB"]) == 3) assert (solve(3, ["AB", "BA", "BB"]) == 2) assert (solve(3, ["AB", "AA", "BB"]) == 2) assert (solve(2, ["AB", "BA"]) == 1) assert (solve(2, ["BA", "BA"]) == 1) assert (solve(3, ["AB", "BA", "BA"]) == 2) assert (solve(3, ["BA", "BA", "BA"]) == 2) assert (solve(3, ["BCA", "BCA", "BCA"]) == 2) assert (solve(3, ["BCC", "BCA", "BCA"]) == 2) assert (solve(3, ["CCA", "BCA", "BCA"]) == 2) print("OK") if __name__ == "__main__": N = int(input()) Ss = [input() for _ in range(N)] print(solve(N, Ss))
これも約数を求めてカウントすればよい、というところまではすぐに分かったがどうも実装がはまった。
まず、約数を求める範囲だが、
N = m * k + k
としたとき、例にもあるようにN=8のときm = 7になるため、mを動かしてしまうと調べる範囲がどうも1 - Nの範囲になり間に合わない。
そこで、逆にkを動かそうと考えてみると、
N = m * k + k
= (m + 1) * k
より、一つのkに対して、一つのmが定まることがわかる。
この式を満たすkを探すことを考えれば、考えられるすべてのkを求めるためにはO(√N)ですむ。
(N // k) - 1 = m
def solve(N): s = 1 e = int(pow(N, 0.5)) + 1 ds = [] for k in range(s, e): if N % k == 0: m = (N // k) - 1 if m and N // m == N % m: ds.append(m) return sum(ds) assert (solve(8) == 3 + 7) assert (solve(10) == 4 + 9) assert (solve(1000000000000) == 2499686339916) if __name__ == "__main__": N = int(input()) print(solve(N))
