AtCoder Grand Contest 031

ついに水色になれた。精進します。 f:id:mitsuo_0114:20190317191001p:plain

atcoder.jp

"文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。" ここを若干勘違いして10分ほどロス。

それぞれの文字から1個以下ずつ選び、最後にすべてゼロの分を抜けばよい。

from collections import Counter
def solve(N, S):
    d = 10**9 + 7
    c = Counter(S)
    ans = 1
    for ch, count in c.items():
        ans *= (count + 1)
    ans %= d
    return ans - 1

assert(solve(1, "a") == 1)
assert(solve(2, "ab") == 3)
assert(solve(3, "abc") == 7)
assert(solve(3, "baa") == 5)
assert(solve(6, "abcab") == 17)

if __name__ == "__main__":
    N = int(input())
    S = input()
    print(solve(N, S))

atcoder.jp 700点問題を取れたのは初。600点もなかった気がする。

最初はそんな簡単なわけがないと思いつつ、各色ごとの中から2つ選ぶだけでよいと考えた。 これはある色だけを見たとき、その中から二つ選び間を塗るという行為は、任意の区分を塗ることに等しくなると思っていたから。 が、実際にはこれは異なる。区間が3つに分割されるとき、左右の区間を塗ることは二つを選ぶだけでは満たすことができない。

色の数、石の数共に20000で、計算量N2の解法は取れない。計算量Nの解法を突き詰めて考える。

ではDPっぽく考えてみる。ある地点まででKパターンできたとする。 ここでさらに一つ石を追加したときを考える。

同じ色の石がその地点までに一つもなかったらパターンは一つも増えない。 もし、同じ色の石がその地点までに一つ以上あった場合は増えそうだとわかる。

ここで、追加したことによって新しくできる「既存の一番右にある同じ色の石」と「新しく追加した石」の区間を考えると この間を塗る、塗らないのに2パターンに分けることができる。

この2パターンに分けたとき、全体としては「既存の一番右にある同じ色の石」が左側に構成する区間の通り数の分だけ増えることがわかり、 この地点はKパターン+「既存の一番右にある同じ色の石、が左側に構成する通り数」となり、DPが成立する。 なお、コーナーケースとして同じ色が連続していたらそれは区間を作ったことにならないので、はじく。

また、新しく追加した石と、一番右以外にある同じ色の石が作る区間は考えなくてよい。 なぜならば、その区間はすでに一番右にある石が追加された段階で数え上げられていると考えてよいため。

結果として、一次元のDPだけれども、ある地点の解を構成する要素は石の並び方によって異なることになる、ちょっと変形したDPになる。 漸化式としては作れず、トップダウンは、、実装できない気がする。ともあれ、ボトムアップの実装にならざるを得ない。 DPの勉強をしてた時にこういうケースもあるんだろうなと考えていたがさっそく現実に。

def solve(N, Cs):
    dp = [-1 for _ in Cs]
    latest_c = {}
    ans = 1
    d = 10 ** 9 + 7
    for i, c in enumerate(Cs):
        if c not in latest_c:
            latest_c[c] = i
            dp[i] = ans
        else:
            previous_i = latest_c[c]
            if previous_i != i - 1:
                ans += dp[previous_i]
            latest_c[c] = i
            dp[i] = ans
    return ans % d


assert (solve(1, [1]) == 1)
assert (solve(2, [1, 1]) == 1)
assert (solve(3, [1, 1, 1]) == 1)
assert (solve(3, [1, 2, 1]) == 2)
assert (solve(3, [2, 1, 1]) == 1)
assert (solve(4, [2, 1, 2, 1]) == 3)
assert (solve(5, [1, 2, 1, 2, 2]) == 3)
assert (solve(5, [1, 2, 1, 1, 2]) == 3)
assert (solve(5, [1, 1, 1, 1, 2]) == 1)
assert (solve(5, [1, 2, 1, 2, 1]) == 5)
assert (solve(7, [1, 3, 1, 2, 3, 3, 2]) == 5)
assert (solve(6, [1, 3, 1, 2, 3, 2]) == 5)
assert (solve(3, [1, 3, 1]) == 2)
assert (solve(4, [1, 3, 1, 2]) == 2)
assert (solve(5, [1, 3, 1, 2, 1]) == 4)

