読了 - Unix考古学 Truth of the Legend

Unix考古学　Truth of the Legend【電子書籍】[ 藤田　昭人 ]

アルゴリズムの話だけだと脳がないので読んだ本もつらつらと。 とはいえ時間かけてもしょうがないのでざっと。

ケントンプソンとデニスリッチーの話からUNIXの時代をざっと見る。 最後まで行っても自分は生まれなかった。

正直、Linuxしか触ってない人間にはUNIXなんてMacOSの一部で、SolarisとかIBM AIXとか使っているのは知っている程度。 物語の中に出てくる話はあまりピンとくるところが多くなかった。 それでも、DECに勤めていた人と知り合いだったのでそのあたりの話は興味をもって読めた。

技術面だと、最近ちょこちょこ手を出している低レイヤー部分の実装が どのようにしてOSに組みあがっていったのかが何となく想像できるような内容。 アセンブラが人間の手で組み立てられてコンパイラが出来、コンパイラがコンパイラを作り、 UNIXが物理レイヤーへの依存を吸収したとき、そのときが今の時代のOSの始まりなんだろう。 また、今の時代でも使われて続けている仮想メモリ機構などは、当時の世界最高の大学の博士論文で構成されてる。

歴史的な話だと、独占禁止法によってAT&Tがソースコード開示という戦略を取った時から、オープンソースは始まった。 もちろん最初はオープンソースではなく、AT&Tがコンピュータを主力に置かないという見せしめのようなものだったのだけれども、 コミュニティが立ち、UNIXソースコードが開示されなくなった後は廃れずに、Linux含め、いろいろな方向に飛び火するわけだ。

映画などでノンフィクション物を見ることが多かったり、経営学の勉強をするときに1970年代～80年代の戦略や企業論を知るのだけれど、 その背景でコンピュータの世界がどう動いていったのか、時間軸を持ちながら知識を紐づけて学んでいきたい。

Kickstart Round G 2018 - Problem A. Product Triplets

Dashboard - Kickstart Round G 2018 - Google Code Jam

smallはまわすだけ、largeはむずい。 atcoderでいうと、smallは200点、largeは400点問題ぐらいだろうか。

def small_solve(case):
    nums = list(map(int, case.split(" ")))
    count = 0
    for x in range(len(nums)):
        for y in range(x + 1, len(nums)):
            for z in range(y + 1, len(nums)):
                xn, yn, zn = nums[x], nums[y], nums[z]
                if xn == yn * zn or yn == xn * zn or zn == xn * yn:
                    count += 1
    return count

0を特別扱いするところまでは思いついたが、 x = 0 and y = 0を特別扱いするか、x = 0 or y = 0を特別扱いするかあたりがうまく回らなかったのと、 x, y を定めた後のzをbinary searchしたがまだ遅かった。

from math import factorial as f
def large_solve(case):
    def nCr(n, r):
        return f(n) // f(r) // f(n - r)
    nums = sorted(list(map(int, case.split(" "))))
    counter = {i: 0 for i in nums}
    ans = 0
    for yi in range(len(nums) - 1, -1, -1):
        y = nums[yi]
        for xi in range(yi - 1, -1, -1):
            x = nums[xi]
            if y > 0 and x > 0:
                ans += counter[y*x] if x * y in counter else 0
        counter[y] += 1

    z = counter[0] if 0 in counter else 0
    if z >= 3:
        ans += nCr(z, 3)
    if z >= 2:
        ans += nCr(z, 2) * (len(nums) - z)
    return ans

今回の学び。

1. ソートすること、探索する計算は減らせる時がある。
2. 配列の組み合わせでx < y < zにおいて、x, yから計算結果をzに見つけるとき、逆順にすることでsearchをせずにカウントが可能。
3. pythonのrangeは逆順がとても読みにくいんだがきちんとかけるように。
4. 特別な場合はダブりに気をつければ、countだけとって別に計算することも出来る。今回の場合は0。

過去のkickstartをとことんやらなくては。

AtCoder Beginner Contest 089 - C

beta.atcoder.jp

知っててよかったitertools.combinations 頭文字ごとにカウントをした後、combinationsでMARCHの中から重複を許さずに3つ取ってくれるというなんて素晴らしい、な関数を使えばよい。 あらかじめ同名は削っておいたが異なるって条件があったことに後から気が付いた。

from itertools import combinations


