かつては道に迷う自由もあった、ってのは中学だか高校の国語の教科書に出てきた記憶がある。 Google Earth、Google Map, ストリートビューそれらの誕生の話。

当時自分は中学ぐらいだっただろうか、まっぷるの地図を買っていろんなところを見ていた記憶がある。住宅地図はどこから手に入れたんだろう。 Perlという言語も知らず、箱庭諸島で遊び、どこかの掲示板で書き込みをしていた、Age of Empire Ⅱのパッケージゲームを雪の中、セブンイレブンだかに取りに行った。 WInMXなんてものもあっただろうか。そのたった数年後、高校でガラケーでメールを打っていたころ、世界の裏側ではすさまじいことが起きていた。高校の卒業のころ、自転車で八王子から二子玉川あたりまで行った。海が見たくて、湘南の海までも行った。まだブックオフで買った地図を握りしめてた。

大学でコンピュータサイエンスを学んで、どうもCSSってのはなかなかにすごいやつで同じhtml構造に対してあっという間に見た目を変えることができるんだなんてことをやっていたころ、 Google Earthをブラウザで見た記憶がある。

これFlashなのか？でもFlashのアニメーションを作ってるやつに見せてもらったやつとはずいぶんと違うな。どうもこれはAjaxっていう技術を使っているらしい、動的にページをロード？動的にページを構築？ブラウザってhtmlを表示してCSSで色付けて、JavaScriptってのは危ないんだろ？なんでこんな八王子の端っこのほうの地図まで乗ってるんだ？世界から注目されるような街だったか？というかこれ体験版だよね？なんのパッケージも買ってきてないんだけど。

今まで、きらきらてかてか文字色や背景色が変わるだけだったWebの世界がはっきりとその形を見せ、これこそが未来なのだとそう思わせてくれた。大量のデータがシームレスに配信されてその場にどんどん出てくる。しかも動画とは違ってインタラクティブに。

当時の自分にはこれの存在が何を意味するのかを十分に理解はしていなかった。が、それは自分に限らず、ラリーとセルゲイ以外には作ってる人ですらわからなかったらしい。

アメリカ全土を５年かけて起こした後、世界の上位２００都市の航空写真を買うために300万ドルの予算を求めていったMTGで

「地球全土のライブラリ、まるごと買いあげたら？」

と言い放ち実際に800万ドル分かけて買ってしまった。

良いシステムは情報をよりよく映し、よりよく映された情報は新たな情報を集める。無料ならなおさら。そしてそうして集まった情報は、ほぼすべての人類を道に迷う最後の世代としてしまった。

昔、研究者になりたかった時期があった。それは個人の幸せよりも、人類としての一歩を進めることこそ人生の本義だと思っていたから。 Google Mapは実は発明としての新しいことはしていない。世界中の地図会社が無料で地図を提供し、航空写真を集め、路線・バス、道の名前や建物名前があり、それをちょっとブラウザで映すだけだ。ただそれを、信じられないスピードで組み合わせ、無料で表示しているだけだ。

ただ、それがどれだけ実現不可能か、それは当時でも今でも容易に想像ができる。

あと５年ぐらい早く生まれて、時代の変遷を大人の目で見たかった。学生の時に時代が変わりすぎてて追えていない。追えなかったのが年齢が原因か、時代が原因かわからんのだ。

でもまぁ、この時代でこのプロダクトを目の当たりにできた素晴らしさはかみしめよう。あと技術的な内容はもうちょっと読みたかった。

2018-12-02

AtCoder Beginner Contest 114 C. 755 / C.756

beta.atcoder.jp

Nが10⁹まで行くのでO(N)を目指すと間に合わない。そもそも七五三数は10⁹以下に対して、3,5,7のみで構成される数値は、高々3**9 = 19683個しかないため、この中から七五三数かつ、N以下のものを探す。

初め３進数として数え上げをしようとしたが、うまくいかず。itertools.productに変更。今思うと、３進数ではゼロパディングをし忘れていた。

from itertools import product

def solve(N):
    sum = 0
    for k in range(1, 10):
        for i in product('357', repeat=k):
            if '3' in i and '5' in i and '7' in i:
                d = int("".join(list(i)))
                if d <= N:
                    sum += 1
    return sum


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

beta.atcoder.jp