assert (solve(20000, [1] * 20000) == 1)
assert (solve(20000, [1] * 10000 + [2] * 10000) == 1)
assert (solve(6, [1, 2] * 3) == 8)

if __name__ == "__main__":
    N = int(input())
    Cs = [int(input()) for _ in range(N)]
    print(solve(N, Cs))

AtCoder Beginner Contest 121

400点とれなかったー。回答なしで時間切れ後にできるのは悔しい。

atcoder.jp

これは200点問題だろう、、。解説も要らん。

def solve(N, M, ABs):
    ABs = sorted(ABs)
    ans = 0
    for a, b in ABs:
        if b < M:
            ans += a * b
            M -= b
        else:
            ans += M * a
            break
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for __ in range(N)]
    print(solve(N, M, ABs))

atcoder.jp

そしてこっちは2時間かかって爆死。

Aから始まってBの間にはそれぞれのbitで周期性があることはすぐわかるので、この間の1の数を数える。

周期性というのは、例えば、3から10まで書き出したとき、一番下のビットは2つごとに同じビット列が並び、 次のビットは4つごと、さらに次は8つごととなってること。

0000000011
0000000100
0000000101
0000000110
0000000111
0000001000
0000001001
0000001010

どん詰まりしたのは、「Aから始まって、周期の始まり」、「周期中」、「周期の終わりからBまで」の3つをバラバラに求めてカウントしようとしたから。

はまりにはまって、コンテスト終了後に、AからBまでの1の数は「0からBまでの1の数」から「0~A-1までの1の数」を引けばよいことに気が付く。 これは、別のメソッドの切り出して実装。 もっと大局的に考えなきゃならん。

明らかに遅いとわかりつつ、今回はslow_solveの実装が楽だったのでさくっと書いてテストで実行。 これがあるとほぼ完ぺきなテストができるので安心。

countのメソッドに関してはテストそのものを間違えてしまった。0を周期にカウントしなかったために、一つずれていた。 修正は苦労しなかったが気が付くのに時間がかかった、、assertの量が苦労を物語る。

def slow_solve(A, B):
    ans = A
    for i in range(A + 1, B + 1):
        ans = ans ^ i
    return ans


