AtCoder Beginner Contest 047 - D - 高橋君と見えざる手 / An Invisible Hand

分割統治の良い練習だった。

indexes = []


def dfs(Ds, s, e, v=None):
    if e - s == 1:
        if v == Ds[s]:
            indexes.append((s, e))
        return Ds[s]
    else:
        center = (s + e) // 2
        left = dfs(Ds, s, center, v=v)
        right = dfs(Ds, center, e, v=v)

        left_m = - (10 ** 9)
        li = -1
        su = 0
        for i in range(center-1, s-1, -1):
            su += Ds[i]
            if left_m != max(left_m, su):
                left_m = max(left_m, su)
                li = i

        right_m = -(10 ** 9)
        ri = -1
        su = 0
        for i in range(center, e):
            su += Ds[i]
            if right_m != max(right_m, su):
                right_m = max(right_m, su)
                ri = i

        if left_m + right_m == v:
            indexes.append((li, ri))

        m = max(left, right, left_m + right_m)
        return m


def solve(N, T, As):
    Ds = [As[i + 1] - As[i] for i in range(N - 1)]
    max_v = dfs(Ds, 0, N - 1)
    dfs(Ds, 0, N - 1, v=max_v)
    return len(indexes)


assert (dfs([-50, 150], 0, 2) == 150)
assert (dfs([-20, 10, -30, 10], 0, 4) == 10)
assert (dfs([3, -6, 1, 4, -6, 3, 2, -6, -1], 0, 9) == 5)
indexes = []
assert (solve(3, 2, [100, 50, 200]) == 1)
indexes = []
assert (solve(5, 8, [50, 30, 40, 10, 20]) == 2)
indexes = []
assert (solve(10, 100, [7, 10, 4, 5, 9, 3, 6, 8, 2, 1]) == 2)

indexes = []
if __name__ == "__main__":
    N, T = map(int, input().split(" "))
    As = list(map(int, input().split(" ")))
    print(solve(N, T, As))

アルゴリズムイントロダクションで紹介されていた株価の話と同じでまずは最大部分和の問題に帰着できる。

最大部分和は、分割統治として解くことができ、 左半分部分、右半分部分、左右にまたがる部分のいずれか1か所に最大部分和ができることになる。 半分はさらに再帰し、一つになるまで分割する。 左右にまたがる部分は中央から左側と右側に伸ばし、一見、N2ですべて数え上げなければならないように見えるが、 それぞれで独立して最大値を計算することができるので、計算量はNになる。

最大部分和を求めたらもう一度動かして、何か所に出てくるかを数え、 これら複数個所出てきたときの処理を考える。

この時、複数個所のうちstart / endが被ることはない。例えばstart - startが被るとき、endは同じ値になってしまい、 問題の制約に反する。同様に、end-endが被るとstartが同じ値になる。

片方のstartがendと被るとき、例えば最大部分和が20だとして 20 - 40 と 40 - 60 ができたとする。この時、20 ~ 60の差が必ず最大部分和の2倍になり、20が最大部分和だという話に矛盾が出る。

これらから、複数個所の独立性が出てくる。

あとは、それぞれ一か所ずつ1ずつ削ってやればよいので、この最大部分和をもつ個所の数と同値になる。 Tは要らない!

AtCoder Beginner Contest 045 D - すぬけ君の塗り絵 / Snuke's Coloring

これは割とすんなり解けたかな。

from collections import Counter


def solve(H, W, N, ABs):
    total = (H - 2) * (W - 2)
    points = {}
    for a, b in ABs:
        a -= 1
        b -= 1
        for i in [-1, 0, 1]:
            for j in [-1, 0, 1]:
                if 0 < a + i < H - 1 and 0 < b + j < W - 1:
                    d = (a + i, b + j)
                    if d not in points:
                        points[d] = 0
                    points[d] += 1
    c = Counter([v for v in points.values()])
    ans = [total - len(points)] + [c[f] if f in c else 0 for f in range(1, 10)]
    return "\n".join([str(a) for a in ans])

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

H, Wがかなり大きいので、盤面すべてを記録する or 全3x3の正方形の走査は除外。 Nは走査がいけそうなので、各点から計算ができるかを考える。

