2019-02-01から1ヶ月間の記事一覧
問題 atcoder.jp 解法 の値が大きい方から小さい方に辺を張ると考えても良いので、そう考える。 となるような i, j, k を考え、頂点kからiかjのどちらかに辺を引くことを考える。 i-j 間のコストは j-k 間のコストは i-k 間のコストは の場合、 だから だか…
問題 http://codeforces.com/contest/1131/problem/Eある文字列 S と T が与えられた時、文字列 S の長さを m として S と T の積を と定義する。文字列 p1, p2, ..., pN が与えられるので の中で同じ文字が連続して現れる回数の最大値を求めよ。 解法 pN 以…
問題 atcoder.jp 解法 頂点 v から v+1 へ、長さ 0 の辺と、長さ の辺を張る。これによって、 の長さのパスが存在することになる。次に、頂点を の順番で見ていく。頂点 0 から頂点 v へは の長さのパスが存在するので、頂点 v から頂点 n-1 へ長さ t の辺を…
atcoder.jpこのコンテストに出たのですが、散々な結果だった。ただ、終わった後に流れてきた解法を見ると結構シンプルなものが多かったので、復習した。 A - ツーリストXの旅行計画 A - ツーリストXの旅行計画 分散が出てきてややこしい気持ちになるが、平均…
当たり前っちゃ当たり前だが、 vec.sort_by_key(|&value| heavy_function(value)); みたいなことをすると、 heavy_function が比較のたびに呼ばれるので、ソートが遅くなる。これは sort_by_cached_key でなんとかなるっぽい。sort_by_key は This sort is s…