def solve(N, Ss):
    caps = {c: set() for c in 'MARCH'}
    for s in Ss:
        caps.setdefault(s[0], set()).add(s)
    sum = 0
    for d in combinations('MARCH', 3):
        sum += len(caps[d[0]]) * len(caps[d[1]]) * len(caps[d[2]])
    return sum


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

AtCoder Beginner Contest 088 - C

beta.atcoder.jp

初め、aの存在範囲を勝手に-50 ~ 50としていて総当たりしたが間違いだと気が付く。 あくまでもa + bが0 <= a + b <= 100なのであってこれからa, bの存在範囲は決められない。

では違うアプローチ。 表のすべての値を足すとsum(a1, a2, a3, b1, b2, b3) * 3、というのはすぐわかる。3の倍数が出てきてうれしくなるが、これだけでは必要条件とはならなそう。 sum(a1, a2, a3, b1, b2, b3)がどこかにあるかと探すと、c11, c22, c33があった。 これらが3倍になっていることを確認すると、9つの数値が使われているのでよさそう、で実際よかった。

証明まで持ち込めはしないが直観的にはこれでいいか。

def solve(c1, c2, c3):
    if (c1[0] + c2[1] + c3[2]) * 3 == sum(c1) + sum(c2) + sum(c3):
        return "Yes"
    return "No"


if __name__ == "__main__":
    c1 = list(map(int, input().split(" ")))
    c2 = list(map(int, input().split(" ")))
    c3 = list(map(int, input().split(" ")))
    print(solve(c1, c2, c3))

AtCoder Beginner Contest 085 - C

beta.atcoder.jp

N枚のお札がすべてが5000円だったとして目標金額と合計金額の比較をすると、 合計金額を減らすためには5000円を1000円に変換するしかなく、 合計金額を増やすためには5000円を10000円に変換するしかない。 これを利用すればよい。 もし行ったり来たりしてもたどり着けないならばそれは不可能な数値。

実装上の注意としては、N枚目の変換が終わった後にもう一度判定を入れなくてはならないので、 ループをN+1回回すか、ループ終了後に再度判定を入れる必要がある。サンプルテストケースに助けられたので反省。 また、sumは毎回計算しても全然間に合ったが、本当は5000 * Nの初期値に対して変換のたびに-4000か+5000すれば追加の計算は不要。

もしお札が4枚だったら場合分け必要そうだから探索かな。。

def solve(N, Y):
    r = [5000 for _ in range(N)]
    for i in range(N + 1):
        s = sum(r)
        if s == Y:
            return (
            len([d for d in r if d == 10000]), len([d for d in r if d == 5000]), len([d for d in r if d == 1000]))
        elif s < Y and i < N:
            r[i] = 10000
        elif s > Y and i < N:
            r[i] = 1000
    return (-1, -1, -1)


if __name__ == "__main__":
    N, Y = tuple(map(int, input().split(" ")))
    print(" ".join(map(str, list(solve(N, Y)))))

AtCoder Beginner Contest 110 - C

beta.atcoder.jp

直観とテストケースに頼って実装してしまった。学びにならないのでよくない。

def solve(S, T):
    sm = {}
    tm = {}
    for s, t in zip(S, T):
        if s in sm and sm[s] != t:
            return "No"
        sm[s] = t

        if t in tm and tm[t] != s:
            return "No"
        tm[t] = s

    return "Yes"


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

改めて考えてみる。 Sの中に含まれるある文字で構成されるグループは、置き換えによって文字そのものは変わるものの、 そのグループの位置は変わらない。 そして、このグループは統合することも分割することもできない。

SからTに変換するための必要条件として、グループの構成が常に同じになる＝S中のある文字に対して、T側が常に同じ文字で対応する、というのがあげられる。 S->Tの対応だけを考えてしまうと以下のようなケースが通ってしまうため、T->S側の対応も確認し、常に同じグループであることを確認する。

S = bbbbcccc T = aaaaaaaa

って感じでよいのかな。

AtCoder Beginner Contest 113 - C

beta.atcoder.jp

ソートとカウントして出力を作ってから元の順番で。tupleは便利。

def solve(N, M, PYs):
    Ys = {i + 1: 1 for i in range(N)}
    ret = {}
    for p, y in sorted(PYs, key=lambda x: x[1]):
        ret[(p, y)] = "{:06d}{:06d}".format(p, Ys[p])
        Ys[p] += 1
    return [ret[(p, y)] for (p, y) in PYs]

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

しかし、日曜日にいきなりやられても。。参加したかった。