torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Fenwick Tree

TopCoder, SRM 627, Division 2, Level 3 : BubbleSortWithReversals

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13256&rd=16008 問題概要 整数列 が与えられる。高々 個のオーバーラップしない の連続する部分列を反転させる操作をした後、 をバブルソートで昇順ソートする。発生する交換操作の回数を…

TopCoder, SRM 627, Division 1, Level 2 : GraphInversions

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13275&rd=16008 問題概要 頂点からなる無向・重み無しで連結なグラフが与えられる。辺の数は に等しく。 番目の辺は と を結んでいる。更に、各頂点には(頂点番号とは別に)整数値が割り…

POJ 1990 : MooFest

問題文 http://poj.org/problem?id=1990 概要 N 匹の牛が一直線上に並んでおり、各牛について、その聴力と x 座標が与えられる。 異なる二頭の牛同士は、座標の差(の絶対値)に大きい方の聴力を乗じた音量で会話をする。 全ての牛が会話をした場合の音量の…