perogram

Range Mindex Query (最小値とindexのペアを返すセグメント木)

Quiz

https://yukicoder.me/problems/no/875

AC code

https://yukicoder.me/submissions/442780

補足

  • クエリに答えるときに、min値を持つ場所のindexを返す必要がある
  • だから min + index = mindex というタイトルなのだろう
  • 遅延なしSegTreeは書いたことがあったのでそれをコピーしてきて、値だけ持っていた場所を(値, index)のペアに書き換えた
  • 思った以上に書き換えがすぐ終わった。やはり自作ライブラリは手を入れやすい

mindex segment tree

// range min, and index (range Mindex)
struct SegmentTree{
    vector<PII> A;
    ll N; // node num
 
    // 初期化
    SegmentTree(ll size){
        N = _powerOfTwo(size); //2べき
        auto initial_value = MP((1LL<<31)-1LL, -1);
        A.resize(N * 2, initial_value); // 木なので2倍必要
    }

    void update(ll i, ll x){
        int index = N + i - 1; // 葉のインデックス
        A[index].first = x;
        A[index].second = i;
        // 親にも反映
        while(index > 0){
            PII min0 = A[index];
            PII min1;
            if(index%2==0){
                min1 = A[index-1];
            }else{
                min1 = A[index+1];
            }

            ll parent = (index-1) / 2;
            A[parent] = min(min0, min1);
            index = parent;
        }
    }

    bool is_power_of_two(ll v){
        return !(v & (v-1));
    }
 
    // 引数以上の2のべき乗 5=>8
    ll _powerOfTwo(int n){
        ll ret = 1;
        while(ret < n){
            ret *= 2;
        }
        return ret;
    }
 
    // 区間[a,b)の総和。ノードk = [l,r) に着目している
    PII _rangeMin(int a, int b, int k, int l, int r){
        // 重ならない
        if(r <= a || b <= l){
            return MP(inf, -1);
        }
        // 内包する
        else if(a <= l && r <= b){
            return A[k];
        }
        // 重なる部分もある
        else{
            ll center = (l+r) / 2;
            // 左下の子
            auto min0 = _rangeMin(a, b, 2*k+1, l, center);
            // 右下の子
            auto min1 = _rangeMin(a, b, 2*k+2, center, r);
            return min(min0, min1);
        }
    }
 
    // [a, b) までのmin
    // 半開区間
    PII RangeMin(int a, int b){
        return _rangeMin(a, b, 0, 0, N);
    }
};

解答コード(抜粋)

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

    // input
    ll N,Q;cin>>N>>Q;
    VI A(N);
    rep(i,N)cin>>A[i];

    auto seg = SegmentTree(N);
    rep(i,N){
      seg.update(i, A[i]);
    }

    while(Q--){
      ll ty;cin>>ty;
      ll l,r;cin>>l>>r;
      l--;r--;
      if(ty==1){
        // swap
        ll a = seg.RangeMin(l, l+1).first;
        ll b = seg.RangeMin(r, r+1).first;
        seg.update(l, b);
        seg.update(r, a);
      }
      else{
        // print
        PII a = seg.RangeMin(l, r+1);
        p(a.second+1);
      }
    }
    
    return 0;
}

No.999 てん vs. ほむ

Quiz

https://yukicoder.me/problems/no/999

公式解説

https://yukicoder.me/problems/no/999/editorial

私の解説

  • 累積和を使わなかったので書いておく
  • ほむちゃんが左から攻める領域と、右から攻める領域は2つは左右に分割されるので、切れ目を全探索。各切れ目ごとに得点を求めてmaxをとっていけばいい

例:サンプル3

f:id:peroon:20200311052236p:plain

code 抜粋

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

    // input
    ll N; 
    cin>>N;

    VI A(2*N);
    rep(i, 2*N) cin >> A[i];

    // 左から取った場合のほむちゃんのスコア
    VI V;
    for(int i=0; i<2*N; i+=2){
      ll a = A[i];
      ll b = A[i+1];
      V.push_back(a-b);
    }

    ll sum = SUM(V);
    ll ma = sum;

    for(int i=N-1; i>=0; i--){
      // i番目を右から取った場合に変更する
      sum -= 2*V[i];
      chmax(ma, sum);
    }
    p(ma);
    
    return 0;
}

Zアルゴリズムを使って文字列sから文字列tを見つける

Quiz

No.1005 BOT対策 https://yukicoder.me/problems/no/1005

AC code

https://yukicoder.me/submissions/442411

説明

  • 別解でO(N)で解ける方法としてZアルゴリズムが挙げられている
    • 先頭とどれだけ一致するかが分かる
  • 使ったことが1度だけあるが、再度使って練習してみた
  • 文字列sから文字列tを探すとして、t+sをZアルゴリズムの入力とする
  • 具体例としてサンプルを使うと
// 入力
s = doyouknowsegmenttreeiknowsegmenttree
t = segmenttree

// 出力
2

// 補足
|t| = 11
Zアルゴリズムの出力で11以上のところにtが存在する
{
47, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
11, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 11, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 
0
}

f:id:peroon:20200311023251p:plain

  • tの長さである11以上の数字が現れた箇所にtが存在する
  • あとは解説通り、s内で見つけたtの右端にピリオドを打てばいい

code 抜粋

