2019年12月25日水曜日

ARC 032 - 仕事計画

ARC 032 - 仕事計画

辞書式順序の条件を無視すればただの区間スケジューリングなので、始点aia_iでソートして逆から貪欲に選んでいけば仕事の数の最大数kkが求まる。この際に得られた仕事の列が開始から

(a1,b1),(a2b2),...,(ak,bk)(a'_1, b'_1), (a'_2 b'_2), ..., (a'_k, b'_k)

となっているとする。このとき、次の性質があることに注目する:

  • k1k-1個の仕事をこなすためには、少なくともa2a'_2までには始めなければならないし、a2a'_2までに始めればk1k-1個の仕事が可能である
  • k2k-2個の仕事をこなすためには、少なくともa3a'_3までには始めなければならないし、a3a'_3までに始めればk2k-2個の仕事が可能である
  • 11個の仕事をこなすためには、少なくともaka'_kまでには始めなければならないし、aka'_kまでに始めれば11個の仕事が可能である

これらの性質から、kk個の仕事からなる辞書順最小のスケジュールを構成する方法が従う:

  • 11個目の仕事はa2a'_2までに終わるものならなんでも可能である。このうちインデックスが最小のものを(l1,r1)(l_1, r_1)とする。
  • 22個目の仕事はr1r_1以降に始まってa3a'_3までに終わるものならなんでも可能である。このうちインデックスが最小のものを(l2,r2)(l_2, r_2)とする。
  • kk個めの仕事はrk1r_{k-1}以降に始まるものならなんでも可能である。このうちインデックスが最小のものを(lk,rk)(l_k, r_k)とする。

こうして辞書順最小のスケジュール(l1,r1),...,(lk,rk)(l_1, r_1), ..., (l_k, r_k)が得られた……わけだが、実際にこのスケジュールを求める手順がまだ明らかでない。

時間xxに始まってyyに終わる仕事のインデックスをf(x,y)f(x, y)とするとき(複数ある場合、インデックスが最小のもの以外は捨ててよい)、仕事は二次元空間上の点とみなせるので、上の性質をさらに言い換えられる:

  • [0,a2]×[0,a2][0, a'_2] \times [0, a'_2]上にある仕事についてf(x,y)f(x, y)の最小値を求める。(l1,r1)(l_1, r_1)で最小になるとする。
  • [r1,a3]×[r1,a3][r_1, a'_3] \times [r_1, a'_3]上にある仕事についてf(x,y)f(x, y)の最小値を求める。(l2,r2)(l_2, r_2)で最小になるとする。
  • [rk1,+]×[rk1,+][r_{k-1}, +\infty] \times [r_{k-1}, +\infty]上にある仕事についてf(x,y)f(x, y)の最小値を求める。(lk,rk)(l_k, r_k)で最小になるとする。

ここまで整理すると、min\minを乗せたrange treeで実行できる手順になっている。計算量はO(Nlog2N){\mathcal O}(N \log^2 N)


線形で求まるのは、手順を示されれば確かにとなるけどまったくわからなかった。

今出題されたら、もう少し制約が大きくなってlog2\log^2は落ちる気がする。この方針のままでも、2D range tree + fractional cascading + 構築O(N){\mathcal O}(N)クエリO(1){\mathcal O}(1)のRMQでlog\logを1つにできそう? でも、そもそも平面走査的になんとかできないのかな。

2019年12月21日土曜日

CODE FESTIVAL 2015 E - ショートコーディング

CODE FESTIVAL 2015 E - ショートコーディング

次の3つの変形を適用していく:

  • !!!= !!!! = \ !
  • = id-- = \ \operatorname{id}
  • != !!- = \ !

このとき、可能な解は!!,!,id,!!,!,!!, !, \operatorname{id}, -!!, -!, -の6つしかないことがわかる。

2019年12月16日月曜日

WUPC 2019 C - Choose Your Characters

WUPC 2019 C - Choose Your Characters

勝てない相手キャラがいないような最短の区間を尺取り法で求める。つまり、dp[i]:=dp[i] :=キャラiiが勝てるキャラの数、を00で初期化し、各区間について正しいdpdpを求めて、minidp[i]>0\min_i dp[i] >0になるような最短の区間を探せばよい。

具体的には、最初に

S(i):=S(i) :=キャラiiが勝てないキャラの集合(同キャラ含む)

を作っておく。区間を伸ばすときにはdpdp全体に1を足してから各kS(i)k \in S(i)についてdp[k]=1dp[k] -= 1とし、区間を縮めるときにはdpdp全体から1を引いてから各kS(i)k \in S(i)についてdp[k]+=1dp[k] += 1とする。dpdpにセグメント木等を使えば間に合う。


ようやく尺取り法の間違えにくい書き方にたどり着いたのでメモ。

  • ok関数とng関数で相互再帰する。
  • 常に半開区間[l,r)[l, r)を扱う。(ok l r)[l,r)[l, r)が条件を満たすときに呼び出され、(ng l r)[l,r)[l, r)が条件を満たさないときに呼ばれる。rはこれから追加される位置であり、lはこれから除去される位置である。
  • (ok l r value)のように区間に関する値を受け渡す場合は、valueが区間[l,r)[l ,r)に対応する値になるように注意する。
  • 最適値はok関数の冒頭で更新する。

2019年12月9日月曜日

JOI2018 本戦 B - 美術展

JOI2018 本戦 B - 美術展

最初からA1A2...ANA_1 \le A_2 \le ... \le A_Nであると仮定してよい。この場合、大きさの最大と最小が決まっていればその範囲にある美術品はすべて展示したほうが得なので、美術品の連続部分列だけ考えればすむ。

美術品iiを展示しているとき、さらにi+1i+1を展示すると得点はBi+1(Ai+1Ai)B_{i+1}-(A_{i+1}-A_i)だけ増えることに注目してDPする。dp[i]:=idp[i] := iまで展示するとした時の最大得点、とすると

dp[i]=max(dp[i1]+Bi(AiAi1),Bi)dp[i] = \max(dp[i-1] + B_{i}-(A_i-A_{i-1}), B_{i})

答えはmaxi[N]dp[i]\max_{i \in [N]} dp[i]


いわゆるKadane’s algorithmっぽい感じなんだけど、なぜかそれをそのまま書いてしまってWAした。

2019年12月2日月曜日

JOI2010 春合宿 - Stairs

JOI2010 春合宿 - Stairs

xx段目の地面からの高さをHxH_xとし、xx段目までの上り方の総数をf(x)f(x)とする。HlHxPH_l \ge H_x - Pとなるような最小の段をll段目とするとき、ffの漸化式は

f(x)=t[l,x)f(t)f(x) = \sum_{t \in [l, x)}f(t)

と書ける。このままDPすると間に合わないので累積和S(x):=t=0xf(t)S(x) := \sum_{t=0}^xf(t)を考える。

f(x)=S(x1)S(l1)f(x) = S(x-1) - S(l-1)

S(x)=f(x)+S(x1)S(x) = f(x) + S(x-1)

が成り立つから、SSの漸化式は

S(x)=2S(x1)S(l1)S(x) = 2S(x-1) - S(l-1)

とまとまる。SSに関してDPすればよい。答えはf(N)=S(N)S(N1)f(N) = S(N)-S(N-1)である。

毎回llを二分探索で求めると計算量はO(NlogN){\mathcal O}(N\log N)。尺取り法でO(N){\mathcal O}(N)