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をずらしながら考える。

1111
1001
0111
0110

先ほどの通り、左の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

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

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

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

www.jdla.org

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

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

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

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

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

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

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

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

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

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

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

読了 - 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))