忘れるので。 def gcd(a, b): while b != 0: a, b = b, a % b return(a)

最近、AtCoder 版！蟻本 (初級編)をやってる。 めっちゃ多い。 多重な動的計画法の実装がうまくいったから、見せびらかそうと思って、記事を書いてる。 本当は解説しようと思ったけど、めんどくさくなった。 問題はABC015のD問題D - 高橋くんの苦悩です。 解…

ABC106のD問題の解説の二重累積和がよくわからなかったので、簡単に証明をつけた。 まず、を二重配列と考えます。 の各列の累積和を取ったものをとします。 すると、 となります。 次に、の各行の累積和を取ったものをとします。 すると、 となります。 とい…

ABC104のD問題 ABC104のD問題で'B'を固定する解法についての解説。 D: We Love ABC - AtCoder Beginner Contest 104 | AtCoder 問題は次のようなものです。 ABCからなる文字列Tに対し、i ABC?からなる文字列Sが与えられたときに、?はABCそれぞれが入り、通り…

初めて幅優先探索の問題を解けたときの話。 ABC088のD問題を解いた。 白か黒で塗られたマスのうち、白のマスだけを通ってゴールする場合、 最大でいくつの白マスを黒マスに塗り替え得てもゴールできるか？という問題です。 白マスを通る最短経路を求めればよ…

ABC103のD問題のコード。 実行時間が、上のやつは2000msくらいで下のやつは500msくらい。 どこで4倍の差が出ているのかわからない。 N, M = map( int, input().split()) Q = [[int(s) for s in input().split()] for _ in range(M)] Q = sorted(Q) ans = 1 L…