ある点が影響を及ぼすのは高々9個のみ、つまり3x3正方形の中で0とならないものは最大でも 9 * N <= 9 * 105でこれを数えていけばよい。

教訓

  • (若干邪道だが)109なものは初めから数えられると思わず、数えられるものから考える。
  • 境界条件はやはり注意が必要。プログラムを実行せずに頭の中でちゃんと考える癖をつける。

AtCoder Beginner Contest 043 D - アンバランス / Unbalanced

400点問題だからと言って実装が必ず大変ってわけでもない。

def solve(s):
    for i, j in zip(range(0, len(s) - 1), range(1, len(s))):
        if s[i] == s[j]:
            return "%d %d" % (i + 1, j + 1)

    for i, j in zip(range(0, len(s) - 2), range(2, len(s))):
        if s[i] == s[j]:
            return "%d %d" % (i + 1, j + 1)

    return "%d %d" % (-1, -1)

assert (solve("ee") == "1 2")
assert (solve("eeded") == "1 2")
assert (solve("abcdd") == "4 5")
assert (solve("needed") == "2 3")
assert (solve("atcoder") == "-1 -1")
assert (solve("abaca") == "1 3")
assert (solve("cbaca") == "3 5")
assert (solve("abc" * 5000) == "-1 -1")

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

総当たりすればいけるのはすぐわかったのでまぁそれはよくて、 初めはしゃくとり法を考え付いたが、理解が浅くて使い方がままならず。

教訓

  • 分解してみると小さい問題だけで完結することがある。
  • 文字列のテストはやはり最初と最後まできちんと見れてるか。Indexの操作がたまに危うい。
  • 2文字の範囲、3文字の範囲のpythonのzip,rangeは頻出。考えずに打てるぐらいまで覚えたい。

読中 - 低レイヤを知りたい人のためのCコンパイラ作成入門

compilerbook.booth.pm

Linuxのブートプロセスの理解をしているのは世界にどれだけいるのだろう。

さて、Cでも勉強したいのだけれど、作りたいものが見つからない状況なのでコンパイラを作る。

環境設定

WindowsのCLionを使いたい。CLionとしてはMinGWやCygwinなどあるが、筆者の意図に合わせてこれをインストール。 Install Windows Subsystem for Linux (WSL) on on Windows 10 | Microsoft Docs

/mnt/内部にwindows側のディスクがマウントされるのでこの中でコンパイルする。 無事共存

f:id:mitsuo_0114:20190114113940p:plain

Step1, Step2

全く問題なし

Step3

Tokenのvalの部分で、long intとintのWarningが出るぐらいで問題なし。

Step4の前

構文木を組むことによって、演算子の順番の特定ができる話。若干理解が浅い部分。 あとスタックマシンはコンピュータシステムの理論と実践で頑張ったからまぁわかる。アセンブラでスタックマシン実装した良い思い出。

読了 - コンピュータシステムの理論と実装 - エンジニア。

Step4

おおむね写経で済む。書いてないのは以下ぐらい。

  • 循環で関数を読んでるためheaderに別だしする必要あり。もちろんMakefileも。
  • tokenizeで新しく追加した演算子に対応
  • 地味にposの初期化がないのでこれも適当に実装。

Cの理解が浅くて可変長Vectorの実装が出来なくて泣きたい。 引き続き実装を進める。

個人的に勇気づけられたのはここ。 不思議な感じがする=理解が浅いと思っていたが筆者が言ってるんだからこの不思議な感じは理解とは別物なんだろうな。

正直、再帰には非常に慣れているはずの筆者ですら、こういったコードが動くのは一種の魔法のように感じます。再帰的なコードは、仕組みがわかっていてもどこか不思議な感じがするのですが、それはおそらくそういうものなのでしょう。

個人情報。

www.chunichi.co.jp

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

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

elaws.e-gov.go.jp

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

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

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

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

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

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

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

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

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

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

f:id:mitsuo_0114:20190105174453p:plain

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

elaws.e-gov.go.jp

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

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

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

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

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

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

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

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

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

法律上の照会権限を有する者からの照会(刑事訴訟法第 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以上カウントされた因数を抽出、 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が混じったり真ん中の数値あたりは頭の中で作るのが難しい。 かなり時間食ってしまった。