N<=100のため、Nの累乗はそのままでは扱えない。 Nの累乗の素因数分解結果は、2, 3, 4, ... Nの素因数分解結果を統合したものに等しくなり、この結合した素因数の部分集合はすべて、Nの累乗の約数であり、この中から七五数を見つける。

75個の正の整数の約数を持つとき、75 = 5 * 5 * 3 = 15 * 5 = 25 * 3であるため、 k, l, dを素因数とすると以下のいずれかを満たすことができる素因数の組み合わせを数えればよい。

k⁴ * l⁴ * d²

k⁴ * l¹⁴

k²⁴ * l²

k⁷⁴

from collections import Counter
from itertools import combinations


def prime_factors(n):
    c = Counter()
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                c.update([i])
                n //= i
                break
    return c


def factrials(n):
    c = {}
    for i in range(2, n + 1):
        d = prime_factors(i)
        for k, v in d.items():
            if k in c:
                c[k] += v
            else:
                c[k] = v
    return c


def solve(N):
    facts = factrials(N)
    over2 = [k for k, v in facts.items() if v >= 2]
    over4 = [k for k, v in facts.items() if v >= 4]
    over14 = [k for k, v in facts.items() if v >= 14]
    over24 = [k for k, v in facts.items() if v >= 24]
    over74 = [k for k, v in facts.items() if v >= 74]

    sum = 0
    # 4 - 4 - 2
    sum += len([(d, d4) for d in over2 for d4 in combinations(over4, 2) if d not in d4])
    # 4 - 14
    sum += len([(d, d4) for d in over14 for d4 in over4 if d != d4])
    # 2 - 24
    sum += len([(d, d2) for d in over24 for d2 in over2 if d != d2])
    # 74
    sum += len(over74)

    return sum

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

コンテストとしてはBeginnerだけれど初めての完答だった。 f:id:mitsuo_0114:20181202222251p:plain

2018-11-26

CODE THANKS FESTIVAL 2018 - C. Pair Distance

beta.atcoder.jp

from itertools import combinations
def slow_solve(N, Xs):
    ans = 0
    for pairs in combinations(Xs, 2):
        ans += abs(pairs[0] - pairs[1])
    return ans

まずは遅く総当たり。で、高速化を考える。

まず、Xはソートしても一般性を失わない。

x0 - x1 - x2 - x3

ここで、まとめられる計算がないかを考える。各間は何回も同じ場所を足すのでここはまとめられそう。

x1 - x2の間をd1としたとき、ここはx0 - x2 / x0 - x3 / x1 - x2 / x1 - x3で通る場所である。

つまりこれを一般化すると、diは、x0 ~ xiまでの一つとx(i+1) ~ xnまでの一つ選ぶ時の通り数だけ通る場所であるのでこの回数をかけながら距離を計算すれば計算量O(N)で、カウントできることになる。 0 ~ iまでの一つの選び方はi + 1通り、 i + 1 ~ nまでの一つの選び方は n - (i + 1) 通り

def solve(N, Xs):
    ans = 0
    Xs = sorted(Xs)
    for i, j in zip(range(N), range(1, N)):
        d = abs(Xs[j] - Xs[i])
        c = ((i+1) * (N-i-1))
        ans += d * c

    return ans

2018-11-26

Dwango Programming Contest V - Program B. Sum AND Subarrays

beta.atcoder.jp

とりあえず遅いとわかりつつも総当たり

 from itertools import combinations
 def slow_solve(N, K, As):
     alls = []
     for i in range(N):
         for j in range(i + 1, N + 1):
             alls.append(sum(As[i:j]))
     m = 0
     for c in combinations(alls, K):
         a = 0xFFFFFFFFFFF
         for p in c:
             a &= p
         m = max(m, a)
     return m

で、ここから高速化を考えていく。

全体を通して、N(N+1)/2個に対する美しさの計算部分と K個選択して最大を取る部分の２か所に分かれる。

前半は各美しさに対してまとめられる要素がなさそうなのであきらめて、後半の高速化を考える。ビット毎の論理積を計算したときに最大となるためには、 ANDを取った時になるべく左側にビットが立つようにしてあげればよい。それより右がどうなろうとも、そこで最大値が決まる。

bit計算をすることによって１つの美しさに対して、O(log N)に計算量が落とせる。全体としてはO(N² * log N )