VI Z_algorithm(const string &S) {
    int N = (int)S.size();
    VI res(N);
    res[0] = N;
    int i = 1, j = 0;
    while (i < N) {
        while (i+j < N && S[j] == S[i+j]) ++j;
        res[i] = j;
        if (j == 0) {++i; continue;}
        int k = 1;
        while (i+k < N && k+res[k] < j) res[i+k] = res[k], ++k;
        i += k, j -= k;
    }
    return res;
}

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

    // input
    string s,t;cin>>s>>t;
    debug(s, s.size());
    debug(t, t.size());
    ll L = s.size();
    ll M = t.size();
    string u = t+s;
    VI A = Z_algorithm(u);
    debug(A);

    // 無理な場合があるとすればこれのみ
    if(M==1){
      bool exist = false;
      for(char c : s){
        if(c==t[0]) exist=true;
      }
      if(exist){
        p(-1);
      }else{
        p(0);
      }
      return 0;
    }

    set<ll> se;;
    for(int i=0; i<L; i++){
      if(A[i+M]>=M){
        // iで見つけた
        ll j = i+M-1; // 検索後の後端
        se.insert(j);
        i = i+M-2;
      }
    }

    // BOTに見つからない文字列を具体的に作るならこれ
    // rep(i, L){
    //   if(se.count(i)>0){
    //     cout << '.';
    //   }
    //   cout << s[i];
    // }
    // cout << endl;

    p(se.size());
    
    return 0;
}

Magic Bullet ~3次元幾何ライブラリを借りて~

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2641&lang=jp

AC code

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4239654#1

code抜粋

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

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

    // obstacles
    vector<Point3D> P(N);
    VI R(N);
    VI Magic(N);
    rep(i,N){
      cin>>P[i].x>>P[i].y>>P[i].z;
      cin>>R[i]>>Magic[i];
    }

    // queries
    while(Q--){
      Point3D a,b;
      cin>>a.x>>a.y>>a.z;
      cin>>b.x>>b.y>>b.z;

      // 線分と点の距離
      Segment3D seg(a,b);
      ll sum=0;
      rep(i,N){
        Point3D p = P[i];
        double distance = getDistanceSP(seg, p);
        if(distance<R[i]){
          sum += Magic[i];
        }else if(equals(distance, (double)R[i])){
          sum += Magic[i];
        }
      }
      p(sum);
    }

    return 0;
}

サンプル2

  • desmos.comでグラフを書いてみると接していて、その場合も魔力を消費するようだ
  • その場合のイコール判定は誤差に弱い。差がepsより小さい時はイコールと判定しよう

f:id:peroon:20200306231614p:plain

desmos用

// circle
\left(x-a\right)^{2}+\left(y-b\right)^{2}<r^{2}

// line
y-y_{1}=m\left(x-x_{1}\right)

その他

幾何・円の交点 (2次元)

Quiz

https://atcoder.jp/contests/abc157/tasks/abc157_f

AC code

解法

はまりどころ

  • epsを使わない場合の誤差
  • 円の交点だけでなく、円の中心も交点と同様にチェック点とする必要がある。なぜなら、

  • 二分探索でt=0は不可能とする都合上、これと矛盾するK==1のパターンは先に潰しておく必要
  • 円の交点コード自体のバグ(ライブラリを持っていれば安全性は上がる)

得たもの

  • 円の交点ライブラリ
  • complex<double>以外の点の構造体(V)

幾何ライブラリ(借りてくるときの候補として良さそう)

Bananas Multiplier (Easy/Hard)

Quiz

(hardも通る)解法

  • (0-indexedとする)
  • 頂点0からの最短距離(辺の本数)を各頂点について求める
  • 各頂点にたどり着いた時のcの積をそれぞれ求める。これは直前の点の値が分かればO(1)で求まるので、全体ではO(N)で求まる
    • メモ化再帰なり、dpなりで
  • 例えば下記画像で、頂点2~頂点5までの積を求めたいなら、「頂点0~5までの積」÷「頂点0~2までの積」で求まる
    • modの世界なので割り算は逆元で処理する

f:id:peroon:20200229194000p:plain

  • 画像のように、頂点aから頂点bに行くときに、頂点0を挟むかどうかの場合がある
  • LCAをlog(N)で求められるように前準備しておけば、除去する辺は求まる
  • 実は、どちらの場合であっても統一的に処理できる。下記コード参照
// 関数fは、頂点0からその頂点に行くまでのcの積とする

// クエリ処理
ll Q;cin>>Q;
while(Q--){
  ll a,b,banana;cin>>a>>b>>banana;
  a--;b--;

  ll lca = LCA(a,b);
  ll ans = banana * f(a) % mod * f(b) % mod;
  ans *= mod_pow(f(lca), mod-2); ans %= mod;
  ans *= mod_pow(f(lca), mod-2); ans %= mod;
  p(ans);
}

計算量

  • O(Q log(N) ) : クエリ数xLCAのコスト

要素

  • 最短距離
  • メモ化再帰 or DP
  • 逆元
  • LCA

JOIOJI

Quiz

https://atcoder.jp/contests/joisc2014/tasks/joisc2014_h

公式解説

https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d3-joioji-review.pdf

解説

f:id:peroon:20200226183025p:plain

  • サンプルの文字列に公式解説を適用するとこうなる
  • JO[i]==JO[j] かつ JI[i]==JI[j] の組の中で一番離れているものを見つければいい
  • 解説には「ソートして~」と書いてあるがここを補足しておく
  • 列ごとに構造体にする。例えば
struct Data{
  int jo;
  int ji;
  int index;
}
  • この構造体+比較関数を定義する
  • 比較関数で jo, ji, index の順に大小比較すれば、上記画像で言う黄色の"0, 1"はindexの順に並び、ソートにO(N logN), 最長距離はO(N)で求められる
  • 参考コード https://atcoder.jp/contests/joisc2014/submissions/8932147

学び

  • 累積和の移項
  • ソートを最適ペア探しに使う

追記:AC