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

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

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

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

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

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

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

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

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

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

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

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

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

DP訓練。 tdpc.contest.atcoder.jp まずはDP抜きにして問題文がきちんと理解できていることを確認するために さくっと実装。 def solve(N, Ps): cs = set() cs.add(0) for p in Ps: d = set() for c in cs: d.add(c + p) cs.update(d) return len(cs) if __n…

beta.atcoder.jp 答えを見たらもっと楽だった。 確認時の比を t : a、前回までの累計をT, A、前回確認時からの差分をx , yとしたとき以下が成り立てばよい。 T + x : A + y = t : a 式にしてこれを整理すると、 x = (t * A + y * t) / a - T y = (a * T + x …

beta.atcoder.jp 基数ソートで計算量N。 普通のソートはNlogNなのでソートそのものは間に合うけれども 挿入回数が1010まで行くのでばらばらに数値を扱うと間に合わなさそう。 def solve(N, K, ABs): counts = {i: 0 for i in range(1, 10 ** 5 + 1)} for a, …

beta.atcoder.jp 無向グラフの探索。再帰よりもキューのほうが好き。深さ優先と幅優先の切り替えが楽だから。 def solve(N, M, Es): al = {} for e in Es: al.setdefault(e[0], []).append(e[1]) al.setdefault(e[1], []).append(e[0]) ans = 0 q = [(1, [1]…

Tenka1のログインアカウント間違えて参加してしまった。。 とはいえ、300点、400点問題あたりに壁を感じるので過去問練習。 abc042.contest.atcoder.jp 数が少ないので総当たり。最大 2N 回繰り返されるかな。 def solve(N, K, Ds): while True: c = set([in…

以下3問。Div2って書いてなかったけど多分Div2。 Easy: Make737Easy Medium: AliceAndBobMedium Hard: SimpleMathProblem 公式Editorial Single Round Match 737 Editorials - Topcoder 2.0