CS Academy #41 - Candles
問題
問題概要
本のろうそくがある。番目のろうそくの長さはである。一晩ろうそくを使用すると長さは1だけ減る。
これから、回の夜を過ごそうとしている。日目の夜には、本のろうそくを灯そうと考えている。最大で過ごせる夜の回数を求めよ。
アイデア
できるだけ多くのろうそくを残し続けた方がいいので、その日ごとに長い方から本のろうそくを貪欲に選んで使用するのが最適であるのは分かる。 ただ、それを愚直に処理するのは無理なので、効率よく処理することを考える。
ろうそくを、長さの降順でソートしておけば、使用するろうそくの番号は区間になる。その使用した状況をBITで管理する。その時、1番目から番目を使用することになるのだが、ろうそくを使用後にもソートされた状態を保ちたいので、番目のろうそくの長さに注目し、その長さをとすると、以上の長さの位置までは素直に先頭から減少させ、と同じ長さの区間だけはソートされた状態を保つためにできるだけ後ろのものを減少させる。その区間の位置の左端と右端は二分探索によって探せばよい。
実装(C++)
続きを読むCS Academy #40 - Direct the Graph
問題
問題概要
頂点数の完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。
アイデア
まず、問題に答える前に、あるトーナメントに対して、経路長3の閉路の個数を数え上げるにはどうすればいいだろうか(コンテスト時間中は、ある辺に対して、他のある頂点と閉路をなすかチェックするしか思いつかなかった)。
逆に満たしていないものの個数を数えて、全体から引くことを考えてみる。全体で通りの3点を選ぶ方法があり、その3点の間にある有向辺が閉路をなしていないもののの個数を数える。すると、閉路をなさない形は下の図のようなパターンのみに帰着する。
それぞれの頂点の(入次数,出次数)
に注目すると、それぞれ(0,2)
、(1,1)
、(2,0)
となっている。
数え上げのためには、このどちらも出ている頂点とどちらも入ってくる部分に注目して、頂点の入次数を、出次数をと表すと、数え上げの重複を考慮して、経路長が3である閉路の個数は
となる。
本題に戻ると、この閉路の個数を最大化したい。各頂点に対する辺の個数の制約によって、であるから、これを最大化するにはとはできるだけ等しい値にすると良い。そのようなグラフは、各に対してちょうど半分(またはと)になるように辺の向きを割り当てるのが良い。(実は01を交互に出力をすると今回の出力形式だとそれが実現できる(隣接行列の上三角部分を出すので))。
inとoutが各頂点に均等に分かれるようにすれば良さそうってのは何となくあったけど数え上げができなかった…