Le Algorithm: Codeforces

ラベル Codeforces の投稿を表示しています。すべての投稿を表示

2015年8月30日日曜日

CodeForces #306 Div2 D : D. Regular Bridge

問題：
橋を持つk-正則グラフを作れ。ただし作れないときはNOと答えよ。

解法：
明らかにk=2のときはグラフはCycleとなるのでNO.
一般に、kが偶数であるときはNOとなる。
(証明)
kが偶数のときにk-正則グラフに橋が存在すると仮定する。
すると、その橋を取り除くことによって二つのグラフに分解することが出来る。
しかし、それぞれのグラフについて、次数の和は奇数となってしまうので矛盾。

以上よりkが偶数の時はNOと答えれば良い。ではkが奇数の時はどのようにして構成出来るか？

kが奇数の時は
完全二部グラフK(k-1,k-1)を構成し、それぞれの頂点集合をA,Bとする。
Aの各頂点マッチングを結ぶ(k-1は偶数なので存在する)
頂点vを新たに一つ用意し、vとBの各頂点を結ぶ。
このように構成したグラフの次数について見ていくと、vの次数はk-1で、そのほかの次数はkとなる。
よってこのグラフを二つ用意しそれぞれのv同士を結べばその辺が橋になり、しかもグラフはk-正則となる。

ソースコード:
https://gist.github.com/knewknowl/4c17af4dde6f43e9bdc7

2015年7月1日水曜日

Codeforces Round 311 D Vitaly and Cycle

問題

http://codeforces.com/contest/557/problem/D
多重辺や自己ループを含まないグラフが与えられる。またこのグラフでは辺の重みは全て1として考える。
この辺にいくつか辺を追加して長さ奇数の閉路(ただし自己ループではない)を一つ以上含むグラフにしたい。ただし元々辺があるノード間に新たに辺を追加するのはできない。

最小何本の追加で達成できるか。またその最小本数の追加は何通りあるか。

解法

入力で与えられるグラフの頂点数をn,エッジ数をmとする。
追加する最小本数tは0,1,2,3のどれかである。
グラフの最大次数が0の時、辺は1本もないのでt=3で、追加の仕方は全部の頂点から3個選んだ通りになるのでnC3となる。
グラフの最大次数が1の時、長さ3の閉路を作ればよく、この時t=2である。この時は辺とその辺に含まれない頂点の中から1個選べば良いのでm*(n-2)である。
それ以外の時、BFSまたはDFSによってグラフに奇数の閉路がないか調べる。あった場合はt=0で追加の仕方は1通り。奇数の閉路があった場合、頂点を2色で塗り分けて同じ色どうしの頂点をエッジで結べば長さ奇数の閉路ができるので n1 chose 2 + n2 choose 2で計算できる。ただしn1,n2はそれぞれ色1,2で塗られた頂点の個数。

Codeforces Round 311 C : Arthur and Table

問題
http://codeforces.com/contest/557/problem/C
n本の脚がついたテーブルがある。各脚の長さがL[i]で与えられる。このテーブルの脚を何本か切り落としてテーブルをStableな状態にしたい。テーブルがStableであるとは
・一番長い脚の本数が残っている脚の中で過半数を占めている
ということを指す。また、脚が1本だけのテーブルはStableであるとする。
テーブルの各脚を切り落とすにはコストが必要でそれぞれのコストがd[i]で与えられる。
Stableにするための最小コストを求めよ。
制約としてn<=10^5, L[i]<=10^5, 1<=d[i]<=200

解法
脚の長さでソートしたあと、最長の脚をL[i]にした時の最小コストというのを各iについて求めれば良い。
最長の脚をL[i]にした時の最小コストというのは、
1. L[i]より長い脚を全て切る
2. L[i]より短い脚を、L[i]の脚が過半数になるようにコストが小さい順に切っていく
ことによって得られる。
1はコストの累積和をあらかじめ計算しておけば簡単に求められる。
2は今脚L[i]をみている時に、それまでみていた脚の中でコストjの脚が何本あるかというヒストグラムを保持しておけば高速に求められる(d[i]が200以下であるため)

CF Round 309 C Kyoya and Colored Balls

問題:

http://codeforces.com/contest/554/problem/C
k色ボールが全部でn個ある。
各色のボールはa[i]個ある(つまりn=Σa[i])
このボールを以下の条件を満たすように横に並べる時、その並べ方は何通りあるか。ただし同じ色のボールは区別しない。

条件: 全ての色i=1,2,...,k-1に対して、並べた色iのボールの中で一番左側にあるものをp[i]と表すと、p[i]はp[i+1]の右側にある。

入力はkと各a[i]で、制限はn<=1000, k<=1000である。

解法:

