読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

codeforces #393 div2 A, B, C

Codeforces 競技プログラミング

codeforces.com

問題A

問題概要

 月とその月が何曜日から開始するかが与えられる。この月で1週間ごとに列が切り替わるカレンダーを作成する際、カレンダーは何列になるか。

解法

 1, 3, 5, 7, 8, 10, 12月は31日、2月は28日、4, 6, 9, 11月は30日である。1列目に書く日数を1ヶ月の日数から引いた後、7で割った数の天井関数が答えになる。


問題B

問題概要

 n個の要素から成り和がmの数列を考える。数列の隣り合う要素の差が2以上にならないようしたい。このとき、最大となるk番目の要素の大きさを求めよ。

解法

まず、差が2以上にならないことからk番目の要素が最も大きくその隣の要素が1小さい数、その隣の要素がさらに1小さい数…となっていく。
 例としてn=4, m=7, k=1のときを考える。まず、全ての要素が1以上であることから全ての要素に1を加え、mからnを引く。その後、k番目の要素をプラス1したいときは階段状になるように各要素に数を加えて、加えた分mを引いていく。
(丸の数が各要素の値、丸の中の数が加える順番)
f:id:ferin_tech:20170310020030p:plain
この加算を行った後もmがまだ残っている場合、各要素に(残っているm)/nを足すことが可能である。(図でいうと底上げするようなイメージ)


問題C

問題概要

 n頂点n辺の有向グラフが与えられる。このときすべての頂点について入次数と出次数は共に1である。各頂点に2状態を持つ物体が置かれている。辺に重みがついていて、重みが1の辺を移動すると状態が反転する。重みの変更、辺の繋ぎ変えを行うことで全ての物体が各頂点を両方の状態で通過するようにしたい。変更を行う最小の回数を求めよ。

解法

条件から考えて有向な閉路が1個または複数個存在する。
 状態の変化について考える。重みが1の辺が偶数個のとき一周回って同じ頂点に戻ってくる際も出発したときと同じ状態であり、両方の状態で各頂点を通過することは不可能である。逆に重みが1の辺が奇数個のとき両方の状態で各頂点を通過することができる。したがって、重みが1の辺が偶数個であれば1回変更する必要がある。
 次に辺の繋ぎ変えを考える。閉路がn個存在するとき、n個の辺をつなぎ替えることで全ての閉路をつなげることが可能である。閉路の個数はUnionFind木を用いることでO(nα(n))で求めることができる。

問題文の読解に時間を取られた…