CADDi 2018 for Beginners - C.Product and GCD / D.Harlequin

atcoder.jp

とりあえずPを素因数分解して、因数ごとのカウントを取る。

なるべくN個の数値に分配してあげることを考えるために、N以上カウントされた因数を抽出、 2個以上分配できる可能性も考え、Nで割った商を分配する。 ansにはこれらをすべてかけたものを入れてあげる。

また、素因数分解する際には少し高速化をしないと間に合わないので2つ高速化。

一つは因数で検索がヒットした際に、iを最初まで戻さずにもう一度同じ因数をチェックする。

もう一つは因数を調べるときに√Pより検索値が大きくなったらその場で探索を打ち切って、残ったPを因数にする。

from collections import Counter

def d(P):
    c = Counter()
    i = 2
    while (P > 1):
        if P % i == 0:
            c.update([i])
            P //= i
            i -= 1
        i += 1
        if i > P ** 0.5:
            c.update([P])
            break
    return c


def solve(N, P):
    c = d(P)
    ans = 1
    for k in [k for k, v in c.items() if v >= N]:
        ans *= k ** (c[k] // N)
    return ans

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

atcoder.jp

ソースコードはとても短いので思考をもう一度。 1つの木から1つしか取れない石取りゲーム。石取りゲームだったので動的計画法などではなく偶奇で取れると判断。

小さく考える。まず、1本の木に1つのリンゴしかない場合、最後のりんごと取ったほうが勝ちなので"first" 1本の木に2つのリンゴがあったら、必ず相手が勝ちとなる状況を作らざるを得ないので"second" 3個のリンゴも同様。assert文にすると以下な感じ。

assert (solve(1, [1]) == "first")
assert (solve(1, [2]) == "second")
assert (solve(1, [3]) == "first")

次に2本の木にそれぞれ1つのリンゴしかない場合、すべてのりんごを取ればいいので"first" 2個ー1個となってた場合、2個ー0個にして相手に渡すことで、先手が勝てるので"first" 2個ー2個となっていた場合、先手は1個ー1個、2個ー1個の状況、つまり必ず相手が勝ちとなる状況を作らざるを得ないので"second"

assert (solve(2, [1, 1]) == "first")
assert (solve(2, [2, 1]) == "first")
assert (solve(2, [2, 2]) == "second")

3本の木、4本の木の時も同様に。

assert (solve(3, [1, 1, 1]) == "first")
assert (solve(3, [2, 1, 1]) == "first")
assert (solve(3, [2, 2, 1]) == "first")
assert (solve(3, [2, 2, 2]) == "second")

assert (solve(4, [1, 1, 1, 1]) == "first")
assert (solve(4, [2, 1, 1, 1]) == "first")
assert (solve(4, [2, 2, 1, 1]) == "first")
assert (solve(4, [2, 2, 2, 1]) == "first")
assert (solve(4, [2, 2, 2, 2]) == "second")

これらから、N本の木として考えたとき、 「すべてが1」の時は"first”が勝て、 「1と2が混在」している場合、1となっている部分をすべて取ってしまえば、「すべてが2」の状況を相手に渡すことができるため、先手が必ず勝てることになる。 「すべてが2」となっていた場合では「すべてが1」か「1と2が混在」を相手に渡さざるを得ず、勝つことができない。

さらにaの値について一般化を考える。 「すべてが2」を相手に渡すためには、「2と3の混在」あるいは「すべてが3」の状況が自分の手番に来ればよい。 さらにこれらどちらかの状況は手番を自分の手番に持ってくるためには「すべてが4」である状況が相手の手番にあればよい。 同様にaが「すべての同じ偶数」について言え、「すべてが同じ偶数」が来たら負ける。

では異なった数の場合はどうなるか。 2本の木に[3, 5]と存在していた場合、先手は[2, 4]とすべてが偶数の状況を後手に渡せばよい。 後手がりんごと取った後は[1, 3], [2, 3], [1, 4]のいずれかの状況となり、いずれの状況においても先手は[0, 2], [2, 2], [0, 4]とすべてが偶数の状況を作って後手に渡すことができる。 これを繰り返していくと、0個となった木を除くことでのいつか「すべてが同じ偶数」となる状況を必ず後手に渡すことができる。ので、先手が勝利する。

逆に最初の状況で[偶数, 偶数]となっていた場合、 後手は先手にすべてが偶数の状況を渡すことができるので後手が勝利する。

ソースコードはかなり簡単になる。pythonのallは便利や。

def solve(N, As):
    As = [1 if a % 2 == 1 else 2 for a in As]
    if all(a == 2 for a in As):
        return "second"
    else:
        return "first"

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

あとsolve と mainの間にassertは便利ね。 もしassert落ちたらそもそも手のテストができなくなって無駄なテストをすることがない。

初めての二桁順位。Beginner終わったらもうきっと取れないだろうな。。

f:id:mitsuo_0114:20181222225832p:plain

AtCoder Beginner Contest 115 - C. Christmas Eve / D. Christmas

beta.atcoder.jp

ソートすると、ある位置から右に距離Kにある木が差が最小値になることが保証される。 ので、これを0からN-Kまで動かせばよい。

def solve(N, K, Hs):
    Hs.sort()
    return min([b - a for (a, b) in zip(Hs[:], Hs[K - 1:])])


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

beta.atcoder.jp

昔どこかでこれのもっと大きい数字の中で特定の小範囲に対して同じように計算をしたことがある。 今回は範囲が0から必ず始まる代わりに広範囲になる。

あるN番目のバーガーは、 P / (N-1) / B / (N-1) / Pという構造になる。 そこで、Xの位置を以下5通りに場合分けする。

一番左
左側の(N-1)の途中
真ん中のB
右側の(N-1)の途中
右側のP

そしてそれぞれで、再帰含めて考える。

一番左の時、N=0でなければ必ず0、N=0ならば1
左側の(N-1)の途中のときは、一番左側の分一つ引いて、N-1へ再帰を実行。
真ん中のBの時は、上と同様に再帰を実行したうえで、真ん中のBの分プラス1する。
右側の(N-1)の途中の時は左側の再帰、真ん中のBの分、そして右側の分の再帰。
右側のPまで言っていたらN-12つ分と真ん中のB

全体の数はa(n+1) = 2a(n) + 3なので、漸化式。高校数学の知識でN番目のバーガの厚みは計算可能。 で、あとメモ化すれば、O(logN)でいける。

memo = {}


def solve(N, X):
    if (N, X) not in memo:
        l = (pow(2, N + 2) - 3)
        l2 = (l - 3) // 2 + 1
        if N == 0:
            return 1
        if X == 1:
            return 0
        elif X <= l2:
            memo[(N, X)] = solve(N - 1, X - 1)
        elif X == l2 + 1:
            memo[(N, X)] = solve(N - 1, l2 - 1) + 1
        elif X < l:
            left = solve(N - 1, l2 - 1)
            right = solve(N - 1, X - 1 - l2)
            memo[(N, X)] = left + 1 + right
        elif X == l:
            memo[(N, X)] = solve(N - 1, l2 - 1) * 2 + 1
    return memo[(N, X)]


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

特定の小範囲でやっていた時には一つの場所を特定するためにある特定の位置だけ渡して、再帰を行ったが、 今回はカウントなのでそれをしてしまうとループカウントで時間切れになってしまう。 ので、大まかに再帰を切ってカウントにする。メモ化はNとXにしたがNだけでもこれよかったな。

境界値あたり、特に0や1が混じったり真ん中の数値あたりは頭の中で作るのが難しい。 かなり時間食ってしまった。

読了 - NEVER LOST AGAIN

books.rakuten.co.jp

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

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

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

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

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

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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 114 C. 755 / C.756

beta.atcoder.jp

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

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

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を素因数とすると以下のいずれかを満たすことができる素因数の組み合わせを数えればよい。

k4 * l4 * d2

k4 * l14

k24 * l2

k74

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

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

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個選択して最大を取る部分の2か所に分かれる。

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

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

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

ではここでどのように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空間のアルゴリズムにも使えそうだから楽しいと思うんだ。