例えばk=2の場合を考えてみます。
一番左にくるのは必ず色kでなければならず、その時残りのボールの並べ方について考えてみます。
まず最初に色1のボールa[1]個を横一列に並べると、一番左に置いたもの以外の色2のボールa[2]-1個は色1のボールに割り込む形で入れていくことが可能です。
例えばa[1]=○5,a[2]=3の場合だと、まず最初に
1 1 1 1 1 2
と並べたあと残りのa[2]-1=2個のボールは
○ 1 ○ 1 ○ 1 ○ 1 ○ 1 ○ 2
この6個ある○の中のどこかに2個入れるということになります。これは重複組み合わせになっているのでconbinationを使って求めることができます。
3色以上の場合も同様で、まず最初に色1を並べる。そのあとに一番左に置いたあとに色2を並べる。その次に一番左に色3を置いたあとに置けるところに色3のボールを置いていく...というのを繰り返すことで求めることが出来ます。

2015年6月28日日曜日

CF Round310 Div1 C : Case of Chocolate

問題

http://codeforces.com/problemset/problem/555/C
n×nのグリッド上にチョコレートがある。
直線:x+y=n+1上の点からスタートして上または左に食べ進んでいく。
すでに訪問済みの座標にくるまで直進していく。
座標と方向のクエリが与えられるので、各クエリごとに何個のチョコレートを食べることができるかを求める問題。

解法

(sx,sy)から上に進む場合を考える。
この時、今までのクエリの開始地点のx座標の中でsxより大きいものの中で最小の座標mxを求める。そのクエリq'が
・上方向のクエリだったら、xからmxの間にあるチョコレートに対するクエリは存在しないので、q'が進めた分 + mxとxとの距離が食べられるチョコレートの数となる。
・左方向のクエリだったら、そのクエリの開始座標のy座標まで進める。
つまりq'を二分探索で求めれば良い。

2015年5月4日月曜日

VK Cup 2015 - Round 3 : C. Idempotent functions

Problem:

http://codeforces.com/problemset/problem/542/C

Algorithm:

Given some x and do below for many times:
x <- f(x)
Observe the transition of x and find out that there is loop.(the shape is like "ρ")
For example, suppose n=6 and f is
f : i -> i+1 (i=1,2,3,4,5)
6 -> 3
and when x=1, then
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> ...
and the loop is 3->4->5->6 -> ...
also, if we start with x=5, then
5 -> 6 -> 3 -> 4 -> ...

when x is in the loop, then x moves only in the loop. So, let k is the length of loop(in this example, k=4) and m is some multiples of k, f^m(x) moves x to x(if x is in the loop).
For x that is not in the loop will go to loop for big k. Let s is minimum number of step that is needed to go to loop for all x.(in this example, 2 steps needed to go loop and s=2), then f^(m+s)(x) moves all points to loop. and this is Idempotent.

And we must be carefull that there is some "ρ".
So, we need s to be the longest "stick" and m to be the LCM of length of loops.

2015年4月13日月曜日

CF 534D. Handshakes

問題

http://codeforces.com/problemset/problem/534/D
n人の人がいて、適当な順番で部屋に入る。部屋に3人以上いたら、適当な3人組は部屋の外に出て行ってよい(出て行ったら二度と部屋に来ない)(出て行かなくても良い)
どの人も、部屋にx人いたらx人全員と握手をする。
さて、それぞれの人が「何人と握手したいか」という希望を入力として与えられるとき、全員の希望を満たすような部屋の入り方の順番はあるかどうか。あったらその順番を出力せよ。

解法

「希望人数が多い人」から握手させていけば良い。

CF 534C. Polycarpus' Dice

問題

http://codeforces.com/problemset/problem/534/C
n個のサイコロがあってサイコロiの目は1〜diのいずれかが出る。
このn個のサイコロをふって出た目の総和がAだとする。
このとき、各iに対して「サイコロiの出た目の数としてあり得ない目の数」の種類数を求める問題。
例えば、普通の6面のサイコロを2個ふってその目の和が8だったら、どちらのサイコロも1の目が出ることはあり得ないため、答えは{1,1}となる。

解法

各サイコロiに対してその目の出うる目の数の下限と上限を考える。
「サイコロiがxを出して他のサイコロが全部本気出してもAには届かないよなぁ」
というxのうち最大のもの+1が下限で、これをx1
「サイコロiが本気出してyの目が出たとき他のサイコロが全部1の目になってもAより大きいなぁ」
というyのうち最小のもの-1が上限(の候補の一つ)で、これをy1
とおくと、
サイコロiのでうる目の値は
[max(1,x1) , min(y1,di)]
となる。あとはdiからこの区間内の整数の個数を引けば良い。

ただしn=1の時はA=出たサイコロの目のはずなので、di-1を出力すれば良い。

2015年3月30日月曜日

CF 527 C .Glass Carving

問題

http://codeforces.com/problemset/problem/527/C

解法

二分探索

2015年3月1日日曜日

CF 518 C. Anya and Smartphone

問題

http://codeforces.com/problemset/problem/518/C
スマホのホーム画面のアイコンを選択するのに最小のタップ数を求める感じの問題。

解法

読んで書くだけ

CF 518D. Ilya and Escalator

問題

エスカレーターの前にn人並んでいる。先頭の人は1分毎に確率pで勇気を振り絞ってエレベーターに乗り、1-pでその場にとどまる。エレベーターに乗れるのは先頭の人だけ。また、一度乗ったエレベーターは二度とおりることはない(こわい)
この時、t分後にエレベーターに乗っている人数の期待値を求める問題。