裏紙

ほぼ競プロ、たまに日記

CS Academy #41 - Candles

問題

CS Academy

問題概要

n本のろうそくがある。i番目のろうそくの長さはh_iである。一晩ろうそくを使用すると長さは1だけ減る。

これから、m回の夜を過ごそうとしている。i日目の夜には、c_i本のろうそくを灯そうと考えている。最大で過ごせる夜の回数を求めよ。

  •  1 \le n,m \le 10^5
  •  1 \le h_i \le 10^5
  •  1 \le c_i \le 10^5

イデア

できるだけ多くのろうそくを残し続けた方がいいので、その日ごとに長い方からc_i本のろうそくを貪欲に選んで使用するのが最適であるのは分かる。 ただ、それを愚直に処理するのは無理なので、効率よく処理することを考える。

ろうそくを、長さの降順でソートしておけば、使用するろうそくの番号は区間になる。その使用した状況をBITで管理する。その時、1番目からc_i番目を使用することになるのだが、ろうそくを使用後にもソートされた状態を保ちたいので、c_i番目のろうそくの長さに注目し、その長さをxとすると、x+1以上の長さの位置までは素直に先頭から減少させ、xと同じ長さの区間だけはソートされた状態を保つためにできるだけ後ろのものを減少させる。その区間の位置の左端と右端は二分探索によって探せばよい。

実装(C++)

続きを読む

CS Academy #40 - Direct the Graph

問題

CS Academy

問題概要

頂点数nの完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。

  •  3 \le n \le 2000

イデア

まず、問題に答える前に、あるトーナメントに対して、経路長3の閉路の個数を数え上げるにはどうすればいいだろうか(コンテスト時間中は、ある辺に対して、他のある頂点と閉路をなすかチェックするO(n^3)しか思いつかなかった)。

逆に満たしていないものの個数を数えて、全体から引くことを考えてみる。全体で\binom{n}{3}通りの3点を選ぶ方法があり、その3点の間にある有向辺が閉路をなしていないもののの個数を数える。すると、閉路をなさない形は下の図のようなパターンのみに帰着する。

f:id:imulan:20170803043532p:plain

それぞれの頂点の(入次数,出次数)に注目すると、それぞれ(0,2)(1,1)(2,0)となっている。

数え上げのためには、このどちらも出ている頂点とどちらも入ってくる部分に注目して、頂点vの入次数をin(v)、出次数をout(v)と表すと、数え上げの重複を考慮して、経路長が3である閉路の個数は

 \displaystyle \binom{n}{3}  - \frac{\sum_{v} \binom{in(v)}{2} + \binom{out(v)}{2} }{2}

となる。

本題に戻ると、この閉路の個数を最大化したい。各頂点に対する辺の個数の制約によって、in(v) + out(v) = n-1であるから、これを最大化するにはin(v)out(v)はできるだけ等しい値にすると良い。そのようなグラフは、各vに対してちょうど半分(またはxx+1)になるように辺の向きを割り当てるのが良い。(実は01を交互に出力をすると今回の出力形式だとそれが実現できる(隣接行列の上三角部分を出すので))。

inとoutが各頂点に均等に分かれるようにすれば良さそうってのは何となくあったけど数え上げができなかった…

実装(C++)

続きを読む