美しさの計算段階でまず２進数にする。今回は10⁹ * 1000 = 10¹² = E8 D4A5 1000 < FF FFFF FFFF = 40bitだけあれば十分。ここを10⁹で計算していて時間をロスした。

ではここでどのようにK個を取るかを考える。

以下の4つをベースにKをずらしながら考える。

先ほどの通り、左のbitから一つずつ見ていく。

まず、K=3の時、一番左のbitを立てることは不可能であるので、次のbitに行き、ビットが立っている行だけを取ればよい。

K=2の時、一番左のビットが立てられれば良いので、上の二つを取ればよい。

K=1の時、一番左のビットを見ている段階では、上の二つのうちどちらを取ればよいかが不明であるが、上の二つのうちどちらかを取れば良いことがわかるのでこれらをターゲット、かつ次のbitから検索をかければよい。

まとめると再帰がいけそうなので、検索bit位置と、検索対象列を引数に関数 find(i, alls) として、i番目のbitの立っている数と比較、K個ピッタリでbitが立っている場合を探す。

また、K個以上bitが立っていた場合、そのbitが立っている美しさに絞ったうえで、次のbitに検索をかけるが、これ以降で一つも見つからない可能性がある。それはすなわちどれをとっても同じ（次のbit以降はすべて0にしかなりえない）ということなので、適当に最初からK個を取る。

見つけたものはすでにMAXの保証があるので、同じようにAND計算してあげればよい。

def solve(N, K, As):
    alls = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            alls.append("{:041b}".format(sum(As[i:j])))
    def find(i, alls):
        if i > 40:
            return []
        ones = [a for a in alls if a[i] == "1"]
        if len(ones) < K:
            return find(i + 1, alls)
        elif len(ones) == K:
            return ones
        elif len(ones) > K:
            ret = find(i + 1, ones)
            if len(ret) == 0:
                return ones[0:K]
            else:
                return ret
 
    ans = find(0, alls)
    if len(ans):
        a = 0xFFFFFFFFFFF
        for p in ans:
            a &= int(p, 2)
        return a
    else:
        return 0

2018-11-17

読了 - 人工知能は人間を超えるか

人工知能は人間を超えるか【電子書籍】[ 松尾　豊 ]

これは出版された頃に読んだんだが近々検定を受けるのでもう一度勉強しなおした。

www.jdla.org

Lispの時代からGoogleのネコ、DeepBlue、Alpha Goまで入ってたかな。これまでのAIの歴史を冬の時代も含めて解説してくれる素晴らしき良本。

AIは間違いなくコンピュータサイエンスの一つの到達点であるし、エンジニアを名乗る以上は真正面から立ち向かっていなかなくてはならないもの。夢物語と今できていることをきちんと理解して使えるようにしていくわけだ。

今のAIは学習するべきデータは人間が与えるしかなく、どのようなデータを与えるかによって当然結果も変わってくるのだからそのあたりはまだまだ人間が考えていかなくてはならない。

ボストンダイナミクスのロボット工学も素晴らしく、 AIがもし自分でデータを手に入れ始めることができるようになり、かつ計算にかかるエネルギーもどうにかなったとしたらきっとそこにシンギュラリティが現実的に目前に来るんだろうな、と思う。

ディープラーニング活用の教科書【電子書籍】[ 日本ディープラーニング協会 ]

こっちも目を通したんだが、IT企業の活用事例は画像処理以外あまり多くない印象。というのもログの解析などでは特徴量が人間がかなり完璧なものを見つけてしまうからなんじゃないかと思う。ただそれも人の目で見れる範囲の話。時系列データなども含めて解析をし始めたらまた人間にはよくわからないけれどもAIが見つけてしまう怪しいログなどが出てくるんだろうな。

もう一度線形代数からやり直そう。 3D空間のアルゴリズムにも使えそうだから楽しいと思うんだ。

2018-11-15

Kickstart Round F 2018 - Problem A. Common Anagrams

Dashboard - Kickstart Round F 2018 - Google Code Jam

あーよかったさくっと解けた。

連続した文字列でのアナグラムを含んだ一致数を数える。

文字数が最大50文字なので、1文字の時、高々50パターン、2文字の時49パターン、、となる。この状況では、50+1 * 25 < 1300程度にしかパターンができないので、それぞれcollections.Counterでカウント数をとっておき、 A,Bそれぞれでパターンを収集、マッチングさせる。

