かっつのメモ帳

主に競プロ　時々日記

TCO20 Round 3A Easy RectangularObstacle

競プロ SRM

問題概要

始め頂点(0,0)にいる。1回の操作で隣接する格子点を1つ選んで移動することができる。ただし、 x_1 \leqq x \leqq x_2 かつ y_1 \leqq y \leqq y_2 を満たす範囲には障害物があり移動することが出来ない。 S 回以内の操作で到達可能な格子点の総数を求めよ。

制約

  • -10^{6} \leqq x_1 \leqq 0 \leqq x_2 \leqq 10^{6}

  • 1 \leqq y_1 \leqq y_2 \leqq 10^{6}

  • 0 \leqq S \leqq 10^{9}

解法

まず障害物が無い時を考える。この時、黒の菱形部分が到達可能範囲である。

f:id:KKT89:20200802041035p:plain
雑な図

この範囲にある格子点の数は容易に求めることが出来て、

\frac{1}{2}(2S+1+1)(2S+1)\times 2 - (2S+1)=(S+1)^{2}-(2S+1)

となる。後ろの (2S+1) は y=0 での重複分である。

次に障害物ありの場合を考える.。制約より y \leqq 0 の部分は影響を受けないので正の部分だけ考えれば良い.。

重要なポイントとして、 -s \leqq x \lt x_1 , x_2 \lt x \leqq s の範囲における格子点は障害物の影響を受けずに到達可能である。

従って、 x_1 \leqq x \leqq x_2 の範囲を探索し、障害物の影響で到達出来なくなった頂点を引いていけば答えが得られる。

注意するのは長方形の左右から回り込んで長方形より上の頂点に到達する場合で、この時は右回りのコストと左回りのコストを比較してその x における到達可能な頂点のy座標の範囲を求める。

f:id:KKT89:20200802043204p:plain

実装

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;

class RectangularObstacle {
  public:
  long long countReachable(ll x1, ll x2, ll y1, ll y2, ll s) {
    ll res=2*(s+1)*(s+1)-(2*s+1);
    for(ll x=x1;x<=x2;x++){
      if(abs(x)>s)continue;
      ll t=s-abs(x); //長方形が無かった時に到達可能なy座標の最大値
      if(t<y1)continue;
      if(t<=y2){
        res-=(t-y1+1);
      }
      else{
        res-=(y2-y1+1);
        ll cost=min(abs(x1)+y2+2+abs(x-x1),abs(x2)+y2+2+abs(x-x2));
        ll can=max(0LL,s-cost);
        ll no=t-y2; // 元々到達可能で長方形の上側にある頂点数
        can=min(can,no);
        res-=(no-can);
      }
    }
    return res;
  }
};