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

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のボールを置いていく...というのを繰り返すことで求めることが出来ます。

Code Festival : B - 枕決め

問題:

http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_d
m人の人がいる。それぞれの人は好みの枕の高さの範囲[xi,yi]が与えられる。
n個の枕がある。それぞれの枕の高さはh[i]で、これも与えられる。
枕は一人一つ使うものとして、最大で何人の人が枕を使うことが出来るか、人数を求めよ。

解法:

貪欲法で解ける。
まずは点と区間でソートする。
priority_queueを用意する(突っ込むものは区間で、ソート基準は右側の座標の小さい順)

点x[i]について、
1.その点を含むような区間をすべてpriority_queueに入れる。
2.priority_queueから区間を取り出し、もしそれがx[i]を含むものであったらx[i]はその区間とマッチング。そうでないならばpriority_queueから点を取り出し続ける。
3.マッチングの個数を出力

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'を二分探索で求めれば良い。

AOJ埋め

簡単な問題をたくさん解いた。

2021 : 姫血液の問題。memo[ノード][冷凍残り時間]でdjikstra
1145 : ゲノム文字列の問題。構文解析. 長さがインデックスになるまで解凍する感じ。
1138 : 馬車チケットの問題。memo[ノード][持ってるチケット]でdijkstra
1140 : 掃除ロボットの問題。bfsで各汚れ間の距離を出して10!通り試す。
1136 : 折れ線を探す問題。回転したやつとかを全部探索するだけ。回転は虚数掛けると楽
1127 : 宇宙ステーションの問題。最小全域木やるだけ。
2399 : プライバシーを守る問題。やるだけ。
2019 : 姫が護衛を雇う問題。貪欲法。
1165 : 角角画伯の問題。やるだけ。
2151 : 姫が護衛を雇う問題。memo[ノード][残り予算]でdjikstra
2402 : 星間ダイクストラの問題。五角形にして星同士の距離やってdijkstra
2182 : Eleven Loverの問題。なめるだけ。
1189 : 素数洞窟の問題。メモ化探索。
1187 : ICPCのランキング付けの問題。プレディケート書いてソートするだけ。
2014 : WとBの柵の問題。やるだけ。
1335 : 漸化式立ててメモ化。漸化式考えるの楽しかった。
2007 : お釣りを渡す店員が親切な問題。持ってる金全部渡してみるというのがわかれば楽
2012 : 宇宙ヤシガニの問題。探索の順番。
1142 : 列車の文字列の問題。やるだけ。
1125 : できるだけ沢山木をとる問題。英語読むだけ。
1137 : ローマ数字の足し算の問題。YARUDAKE.

こんな問題がDとかに来てていいのかよ、って感じの問題が散見された。