def count(k, cycle):
    k += 1
    tans = (k // cycle) * (cycle // 2)
    res = k % cycle
    if res >= cycle // 2:
        tans += res % (cycle // 2)
    return tans


assert (count(8, 8) == 4)
assert (count(7, 8) == 4)
assert (count(6, 8) == 3)
assert (count(5, 8) == 2)
assert (count(4, 8) == 1)
assert (count(3, 8) == 0)
assert (count(2, 8) == 0)
assert (count(1, 8) == 0)
assert (count(0, 8) == 0)

assert (count(8, 4) == 4)
assert (count(7, 4) == 4)
assert (count(6, 4) == 3)
assert (count(5, 4) == 2)
assert (count(4, 4) == 2)
assert (count(3, 4) == 2)
assert (count(2, 4) == 1)
assert (count(1, 4) == 0)
assert (count(0, 4) == 0)

assert (count(8, 2) == 4)
assert (count(4, 2) == 2)
assert (count(3, 2) == 2)
assert (count(2, 2) == 1)
assert (count(1, 2) == 1)
assert (count(0, 2) == 0)


def solve(A, B):
    cycle = 2
    ans = ""
    for _ in range(40):
        acount = count(A - 1, cycle)
        bcount = count(B, cycle)
        ans = str((bcount - acount) % 2) + ans
        cycle *= 2
    return int(ans, base=2)


assert (slow_solve(2, 4) == solve(2, 4))
assert (slow_solve(2, 5) == solve(2, 5))
assert (slow_solve(2, 6) == solve(2, 6))
assert (slow_solve(2, 7) == solve(2, 7))

assert (solve(1, 1) == 1)
assert (solve(2, 4) == 5)
assert (solve(123, 456) == 435)

if __name__ == "__main__":
    A, B = tuple(map(int, input().split(" ")))
    print(solve(A, B))

もっとしっかり考えましょう。そして400問題で精進しよう。 来週はGrandコンテストでレート下降は避けられないので水色はしばらくお預けかな、、、

AtCoder Beginner Contest 120

全ACできた。

atcoder.jp

初めは01と10の探索から始めたが、発見をした後、2個進める必要があるためforじゃ回しにくいと、 そもそもindexの扱いにして最初と最後のindexの操作を実装した、、が1文字目のindex走査がかなり複雑になり、 簡単なテストケースは通ったものの、一回WA。

300点でこのindex操作量はなかなかないなと思いつつ、テストケースを作ってるうちに気が付く。 これ、どのような01の順序でも、消えない順序がない。 つまり、0と1がどのような順番で存在しても、必ず消えるだけ消えることに気が付く。 ということで0か1のどちらか少ないほうの倍がそのまま答えになる。

def solve(S):
    return min(S.count("1"), S.count("0")) * 2

assert (solve("1") == 0)
assert (solve("0") == 0)
assert (solve("10") == 2)
assert (solve("101") == 2)
assert (solve("100") == 2)
assert (solve("01") == 2)
assert (solve("011") == 2)
assert (solve("0110") == 4)
assert (solve("1100") == 4)
assert (solve("111000") == 6)
assert (solve("101010") == 6)
assert (solve("000000") == 0)
assert (solve("010000") == 2)
assert (solve("011000") == 4)
assert (solve("011010") == 6)
assert (solve("011110") == 4)
assert (solve("000011110000") == 8)
assert (solve("101110") == 4)
assert (solve("100010") == 4)
assert (solve("010") == 2)
assert (solve("0" * 10000) == 0)
assert (solve("1" * 10000) == 0)
assert (solve("1" * 5000 + "0" * 1) == 2)
assert (solve("10" * 5000) == 10000)

if __name__ == "__main__":
    S = input()
    print(solve(S))

直前でWAした実装で苦労したのでテストが多い。。

atcoder.jp

まず、"崩壊"は考えにくいので逆順にして"建設"をしていく。

あるa, bをつなぐ橋を建設したとき、 a, b がすでにつながっているならば不便さは変わらず、 a, bがつながっていないならば不便さが変わる。

a, b がつながっているかどうかの判定はUnionFindの出番。

さらに不便さの計算は、K個、L個、P個の島々のセットがあった時、 「自分の島々の個数」*「自分の島々から到達できない島の個数」 であるため以下3つを足し、最後に2で割ればよい。

K * (N-K)
L * (N-L) 
P * (N-P)

素直に実装すると、N個の全島群から不便さをM回計算することになる。島群のため、橋が建設されるたびに計算量は減っていくが、 減る量は特に最初のころはあまり期待できないなのでまだ改善が必要。

そこで、不便さの変化量を考える。 橋を建設するとき、島aが所属する島々の数と島bが所属する島々の数だけに依存し、それ以外が変わることはない。

このため、島aが所属する島々と、島bが所属する島々の不便さをいったん取り除き、 マージした後にできた新しい島々の不便さを再計算してやることで、再度すべての計算をしなくて済む。

初期状態はすべての橋が崩壊しているとき(=一つも建設されていない時)で、この時、不便さはN * (N - 1) // 2。

import sys
sys.setrecursionlimit(100000)

class UnionFind:

    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

    def is_unite(self, i, j):
        return self.root(i) == self.root(j)


from collections import Counter


def solve(N, M, ABs):
    uf = UnionFind(N)
    counter = Counter([i + 1 for i in range(N)])
    ans = []
    tans = N * (N - 1)
    for a, b in ABs[::-1]:
        ans.append(str(tans // 2))

        if not uf.is_unite(a, b):
            ar = uf.root(a)
            br = uf.root(b)

            tans -= counter[ar] * (N - counter[ar])
            tans -= counter[br] * (N - counter[br])
            counter[br] += counter[ar]
            tans += counter[br] * (N - counter[br])

            uf.unite(a, b)
    return "\n".join(ans[::-1])


assert (solve(2, 1, [(1, 2)]) == "1")
assert (solve(4, 5, [(1, 2), (3, 4), (1, 3), (2, 3), (1, 4)]) == "0\n0\n4\n5\n6")
assert (solve(6, 5, [(2, 3), (1, 2), (5, 6), (3, 4), (4, 5)]) == "8\n9\n12\n14\n15")

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

AC取れたのはよいが、今回は時間かかりすぎた感が否めない。

あとpythonの再帰回数にやられて謎のRE状況から10分悩んだ+15分ペナルティは痛い。 UnionFindで1000回以上して再帰してREってのはすぐに思いつかなかったわ。。

AtCoder Beginner Contest 119

久しぶりに全AC。。よかった。

atcoder.jp

Nの数から全数え上げをする問題、とすぐに気が付いたが、ある竹がAに取られたとき、B、Cには使えないという表現をどう数え上げるのに苦労した。

すべての竹に対し、A,B,Cあるいはいずれにも使われないという4パターンを渡せばよいと気が付く。 48 = 216 < 10万と計算量も見積もったうえで実装。これはpythonではitertoolsのproductを使えばループが可能。

    for p in product("ABCD", repeat=N):

これを使うと、N=8の時、以下のような配列が手に入る。これを数え上げればよい。

AAAAAAAA
AAAAAAAB
AAAAAAAC
・
・
from itertools import product


def solve(N, A, B, C, Ls):
    ans = 10000
    for p in product("ABCD", repeat=N):
        if "A" not in p or "B" not in p or "C" not in p:
            continue
        As = sum(Ls[i] for i in range(N) if p[i] == "A")
        Bs = sum(Ls[i] for i in range(N) if p[i] == "B")
        Cs = sum(Ls[i] for i in range(N) if p[i] == "C")
        tans = abs(As - A) + abs(Bs - B) + abs(Cs - C) + \
               (p.count("A") - 1) * 10 + (p.count("B") - 1) * 10 + (p.count("C") - 1) * 10
        ans = min(ans, tans)
    return ans


assert (solve(3, 1, 1, 1, [1, 1, 1]) == 0)
assert (solve(3, 1, 1, 1, [2, 2, 2]) == 3)
assert (solve(3, 1, 1, 1, [2, 2, 4]) == 5)
assert (solve(3, 2, 1, 1, [2, 2, 4]) == 4)
assert (solve(3, 1, 1, 2, [2, 2, 4]) == 4)

atcoder.jp

ある地点から一番近い地点を探す。二分探索であることはすぐに気が付く。

2か所をたどるが、ある地点からたどって左右のそれぞれの神社、寺の合計4か所をたどることを考えればよく、 以下の4パターンのみである。ただし左右に分かれる場合には、戻ることになることに注意。

左神社、左寺
右神社、右寺
左神社、右寺
右神社、左寺
import bisect

def solve(A, B, Q, Ss, Ts, Xs):
    ans = []
    Ss.append(10 ** 21)
    Ss.insert(0, -10 ** 21)
    Ts.append(10 ** 21)
    Ts.insert(0, -10 ** 21)
    for x in Xs:
        s_right = bisect.bisect_right(Ss, x)
        s_left = max(s_right - 1, 0)
        t_right = bisect.bisect_right(Ts, x)
        t_left = max(t_right - 1, 0)

        s_right = Ss[s_right]
        s_left = Ss[s_left]
        t_right = Ts[t_right]
        t_left = Ts[t_left]

        d_s_right = abs(s_right - x)
        d_s_left = abs(s_left - x)
        d_t_right = abs(t_right - x)
        d_t_left = abs(t_left - x)

        tans = 10 ** 35
        if x <= s_right and x <= t_right:
            tans = min(tans, max(d_t_right, d_s_right))
        if s_left <= x and t_left <= x:
            tans = min(tans, max(d_s_left, d_t_left))
        tans = min(tans, min(d_s_right, d_t_left) * 2 + max(d_s_right, d_t_left))
        tans = min(tans, min(d_t_right, d_s_left) * 2 + max(d_t_right, d_s_left))
        ans.append(str(tans))
    return "\n".join(ans)


assert (solve(1, 1, 1, [2], [0], [10]) == "10")
assert (solve(1, 1, 1, [200], [0], [10]) == "210")
assert (solve(1, 1, 1, [200], [0], [220]) == "220")
assert (solve(2, 2, 1, [2, 100], [0, 4], [3]) == "3")
assert (solve(2, 2, 1, [2, 100], [0, 4], [124]) == "120")
assert (solve(2, 2, 1, [2, 100], [0, 4], [0]) == "2")
assert (solve(2, 2, 1, [2, 100], [0, 4], [5]) == "3")

if __name__ == "__main__":
    A, B, Q = tuple(map(int, input().split(" ")))
    Ss = [int(input()) for _ in range(A)]
    Ts = [int(input()) for _ in range(B)]
    Xs = [int(input()) for _ in range(Q)]
    print(solve(A, B, Q, Ss, Ts, Xs))

pythonのbisectで返されるindexは、探索対象の配列のレンジに収まらないことがある。

   bisect.bisect_right([0, 1], 2) => 2
   bisect.bisect_right([0, 1], -10) => 0

ここの境界条件にかなり時間を食ったが、一番最初と一番最後に絶対に使わないデータを入れておくことにより、 境界を気にせずにコードを書くことができる。

また、変数の名前の付け方が悪く扱いに苦労した。。左右ぐらいはきちんと変数名に入れよう。

AtCoder Beginner Contest 047 - D - 高橋君と見えざる手 / An Invisible Hand

分割統治の良い練習だった。

indexes = []


def dfs(Ds, s, e, v=None):
    if e - s == 1:
        if v == Ds[s]:
            indexes.append((s, e))
        return Ds[s]
    else:
        center = (s + e) // 2
        left = dfs(Ds, s, center, v=v)
        right = dfs(Ds, center, e, v=v)

        left_m = - (10 ** 9)
        li = -1
        su = 0
        for i in range(center-1, s-1, -1):
            su += Ds[i]
            if left_m != max(left_m, su):
                left_m = max(left_m, su)
                li = i

        right_m = -(10 ** 9)
        ri = -1
        su = 0
        for i in range(center, e):
            su += Ds[i]
            if right_m != max(right_m, su):
                right_m = max(right_m, su)
                ri = i

        if left_m + right_m == v:
            indexes.append((li, ri))

        m = max(left, right, left_m + right_m)
        return m


def solve(N, T, As):
    Ds = [As[i + 1] - As[i] for i in range(N - 1)]
    max_v = dfs(Ds, 0, N - 1)
    dfs(Ds, 0, N - 1, v=max_v)
    return len(indexes)


assert (dfs([-50, 150], 0, 2) == 150)
assert (dfs([-20, 10, -30, 10], 0, 4) == 10)
assert (dfs([3, -6, 1, 4, -6, 3, 2, -6, -1], 0, 9) == 5)
indexes = []
assert (solve(3, 2, [100, 50, 200]) == 1)
indexes = []
assert (solve(5, 8, [50, 30, 40, 10, 20]) == 2)
indexes = []
assert (solve(10, 100, [7, 10, 4, 5, 9, 3, 6, 8, 2, 1]) == 2)

indexes = []
if __name__ == "__main__":
    N, T = map(int, input().split(" "))
    As = list(map(int, input().split(" ")))
    print(solve(N, T, As))

アルゴリズムイントロダクションで紹介されていた株価の話と同じでまずは最大部分和の問題に帰着できる。

最大部分和は、分割統治として解くことができ、 左半分部分、右半分部分、左右にまたがる部分のいずれか1か所に最大部分和ができることになる。 半分はさらに再帰し、一つになるまで分割する。 左右にまたがる部分は中央から左側と右側に伸ばし、一見、N2ですべて数え上げなければならないように見えるが、 それぞれで独立して最大値を計算することができるので、計算量はNになる。

最大部分和を求めたらもう一度動かして、何か所に出てくるかを数え、 これら複数個所出てきたときの処理を考える。

この時、複数個所のうちstart / endが被ることはない。例えばstart - startが被るとき、endは同じ値になってしまい、 問題の制約に反する。同様に、end-endが被るとstartが同じ値になる。

片方のstartがendと被るとき、例えば最大部分和が20だとして 20 - 40 と 40 - 60 ができたとする。この時、20 ~ 60の差が必ず最大部分和の2倍になり、20が最大部分和だという話に矛盾が出る。

これらから、複数個所の独立性が出てくる。

あとは、それぞれ一か所ずつ1ずつ削ってやればよいので、この最大部分和をもつ個所の数と同値になる。 Tは要らない!

AtCoder Beginner Contest 045 D - すぬけ君の塗り絵 / Snuke's Coloring

これは割とすんなり解けたかな。

from collections import Counter


def solve(H, W, N, ABs):
    total = (H - 2) * (W - 2)
    points = {}
    for a, b in ABs:
        a -= 1
        b -= 1
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                if 0 < a + i < H - 1 and 0 < b + j < W - 1:
                    d = (a + i, b + j)
                    if d not in points:
                        points[d] = 0
                    points[d] += 1
    c = Counter([v for v in points.values()])
    ans = [total - len(points)] + [c[f] if f in c else 0 for f in range(1, 10)]
    return "\n".join([str(a) for a in ans])

if __name__ == "__main__":
    H, W, N = map(int, input().split(" "))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(H, W, N, ABs))

H, Wがかなり大きいので、盤面すべてを記録する or 全3x3の正方形の走査は除外。 Nは走査がいけそうなので、各点から計算ができるかを考える。

ある点が影響を及ぼすのは高々9個のみ、つまり3x3正方形の中で0とならないものは最大でも 9 * N <= 9 * 105でこれを数えていけばよい。

教訓

  • (若干邪道だが)109なものは初めから数えられると思わず、数えられるものから考える。
  • 境界条件はやはり注意が必要。プログラムを実行せずに頭の中でちゃんと考える癖をつける。

AtCoder Beginner Contest 043 D - アンバランス / Unbalanced

400点問題だからと言って実装が必ず大変ってわけでもない。

def solve(s):
    for i, j in zip(range(0, len(s) - 1), range(1, len(s))):
        if s[i] == s[j]:
            return "%d %d" % (i + 1, j + 1)

    for i, j in zip(range(0, len(s) - 2), range(2, len(s))):
        if s[i] == s[j]:
            return "%d %d" % (i + 1, j + 1)

    return "%d %d" % (-1, -1)

assert (solve("ee") == "1 2")
assert (solve("eeded") == "1 2")
assert (solve("abcdd") == "4 5")
assert (solve("needed") == "2 3")
assert (solve("atcoder") == "-1 -1")
assert (solve("abaca") == "1 3")
assert (solve("cbaca") == "3 5")
assert (solve("abc" * 5000) == "-1 -1")

if __name__ == "__main__":
    print(solve(input()))

総当たりすればいけるのはすぐわかったのでまぁそれはよくて、 初めはしゃくとり法を考え付いたが、理解が浅くて使い方がままならず。

教訓

  • 分解してみると小さい問題だけで完結することがある。
  • 文字列のテストはやはり最初と最後まできちんと見れてるか。Indexの操作がたまに危うい。
  • 2文字の範囲、3文字の範囲のpythonのzip,rangeは頻出。考えずに打てるぐらいまで覚えたい。