1300* 1300の力業でも計算量は大した量ではないので実装の楽さを優先して以下のように実装。ほぼすべてデバッガーの実行時チェックなしで書けたのは良い感じ。

from collections import Counter
def solve(A, B):
    L = len(A)
    acounters = []
    bcounters = []
    for i in range(1, L+1):
        for j in range(0, L-i+1):
            acounters.append(Counter(A[j:j+i]))
            bcounters.append(Counter(B[j:j+i]))
    c = 0
    for a in acounters:
        if a in bcounters:
            c += 1
    return c

2018-11-15

読了 - コンピュータシステムの理論と実装

www.oreilly.co.jp

少し前に読んだのだけれど面白かった。

まずは大学ぶりにHDLを使って回路を組む。 NAND回路のみを使ってOR/ANDから始まり、マルチプレクサへ行き、クロックが入ってきてメモリ、レジスタ最終的には機械語命令の仕様に沿ってALUとレジスタを組み合わせる。

プログラミングは1行ずつ実行されるが、このレイヤーだと1クロック時にすべての結線で同時に論理演算が進むので、デバックするのが大変。ここまでで10時間ぐらい使っただろうか。

機械語を理解するCPUを作ったら、次はアセンブラ。アセンブラといってもほとんど機械語に直で変換できるので軽くシンボルテーブルと定数あたりを作成すればおしまい。

@0
D=M
@1
D=D-M
@10
D;JGT
@1
D=M
@12
0;JMP
@0
D=M
@2
M=D
@14
0;JMP

これが

0000000000000000
1111110000010000
0000000000000001
1111010011010000
0000000000001010
1110001100000001
0000000000000001
1111110000010000
0000000000001100
1110101010000111
0000000000000000
1111110000010000
0000000000000010
1110001100001000
0000000000001110
1110101010000111

これになる。なんてわからない。

この後、中間コードをアセンブラにコンパイルするコードを書く。この辺りは演算や関数呼び出しのスタックなどをアセンブラで自分で書く必要があり、コピペでは全く太刀打ちできない。

例えば以下のような7 + 8 を演算する中間コードがある。

push constant 7
push constant 8
add

これを1行ずつ読み込み、以下のようなアセンブラを出力するプログラムを書くわけだ。

@7
D=A
@SP
AM=M+1
A=A-1
M=D
@8
D=A
@SP
AM=M+1
A=A-1
M=D
@SP
AM=M-1
D=M
A=A-1
M=M+D

もちろん単純な演算だけでなく、JMP命令につながるものや関数呼び出しも作る。以下はフィボナッチ数列のコード。アセンブラは400行を超える。

function Main.fibonacci 0
push argument 0
push constant 2
lt                     // checks if n<2
if-goto IF_TRUE
goto IF_FALSE
label IF_TRUE          // if n<2, return n
push argument 0        
return
label IF_FALSE         // if n>=2, returns fib(n-2)+fib(n-1)
push argument 0
push constant 2
sub
call Main.fibonacci 1  // computes fib(n-2)
push argument 0
push constant 1
sub
call Main.fibonacci 1  // computes fib(n-1)
add                    // returns fib(n-1) + fib(n-2)
return

x86やatomをきちんと学んだわけではないけれど、特定のレジスタにConstant値を入れて、それを参照しながら別のレジスタやメモリに対してアクセスをかけるアセンブラのコードは高級言語にはない特有の読みにくさがあり、良い勉強になった。

プログラムコードを中間コードにコンパイルするときには構文解析から始まって一度内部的にXMLを作成したうえで、これらを中間コードに落とし込む。このような構文解析と出力の分離はLLVMの階層構造にもつながるところがあり、LLVMというものが流行っているのかなどと考えさせられるきっかけにもなった。

The Architecture of Open Source Applications: LLVM

実装はなかなかつらかったが、低レイヤーを歩き始めるには非常に良い本であった。

エンジニア。

読了 - NEVER LOST AGAIN

AtCoder Beginner Contest 114 C. 755 / C.756

CODE THANKS FESTIVAL 2018 - C. Pair Distance

Dwango Programming Contest V - Program B. Sum AND Subarrays

読了 - 人工知能は人間を超えるか

Kickstart Round F 2018 - Problem A. Common Anagrams

読了 - コンピュータシステムの理論と実装