Inside-Python - lru_cache

functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.7.3 ドキュメント pythonのlru_cacheはアノテーションとしてユーザの関数をデコレーションすることができ、 その呼び出しを監視し、結果をキャッシュするものである。 この実装はなかな…

Inside-Python - heapqとPriority Queue

最近cpythonのソースコードの中まで見ることが多いので、ネタごとにまとめてみる。 queue --- 同期キュークラス — Python 3.7.3 ドキュメント heapq --- ヒープキューアルゴリズム — Python 3.7.3 ドキュメント heapqはPythonの中で、二分ヒープを実装したも…

AtCoder Beginner Contest 126

ルール変更でBeginnerになりました。 atcoder.jp Nの制約がテストケースと違う気がする。 あまり確率の問題は得意ではないが、これはそこまで難しくない。 まずサイコロで初期確率は1 / Nずつになる。 さらにそれぞれの場所から始めたとき、Kを超えるまで連…

Google Code Jam Round1A - Alien Rhyme / Golf Gophers

codingcompetitions.withgoogle.com Alien Rhyme 接尾辞が一致するペアを可能な限り作る問題。 問題文読むのがつらいが、文字は50文字しかないので、実装自体はそこまで難しくない。 対象となる全Wordの末尾を取得し、2個以上被るものがあればそれを抜けばよ…

diverta 2019 Programming Contest

残念、Unratedになってしまった。運営の方々お疲れ様です。 atcoder.jp 例のごとく、assertの量がドはまり感を醸し出す。 まず、”AB"が含まれている場合はよい。で、単に末尾のAと先頭のBだけでなく、両方とも満たす場合は別に考える必要がある。 ここからAB…

Google Code Jam Qualification Round 2019 - Cryptopangrams / Dat Bae

https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/000000000008830b 疑似的な暗号化問題。 26個の素数が選ばれ、大小関係を維持したまま各アルファベットに割り当てられる。 アルファベットから構成される文章が各文字ごとに対応…

Google Code Jam Qualification Round 2019 - Foregone Solution / You Can Go Your Own Way

codingcompetitions.withgoogle.com 1813位でした。 Foregone Solution https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231 任意の数値を二つの和に分ける。ただし、その和は4を使ってはならない。 1桁ずつ、繰上…

AtCoder Grand Contest 033

AtCoder Grand Contest 032はRatingは上がったけれど大した問題は解けなかったので割愛。 Google Code Jamも書かなきゃ。 atcoder.jp 幅探索だろうとは思いつつ、あまり実装してなかったので、複数のスタート地点をまとめても全く問題がないことに気が付くま…

AtCoder Grand Contest 031

ついに水色になれた。精進します。 atcoder.jp "文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。" ここを若干勘違いして10分ほどロス。 それぞれの文字から1個以下ずつ選び、最後にすべてゼロの分を抜けばよい。 fro…

AtCoder Beginner Contest 121

400点とれなかったー。回答なしで時間切れ後にできるのは悔しい。 atcoder.jp これは200点問題だろう、、。解説も要らん。 def solve(N, M, ABs): ABs = sorted(ABs) ans = 0 for a, b in ABs: if b < M: ans += a * b M -= b else: ans += M * a break retu…

AtCoder Beginner Contest 120

全ACできた。 atcoder.jp 初めは01と10の探索から始めたが、発見をした後、2個進める必要があるためforじゃ回しにくいと、 そもそもindexの扱いにして最初と最後のindexの操作を実装した、、が1文字目のindex走査がかなり複雑になり、 簡単なテストケースは…

AtCoder Beginner Contest 119

久しぶりに全AC。。よかった。 atcoder.jp Nの数から全数え上げをする問題、とすぐに気が付いたが、ある竹がAに取られたとき、B、Cには使えないという表現をどう数え上げるのに苦労した。 すべての竹に対し、A,B,Cあるいはいずれにも使われないという4パター…

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 …

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 -…

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…

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

compilerbook.booth.pm Linuxのブートプロセスの理解をしているのは世界にどれだけいるのだろう。 さて、Cでも勉強したいのだけれど、作りたいものが見つからない状況なのでコンパイラを作る。 環境設定 WindowsのCLionを使いたい。CLionとしてはMinGWやCygw…

個人情報。

www.chunichi.co.jp これを書いた人はきっと警察が嫌いなんだね。 法律の専門家ではないが、個人情報保護法の例外の刑事訴訟法とさらにその例外の通信の秘密の話。 elaws.e-gov.go.jp (目的) 第一条 この法律は、高度情報通信社会の進展に伴い個人情報の利…

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

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

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__ == "…

読了 - NEVER LOST AGAIN

books.rakuten.co.jp かつては道に迷う自由もあった、ってのは中学だか高校の国語の教科書に出てきた記憶がある。 Google Earth、Google Map, ストリートビューそれらの誕生の話。 当時自分は中学ぐらいだっただろうか、まっぷるの地図を買っていろんなとこ…

AtCoder Beginner Contest 114 C. 755 / C.756

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

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はソートしても一般性を失わない…

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 …

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

人工知能は人間を超えるか【電子書籍】[ 松尾 豊 ]ジャンル: 本・雑誌・コミック > PC・システム開発 > その他ショップ: 楽天Kobo電子書籍ストア価格: 972円 これは出版された頃に読んだんだが近々検定を受けるのでもう一度勉強しなおした。 www.jdla.org Li…

Kickstart Round F 2018 - Problem A. Common Anagrams

Dashboard - Kickstart Round F 2018 - Google Code Jam あーよかったさくっと解けた。 連続した文字列でのアナグラムを含んだ一致数を数える。 文字数が最大50文字なので、1文字の時、高々50パターン、2文字の時49パターン、、となる。 この状況では、50+1 …

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

www.oreilly.co.jp 少し前に読んだのだけれど面白かった。 まずは大学ぶりにHDLを使って回路を組む。 NAND回路のみを使ってOR/ANDから始まり、マルチプレクサへ行き、クロックが入ってきてメモリ、レジスタ 最終的には機械語命令の仕様に沿ってALUとレジスタ…

読了 - Unix考古学 Truth of the Legend

Unix考古学 Truth of the Legend【電子書籍】[ 藤田 昭人 ]ジャンル: 本・雑誌・コミック > PC・システム開発 > その他ショップ: 楽天Kobo電子書籍ストア価格: 2,808円 アルゴリズムの話だけだと脳がないので読んだ本もつらつらと。 とはいえ時間かけてもし…

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(…

AtCoder Beginner Contest 089 - C

beta.atcoder.jp 知っててよかったitertools.combinations 頭文字ごとにカウントをした後、combinationsでMARCHの中から重複を許さずに3つ取ってくれるというなんて素晴らしい、な関数を使えばよい。 あらかじめ同名は削っておいたが異なるって条件があった…

AtCoder Beginner Contest 088 - C

beta.atcoder.jp 初め、aの存在範囲を勝手に-50 ~ 50としていて総当たりしたが間違いだと気が付く。 あくまでもa + bが0 <= a + b <= 100なのであってこれからa, bの存在範囲は決められない。 では違うアプローチ。 表のすべての値を足すとsum(a1, a2, a3, b…