SRM614-618 Div1E

今日はサークルオリエンテーションというのがあって久しぶりに大学にいった 農工大新入生でプログラミングに興味のある人はMCCに来て競プロやりましょう!(ここで宣伝しても...)

・SRM614 Div1E MinimumSquare

平面上にn個の点がある.このうちk個以上の点が内側にある(境界線上はダメ)ような正方形の面積の最小値を求めよ,という問題.

WAを出してしまってわからず人のブログを読んだ.あるl,rをきめてx座標がl以上r以下の領域に注目すると領域内の点をy座標でソートして連続するk個の点を選ぶことでk個以上の点を囲む最小の長方形が求まる(あとはよしなに).これを全ての(l,r)についてやるのだがかんがえるべき座標は点のx座標として出てくるものだけなのでペアはO(n^2)個.

・SRM615 Div1E AmebaDiv1

n個のゼリーがあり,i個目のゼリーの大きさはX[i]である.アメーバは自分と同じ大きさのゼリーに出会うとそれを食べて大きさが2倍になる.大きさxのアメーバが番号順にゼリーを見ていったとき最終的に大きさf(x)になるとする.集合S={f(x)|x∈N}に含まれない自然数の個数を求めよ.

自分と同じ大きさのゼリーが存在しない場合はf(x)=xなので集合Sに含まれる.よってアメーバのはじめの大きさとしてはXに現れる数だけをかんがえればいい.各大きさのアメーバについて最終的な大きさを計算し,Xに現れる数のうち何個が現れないかを数えればよい.

・SRM616 Div1E WakingUp

Aさんの眠気は整数で表される.眠気が正の間は寝ているが,0以下になった瞬間おきる.単位時間ごとにAさんの眠気はDだけ増加する.n個のアラームがあり,これは時刻start[i]からperiod[i]ごとに鳴ってAさんの眠気をvolume[i]だけ減らす.Aさんがいずれおきてしまうような眠気の初期値のうち最大のものを求めよ(ただしどんなに大きくてもいずれおきてしまうなら-1と答えよ)という問題.

時刻を0-indexedでかんがえる(startの値を1減らす)とi番目のアラームはt≡start[i](mod period[i])であるような時刻tに鳴るといえる.こうすると周期性がわかりやすくて,period[0],period[1],...,period[n-1]のlcmをLとしたとき時刻Lごとに現象が繰り返されることがわかる.よってまず1周期で眠気がどれくらい増加するか(または減少するか)を調べ,減少していたら十分な回数この周期を繰り返せばはじめどんなに眠くてもおきるので-1と答えればいい.そうでないときは,はじめの眠気をxとしたとき1周目の間におきることがないかを調べればおきるかどうか判定できるので,にぶたんしてやる.

・SRM617 Div1E MyLongCake

長さnのケーキがある.あらかじめケーキをいくつかのピースに分割しておき,友達がきたら各人に連続するいくつかのピースを渡していく.各人のもらうケーキの量は平等でなければならない(ピースの数は同じでなくてもいいが長さの和は同じでなければならない).ただし友達が何人来るかは不明で,人数はnでないnの約数であることしかわからない.このとき何人だったとしても平等にわけられるためには最小で何個のピースに分割しておく必要があるか?という問題.

これは簡単.例えばn=6の場合,友達の人数は1,2,3人があり得るがこのときケーキを2等分,3等分する位置でそれぞれきっておけばいい.ただし2等分と4等分など等分点が被ることがあるのでそこを重複しないように気をつける.単純にsetで数えるとnの約数の和をf(n)としたとき計算量f(n)*log(n)で出来て間に合った(どれくらいのオーダーか真面目にかんがえてない).

SRM618 Div1E Family

DAG(閉路のない有向グラフ)で

・頂点iから頂点jへの辺があるときi<j(つまりトポロジカル順序で番号が振られている)

・各頂点の入次数は0または2

であるようなグラフGが与えられる.各頂点に0または1を割り振って,入次数0でない各頂点の2つの親(その頂点への辺がある頂点)に割り振られた値が異なるように出来るか?という問題.

二部グラフ判定みたいなノリ.入次数2の頂点を適当に選んで(まだ割り振る値が決まっていなければ)2つの親に0,1を割り振る.そうするとこれによって他の頂点に割り振るべき値も順次決まっていくのでDFSなどで決めていき,矛盾が生じなければOK.