二分探索の上限をinfにするのは危険 D - Jumping Takahashi 2 

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;
    
    VI X(N);
    VI Y(N);
    VI P(N);
    rep(i,N){
      cin>>X[i]>>Y[i]>>P[i];
    }

    auto L1 = [&](ll i, ll j){
      return abs(X[i]-X[j]) + abs(Y[i]-Y[j]);
    };

    auto f = [&](ll start, ll S){
      queue<ll> q; q.push(start);
      set<ll> not_visited;
      rep(i,N){
        if(i!=start)not_visited.insert(i);
      }
      while(q.size()){
        ll a = q.front(); q.pop();
        VI del_list;
        for(ll to : not_visited){
          if(P[a]*S >= L1(a,to)){ // ★
            q.push(to);
            del_list.push_back(to);
          }
        }
        for(ll idx : del_list){
          not_visited.erase(idx);
        }
      }
      return SZ(not_visited)==0;
    };

    ll left=0; // can't
    ll right=1e15; // can
    while(right-left>1){
      ll center=(right+left)/2;

      bool can=false;
      rep(i,N){
        if(can)break;
        bool result = f(i,center);
        if(result){
          can=true;
        }
      }

      if(can){
        right=center;
      }else{
        left=center;
      }
    }
    p(right);

    return 0;
}
  • 雑にleft=0, right=1e15としていたが、辺を張れるかの判定条件（★の箇所）でoverflowしていた
  • 入力の値域から、right=4*1e9で十分なので、そう変更すればACする

Holes (English Edition)

Holes (English Edition)

Amazon

long doubleのsqrtはdouble版より10倍遅い 

実行時間
long double 122ms
float 12ms
double 8ms
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll D;cin>>D;

    ld d = sqrtl(D);

    ll mi=inf;
    rep(x,1e7){
      if(x>=d)break;

      ld y = sqrtl(D-x*x);

      ll y0 = floorl(y);
      ll y1 = ceill(y);

      ll v0 = abs(x*x + y0*y0 - D);
      chmin(mi,v0);
      
      ll v1 = abs(x*x + y1*y1 - D);
      chmin(mi,v1);
   }
    p(mi);
    
    return 0;
}
  • 122msはlong doubleのsqrtを106回程度回した時の時間なので、1回当たりは十分に速い
  • とはいえ、AHCの焼きなましで可能な限り回したい（高速化したい）などの時は、doubleに落とすのは全然ありだろう

MEXをset<int>から二分探索しようとして失敗した E - Mex and Update

問題

https://atcoder.jp/contests/abc330/tasks/abc330_e

考察 (WA)

  • 1個以上存在する値をsetで管理して、そこからMEXを高速に求めればいいな
  • set内はソートされているのだから二分探索できるだろう
  • ということで下記のようなsetを入力としてMEXを返す関数を書いて提出→TLE
using ll = long long;
ll find_mex(set<ll>& se){
  if(se.count(0)==0)return 0;
  ll left=0; // ここまでは値が詰まっている (0,1,2,...)
  ll right=se.size(); // ここまで詰まっていることはない
  while(right-left>1){
    ll center = (left+right)/2;
    auto it = se.lower_bound(center);
    if(it!=se.end() && *it==center && distance(se.begin(),it)==center){
      left=center;
    }else{
      right=center;
    }
  }
  return right;
}

AC

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,Q;
    cin>>N>>Q;

    map<ll,ll> mp;
    VI A(N);
    rep(i,N){
      ll a;cin>>a;
      A[i]=a;
      mp[a]++;
    }

    set<ll> se;
    rep(i,200200){
      if(mp[i]==0)se.insert(i);
    }

    rep(_,Q){
      ll i,x;cin>>i>>x;i--;
      if(A[i]!=x){
        // 減らす
        ll prev = A[i];
        mp[prev]--;
        if(mp[prev]==0)se.insert(prev);

        // 増やす
        A[i]=x;
        mp[x]++;
        if(mp[x]==1){
          se.erase(x);
        }
      }
      ll mex = *se.begin();
      p(mex);
    }

    return 0;
}

ダイクストラ 復元 注意点 prev 

struct Node{
  ll distance;
  ll index;
  ll prev=-1;
};

// ダイクストラアルゴリズム内部
{ // 省略
        while(!que.empty()){
            // 1番distanceが小さいノード
            Node n = que.top();que.pop();
 
            if(done[n.index])continue;
            
            // 確定
            done[n.index] = true;
            d[n.index] = n.distance;
            prev[n.index] = n.prev; // ここでprevを上書きすべき★1
 
            auto edge_list = graph[n.index];
            for(auto edge : edge_list){   
                // 短くなるノードがあれば
                if(!done[edge.to] && n.distance + edge.cost < d[edge.to]){
                    ll shorter_distance = n.distance + edge.cost;
                    que.push(Node(shorter_distance, edge.to, n.index));
                    // prev[edge.to] = n.index; // ここに書いてもバグります★2
                }
            }
        }
}
  • 具体的には★1の箇所でprevに入力しなければならなかった
  • 最初、★2のところでprevを書き換えたがそれはミス。edge.toの距離が3のものをpush, edge.toの距離が4のものをpush, とした場合、距離4の方でprevが上書きされてしまうため

追記：2024/01/06

  • 距離の更新をどこでやるかにもよる
    • que.pop()した直後で確定させるなら、★1でprevを書き換えるべき
    • for内でdも更新していくなら、★2でprevを書き換えても構わない。というか、こちらの形式(for内でd更新)の人が多いことを知った

(自分用メモ) 論理式の式変形 (和をXOR, ANDで書き直す)