全国統一プログラミング王決定戦本戦 D - Deforestation 解説
感想
本戦は4完で157位でした。
もっと頑張りたかった……
思考過程
- こういう場合は、視点を逆にすると良い。つまり、「各操作について、どこの竹を刈り取って何ポイント獲得するか」と考えるのではなくて、「各竹について、どの操作によってポイントを獲得できているのか」と考える。
- そこで各竹ごとに考えると、要するに最後に刈り取った時間が大事なのだと気づく。
- よって、操作するたびに、操作した竹に「何回目の操作か」を意味する番号を振っていき、最後に竹ごとにみるときにその最大値を取り出して計算する。
実装その１
- 範囲に関する操作を行う問題なので、（計算量を減らすために）セグメント木を使おうと（本戦中は）思った。
１回目の操作で２番目から４番目、２回目の操作で１番目から７番目の竹を刈り取ったとすると、
１回目の操作では[2-3],[4-4]、２回目の操作では[1-1][2-3][4-7]のノードが、それぞれ１と２に更新される。
（※[a-b] := a以上b以下の竹）
- 全操作が終わったときに、各竹について「何回目の操作か」を意味する番号の最大値を求める。
例えば３番目の竹について求めるときだったら、[0-7][0-3][2-3][3-3]のうち、もっとも大きい値を取り出す。
（ちなみに、今回最大値のみを取り出せばよいので、「操作を後ろから行っていき、すでに番号を振ったところはスルーする」という方法でやろうかとも思ったけど難しそうなのでやめた。）
ll segtree[800005]; ll segn; void seginit(ll n_){ segn = 1; while(segn < n_)segn *= 2; for(int i=0;i<2*segn-1;i++)segtree[i] = -1; } void paint(ll a,ll b,ll k,ll l,ll r,ll times){ //a以上b未満の範囲に、timesの値を更新する if(r <= a || b <= l){ //ノードがa以上b未満の範囲と重ならない場合 return; } if(a <= l && r <= b){ //ノードがa以上b未満の範囲にすっぽり含まれる場合 segtree[k] = times; return; }else{ //以上のどちらでもない場合 paint(a,b,k * 2 + 1,l ,(l + r) / 2,times); paint(a,b,k *+ 2 + 2,(l + r )/2 ,r,times); return; } } ll query(ll a,ll k,ll l,ll r){ //aを含む部分についてのクエリ //k番目のノードの範囲がl以上r未満 if(r <= a || a < l){ //aを含まない場合 //不適なので、負の無限大を返すことにする return -INF; } if(a == l && r == a + 1){ //aを含み、それ以上分割できない範囲の場合 return segtree[k]; }else{ //aを含む、ある程度長い範囲の場合 //最大値を返すことに注意 ll one = query(a,k * 2 + 1,l ,(l + r) / 2); ll two = query(a,k *+ 2 + 2,(l + r )/2 ,r); ll three = segtree[k]; one = max(one,two); return max(one,three); } } int main(){ cin >> n >> m; for(i=0;i<m;i++){ cin >> t[i] >> l[i] >> r[i]; } seginit(n+5); for(i=0;i<m;i++){ //0-indexedにするために１ずつ引いている paint(l[i] - 1,r[i],0, 0, segn,i); } ans = 0; for(i=0;i<n;i++){ a = query(i,0,0,segn); if(a == -1)continue; ans += t[a]; } p(ans); return 0; }
