AtCoder Beginner ContestのD問題を解いた。 問題はこれ D - Maximum Average Sets。 解説はこれ https://atcoder.jp/img/abc057/editorial.pdf。 今回は問題自体の話ではなく、Counterのfor文の挙動がバージョンによってかなり違うということ。 次のコード…

AtCoder Regular ContestのD問題を解いた。 問題はこれ D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder。 解説はこれ AtCoder Regular Contest 036 解説。 書いてみたら、最後のテストケースだけREになって、なんでや！ってなって、調べた。 あっ…

pythonでやってる人が全然いない・・・。 トポロジカルソートよくわかんないけど、解けたから解説する。 AGC027のC問題 AtCoder Grand Contest 027のC問題です。 これ C - ABland Yard。 解説 公式の解説はこれ https://img.atcoder.jp/agc027/editorial.pdf…

unionfindの勉強をしたので。 unionfindはグラフの頂点で互いに繋がっているかどうかを判断するのに便利です。 追加の仕方がややこしくて、まだ全然、体に馴染んでない。 unionfindのプログラムの肝は、繋がっている頂点に対しては、同じ値を返すという関数…

優先度付きキュー(priority_queue)の勉強をしたので。 heap型を使えば良い。 heapはリストに比べて最小値の取り出しがはやく、新たな数の追加もはやい。 pythonにはheapqというmoduleがある。 heapqのheapには、基準となる数以外に別の数をtupleの形で持つこ…

これhttp://hos.ac/slides/20140319_bit.pdfを見ながら、これの基本問題をやった。 やり方はこれを見れば十分です。 問題設定はこちら。 N個の変数v_1, ..., v_n。 Q個のクエリ。 各クエリはv_a_jにw_jを加えるという操作。 answerは各クエリに対してv_1 + .…

atcoderで2分探索に気づけないので、覚えるために、書き残しておく。 問題はABC063のD問題。 D - Widespread 解説はこれ。 https://atcoder.jp/img/arc075/editorial.pdf 大事なのは中のコメントのみ(##以下)。 ついでだけど、遅かったので、少し修正した。#…

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

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

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

pythonでオセロのプログラムを書いた。 functions_othello.pyに使う関数をまとめた。 from functions_othello import * turn = 'black' #黒 B = board() #盤面生成 BP, able = check(B,turn) show_double(B,BP,turn) while able != 0: B, turn = place(B,BP,…

初めて幅優先探索の問題を解けたときの話。 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…