2019-03-09

AtCoder Beginner Contest 121

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

これは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つごととなってること。

どん詰まりしたのは、「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コンテストでレート下降は避けられないので水色はしばらくお預けかな、、、

2019-03-03

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ってのはすぐに思いつかなかったわ。。

2019-02-24

AtCoder Beginner Contest 119

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

atcoder.jp

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

すべての竹に対し、A,B,Cあるいはいずれにも使われないという4パターンを渡せばよいと気が付く。 4⁸ = 2¹⁶ < 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

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

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

2019-01-23

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か所に最大部分和ができることになる。半分はさらに再帰し、一つになるまで分割する。左右にまたがる部分は中央から左側と右側に伸ばし、一見、N²ですべて数え上げなければならないように見えるが、それぞれで独立して最大値を計算することができるので、計算量はNになる。

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

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

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

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

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

2019-01-22

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 * 10⁵でこれを数えていけばよい。

教訓

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

2019-01-22

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は頻出。考えずに打てるぐらいまで覚えたい。

2019-01-15

読中 - 低レイヤを知りたい人のためのCコンパイラ作成入門

compilerbook.booth.pm

Linuxのブートプロセスの理解をしているのは世界にどれだけいるのだろう。

さて、Cでも勉強したいのだけれど、作りたいものが見つからない状況なのでコンパイラを作る。

環境設定

WindowsのCLionを使いたい。CLionとしてはMinGWやCygwinなどあるが、筆者の意図に合わせてこれをインストール。 Install Windows Subsystem for Linux (WSL) on on Windows 10 | Microsoft Docs

/mnt/内部にwindows側のディスクがマウントされるのでこの中でコンパイルする。無事共存

f:id:mitsuo_0114:20190114113940p:plain

Step1, Step2

全く問題なし

Step3

Tokenのvalの部分で、long intとintのWarningが出るぐらいで問題なし。

Step4の前

構文木を組むことによって、演算子の順番の特定ができる話。若干理解が浅い部分。あとスタックマシンはコンピュータシステムの理論と実践で頑張ったからまぁわかる。アセンブラでスタックマシン実装した良い思い出。

読了 - コンピュータシステムの理論と実装 - エンジニア。

Step4

おおむね写経で済む。書いてないのは以下ぐらい。

循環で関数を読んでるためheaderに別だしする必要あり。もちろんMakefileも。
tokenizeで新しく追加した演算子に対応
地味にposの初期化がないのでこれも適当に実装。

Cの理解が浅くて可変長Vectorの実装が出来なくて泣きたい。引き続き実装を進める。

個人的に勇気づけられたのはここ。不思議な感じがする＝理解が浅いと思っていたが筆者が言ってるんだからこの不思議な感じは理解とは別物なんだろうな。

正直、再帰には非常に慣れているはずの筆者ですら、こういったコードが動くのは一種の魔法のように感じます。再帰的なコードは、仕組みがわかっていてもどこか不思議な感じがするのですが、それはおそらくそういうものなのでしょう。