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…

AtCoder Beginner Contest 085 - C

beta.atcoder.jp N枚のお札がすべてが5000円だったとして目標金額と合計金額の比較をすると、 合計金額を減らすためには5000円を1000円に変換するしかなく、 合計金額を増やすためには5000円を10000円に変換するしかない。 これを利用すればよい。 もし行っ…

AtCoder Beginner Contest 110 - C

beta.atcoder.jp 直観とテストケースに頼って実装してしまった。学びにならないのでよくない。 def solve(S, T): sm = {} tm = {} for s, t in zip(S, T): if s in sm and sm[s] != t: return "No" sm[s] = t if t in tm and tm[t] != s: return "No" tm[t] …

AtCoder Beginner Contest 113 - C

beta.atcoder.jp ソートとカウントして出力を作ってから元の順番で。tupleは便利。 def solve(N, M, PYs): Ys = {i + 1: 1 for i in range(N)} ret = {} for p, y in sorted(PYs, key=lambda x: x[1]): ret[(p, y)] = "{:06d}{:06d}".format(p, Ys[p]) Ys[p]…

AtCoder Beginner Contest 075 - C

beta.atcoder.jp 計算量的に一本ずつ外して探索して結果を確認すればよい。 あんまり実装しない隣接行列と再帰でやったが若干はまった。 あんまりなれない実装はするもんじゃないな。 def solve(N, M, ABs): ans = 0 for i in range(M): adjMat = [[0 for _ …

AtCoder Beginner Contest 079 - C

beta.atcoder.jp binaryで総当たり。やっと何も見ずにformatの中身をかけた。 evalはまぁ便利なので若干邪道と思いつつ使う。pythonばっかりつかってるとC++でちゃんと書けるか不安になる。 def solve(ABCD): for i in range(0, 8): ops = "{:03b}".format(i…

AtCoder Beginner Contest 046 - D / 047 - C

beta.atcoder.jp 気づけるか。そこが勝負。 解説の通りなんだけれども、得点を最大化する戦略はパーを出すだけ出す。 そして並び順はどうでもよい。 というのも、相手がグーを出しているとき、グーからパーにすると+1ポイント。 相手がパーを出していると…

AtCoder Beginner Contest 076 C

beta.atcoder.jp 辞書順最小を目指すためにはなるべく前のほうにaを入れてあげる = Tの検索は後ろから。 |S| - |T|の位置から始めて前に行き、Tの長さだけ? or S[i] = T[i]であることを調べる。 pythonのallはfor / if / flagな文を一つのif分にまとめられる…

AtCoder Beginner Contest 070 C / 073 C

beta.atcoder.jp 読んだらわかる、最小公倍数やん。コードは覚えてないけれども。 最小公倍数を求めるときには、最大公約数を求めるのが定石。 というのも最小公倍数を求めるときには a * bの約数のうち、共通で取り除いても問題ないものを取り除く必要があ…