個人情報。

www.chunichi.co.jp

これを書いた人はきっと警察が嫌いなんだね。

法律の専門家ではないが、個人情報保護法の例外の刑事訴訟法とさらにその例外の通信の秘密の話。

elaws.e-gov.go.jp

（目的）
第一条　この法律は、高度情報通信社会の進展に伴い個人情報の利用が著しく拡大していることに鑑み、個人情報の適正な取扱いに関し、基本理念及び政府による基本方針の作成その他の個人情報の保護に関する施策の基本となる事項を定め、国及び地方公共団体の責務等を明らかにするとともに、個人情報を取り扱う事業者の遵守すべき義務等を定めることにより、個人情報の適正かつ効果的な活用が新たな産業の創出並びに活力ある経済社会及び豊かな国民生活の実現に資するものであることその他の個人情報の有用性に配慮しつつ、個人の権利利益を保護することを目的とする。

以前、そこそこ年配の警察関係の方に話を聞いたことがある。

この法律は今からわずか１５年ほど前にできた法律で、施行当時はかなり混乱があった。 個人情報を持っている業者はすべからく、一切情報を渡してはいけないものだと解釈されてしまい、 捜査に必要な情報を警察が問い合わせても全然教えてくれなかったと。

例外の話。以下の通り、「次に揚げる場合を除く」とあるので、以下の場合には提供してもよいことになる。

第二十三条　個人情報取扱事業者は、次に掲げる場合を除くほか、あらかじめ本人の同意を得ないで、個人データを第三者に提供してはならない。
一　法令に基づく場合
二　人の生命、身体又は財産の保護のために必要がある場合であって、本人の同意を得ることが困難であるとき。
三　公衆衛生の向上又は児童の健全な育成の推進のために特に必要がある場合であって、本人の同意を得ることが困難であるとき。
四　国の機関若しくは地方公共団体又はその委託を受けた者が法令の定める事務を遂行することに対して協力する必要がある場合であって、本人の同意を得ることにより当該事務の遂行に支障を及ぼすおそれがあるとき。

とはいえ、これだけを読んで実業務で今持っている情報をいくら警察や公的機関だからと言って他人に渡していいのかなんて判断はできない。

この辺りをカバーするために、各省庁はガイドラインを出している。

また、実際、個人情報は個人情報保護法だけに守られているわけではなく、番号法や、金融関連は別に金融商品取引法があったり、 法律そのものよりも自分の会社の管轄省庁のガイドラインを見たほうが良い。

http://www.meti.go.jp/policy/it_policy/privacy/downloadfiles/2612hogo.pdf

ってことで刑事訴訟法がある「法令に基づく場合」を見てみる。

上記のように、法律および条文までが書かれている。

elaws.e-gov.go.jp

第二百十八条　検察官、検察事務官又は司法警察職員は、犯罪の捜査をするについて必要があるときは、裁判官の発する令状により、差押え、記録命令付差押え、捜索又は検証をすることができる。この場合において、身体の検査は、身体検査令状によらなければならない。

刑事訴訟法第２１８条はいわゆる令状での捜査。

この場合、これは「差し押さえ」になり企業側は命令として受け取ることになる。

第百九十七条　捜査については、その目的を達するため必要な取調をすることができる。但し、強制の処分は、この法律に特別の定のある場合でなければ、これをすることができない。
○２　捜査については、公務所又は公私の団体に照会して必要な事項の報告を求めることができる。

こちらが一般的な捜査事項関連照会書に基づくもの。これは「報告」を求めるものであって強制力はない。

とはいえ、さすがに法律なので、国家公務員の守秘義務規定などには抵触しないようになっている。（らしい）

ここで話がややこしくなるのが総務省が出しているガイドライン。

総務省｜電気通信消費者情報コーナー｜電気通信事業における個人情報保護に関するガイドライン

ここに以下のようにある。

法律上の照会権限を有する者からの照会（刑事訴訟法第 197 条第 2 項、少年法第 6 条の 4、弁護士法第 23 条の 2 第 2 項、特定電子メールの送信の適正化等に関する法律（平成 14 年法律第 26 号。以下「特定電子メール法」という。）第 29 条等）等がなされた場合においては、原則として照会に応じるべきであるが、電気通信事業者には通信の秘密を保護すべき義務もあることから、通信の秘密に属する事項（通信内容にとどまらず、通信当事者の住所・氏名、発受信場所、通信年月日等通信の構成要素及び通信回数等通信の存在の事実の有無を含む。）について提供することは原則として適当ではない。

（中略）

個々の通信と無関係かどうかは、照会の仕方によって変わってくる場合があり、照会の過程でその対象が個々の通信に密接に関係することがうかがえるときには、通信の秘密として扱うのが適当である。
いずれの場合においても、本人等の権利利益を不当に侵害することのないよう提供
等に応じるのは、令状や照会書等で特定された部分に限定する等提供の趣旨に即して必要最小限の範囲とすべきであり、一般的網羅的な提供は適当ではない。 

通信の秘密の保護のために、いくつかの法律においては提供が適当でない、とする見解。

これは、憲法の「通信の秘密は、これを侵してはならない。」がめっちゃ強いから。

そしてその通信の秘密とは「個々の通信に密接に関係することがうかがえる」場合。 が、「趣旨に即して必要最小限の範囲」の妥当性の判断にはリスクが高い。

自分の会社の管轄省庁のガイドラインを見たほうが良い、のは確かなのだが、 これだけ各会社が多角化しており、従うべきガイドラインが一つでではないため、明確に「適当ではない」というのはなかなか強く、通信の秘密にかかわるものは照会では出せないのが多分一般的。

大した結論はないけれども、警察庁も昔からこういうのを出したりしてる。 https://www.npa.go.jp/pdc/notification/keiji/keiki/keiki19991207.pdf

ちなみにLINEは透明性レポートを出している。 linecorp.com

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

atcoder.jp

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

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

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

一つは因数で検索がヒットした際に、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つしか取れない石取りゲーム。石取りゲームだったので動的計画法などではなく偶奇で取れると判断。

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

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

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

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

３本の木、４本の木の時も同様に。

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の値について一般化を考える。 「すべてが２」を相手に渡すためには、「２と３の混在」あるいは「すべてが３」の状況が自分の手番に来ればよい。 さらにこれらどちらかの状況は手番を自分の手番に持ってくるためには「すべてが４」である状況が相手の手番にあればよい。 同様に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終わったらもうきっと取れないだろうな。。

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

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

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

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

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

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

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

読了 - 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の世界が はっきりとその形を見せ、これこそが未来なのだとそう思わせてくれた。 大量のデータがシームレスに配信されてその場にどんどん出てくる。しかも動画とは違ってインタラクティブに。

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

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

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

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

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

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

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

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

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

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だけれど初めての完答だった。

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

前半は各美しさに対してまとめられる要素がなさそうなのであきらめて、 後半の高速化を考える。ビット毎の論理積を計算したときに最大となるためには、 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