スピード勝負だった。Fは結局解けない。。 atcoder.jp 数列が与えられ、特定の数列の値を別の値に書き換える操作を行う。 操作ごとにすべての和を答える。 Dにしてはとても簡単。 初期段階での数列の和を取っておいたとき、 BをCに変化させたとき、Bがb個あ…

Eまで通せたが、もうちょっと早くやりたかった。 atcoder.jp こっちは割と典型問題。素因数分解を行った後で、各素数pにおいて p1, p2, p3.... とzを取っていけばよい。素因数分解の実装がさくっとかけたのは満足。 def factrization(N): k = 2 ret = {} L =…

atcoder.jp イワシは相性によってグルーピングができる。 このグルーピングさえうまく処理できれば、あとは数え上げればよい。 a匹のグループAとb匹のグループBの相性がそれぞれ悪かった時、 各グループの内部での取る取らないで2のa乗、2のb乗通りできる。 …

atcoder.jp 30分ぐらい。もう少し早く解きたかった。 まず、10100のおかげで、K個取るとき、K+1個取るとき、K+2個取るとき、・・・で、和がかぶることはなく独立して考えることができる。 N＝10とし、このうち3個だけを考えてみたとすると以下の11個の中から…

atcoder.jp 上から作ったり、下から作ろうとしたり、dpを考えてみたが、 0の扱いが難しくて、下からは作れなかったし、上から作ると、何番目、の扱いが非常に面倒。 しばらく考えて苦肉の策として、Nがそこまで大きくないこととサンプルテストに最大値が出て…

atcoder.jp もう少し早くできた、、はず。 ワーシャルフロイドの本質をきちんと理解してなかったが故に実装に時間がかかった。 当然、Nの制約からワーシャルフロイドを直接使ったO(N3)はできないが、 それでも、ワーシャルフロイドの考え方がベースになって…

しばらくやめてたがまた再開する。 atcoder.jp 「一つだけ抜く」パターンは全体をあらかじめ求めておいて、その抜かれた影響を考えることで計算量がO(N)になるケースが多い気がする。 今回もそんな感じで、抜かれた数字が元々C個あったとすると、そのうちの2…

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

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

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

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

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

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

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

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

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

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…

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

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

分割統治の良い練習だった。 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 …

これは割とすんなり解けたかな。 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 -…

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…

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

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

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

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

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

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

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

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 …