ACL 遅延セグ木を二分探索 min_left, max_right

Skyscraper

  • 問題 https://jonathanirvin.gs/files/division2_3d16774b0423.pdf
  • 自分の高さまで遠くを見ることができる
  • クエリとして
    • 1「建物iから見える建物の数を答える」
    • 2「範囲で高さ更新」
    • 3「単体の高さ更新」
    • というのが飛んでくる
  • O(Q log(N) log(N))で書いたらTLEしたため、min_left, max_rightが必要になった

f:id:peroon:20210210143724p:plain

input

8 6
4 2 3 2 4 7 6 5
1 3
1 2
2 3 8
1 5
3 5 7 1
1 8

output

3
1
2
5

input, output コメントつき

// input
8 6
4 2 3 2 4 7 6 5

// クエリ
1 3 // 建物3から見える建物の数は？
1 2
2 3 8 // 建物3の高さを8にする
1 5
3 5 7 1 // 建物5~7の高さを1にする
1 8

// output
3
1
2
5

全てのクエリを終えた時の建物の状態

f:id:peroon:20211026011640p:plain

AC code

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
    #define __clock__
#else
    #pragma GCC optimize("Ofast")
#endif
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;
using PII = pair<ll, ll>;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<'\n'
#define p2(s, t) cout << (s) << " " << (t) << '\n'
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << '\n'
#define SZ(x) ((int)(x).size())
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(ALL(A), greater<ll>())

const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e18;
const double PI = acos(-1);

#include <atcoder/lazysegtree>
using namespace atcoder; // 忘れがち

using S = long long;
using F = long long;

const S INF = 8e18;
const F ID = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF; }
S mapping(F f, S x){ return (f == ID ? x : f); }
F composition(F f, F g){ return (f == ID ? g : f); }
F id(){ return ID; }

// min_left, max_right用
ll global_h;
bool g(S x){
  return x <= global_h;
}

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

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

    // 範囲更新、範囲MAXの遅延セグ木
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);

    while(Q--){
      ll ty;cin>>ty;
      if(ty==1){
        // print
        ll i;cin>>i;i--;
        ll h = seg.get(i);

        // この素朴な二分探索では クエリごとに O(log(N) log(N))となってしまい、TLEします（まず素朴解法でWAではないことを確認）
        // ll cnt=1;
        // 左にいくつ見える？
        // ll ma = seg.prod(0,i);
        // if(ma<=h){
        //   // 全部見える
        //   cnt += i;
        // }else{
        //   // 二分探索必要
        //   ll left=0; // can't
        //   ll right=i; // can
        //   while(left+1!=right){
        //     ll center = (left+right)/2;
        //     if(seg.prod(center,i+1)<=h){
        //       right=center;
        //     }else{
        //       left=center;
        //     }
        //   }
        //   cnt += i-right;
        // }
        // 右にいくつ見える？
        // ma = seg.prod(i,N);
        // if(ma<=h){
        //   // 全部見える
        //   cnt += N-i-1;
        // }else{
        //   ll left=i; // can
        //   ll right=N; // can't
        //   while(left+1!=right){
        //     ll center = (left+right)/2;
        //     if(seg.prod(i,center+1)<=h){
        //       left=center;
        //     }else{
        //       right=center;
        //     }
        //   }
        //   cnt += left-i;
        // }

        // セグ木内の二分探索により、クエリごとにO(log(N))となり、ACします
        global_h = h; // 関数g用
        ll r = seg.max_right<g>(i); // iより右でどこまで見えるか
        ll l = seg.min_left<g>(i); // iより左でどこまで見えるか
        ll cnt = r-l;
        p(cnt);
      }
      else if(ty==2){
        // set height
        ll i;cin>>i;i--;
        ll h;cin>>h;
        seg.set(i,h);
      }
      else{
        // range update
        ll i,j,h;cin>>i>>j>>h;
        i--;j--;
        seg.apply(i,j+1,h);
      }
    }

    return 0;
}

Quora Programming Challenge 2021

公式サイト

全体の印象

  • 部分点がある
  • 最初の1問はやるだけ実装問題
  • 次に、いくつかの競プロ的問題
  • 最後にML(Machine Learning)問題がセットごとに2つあり、統計を使う

反省点

  • コンテストサイトからは順位表情報が見えないが、Quora上では「開始から1時間経過後のランキング」などが公開されていたのでそれを見て通しやすい問題を見極めればよかった
  • まずすべての問題に目を通す
  • ML問題はマラソン的なので試行錯誤の時間が必要で、ML以外をどれだけ速く片付けられるかが大事そう

レベル感

  • 各回500人ほど参加、水色の私でギリギリ50位になれない所まで行けたので、青以上なら50位以内に行けてTシャツGETできそう

問題文

結果 (full ranking)

他サイト

Div1

  • digest
    • 記事を誰にリコメンドするかという実装問題
  • escape
    • H=1000, W=1000程度のグリッドに壁と平地、始点終点、いくつかの監視員(x,y,r(監視範囲))が与えられる
    • 最短でゴールに行くために必要な距離は？(or print IMPOSSIBLE)
    • bfsを監視員分回すとTLEする
    • kusanoさんのblogによると「移動範囲の広いガードは先に、狭いガードは後に時間差で置いていき」なるほど！
    • multisource bfs (&時間差) って感じかな
  • Students
    • H=3000, W=3000のグリッドに生徒がいて、上下左右は仲良しなこともある（与えられる）
    • 仲良しは含まれないように最大何人選べるか？という問題
    • 連結成分ごとに見て、最大安定集合分選べそう。YES, 二部グラフを意識して辺をはってフローで一発

f:id:peroon:20210209093326p:plain

  • Walls
    • 人と壁が与えられる。全人を連結させるために必要な壁の破壊コストの最小値を求めよ
    • MSTではダメ。どうするんだ？シュタイナー木？Strong connectivity augmentation?
    • （順位表を見てパスすべき問題だったらしい）
  • Tourism
    • 木上を旅行する。頂点ごとにお金を貰う。辺でお金を支払う。最初に持っておくべきお金の最小値は？
    • 典型っぽいが... HLD?
  • (ML)Flipped Data
    • N個の特徴ベクトルのうちb個をflipしてしまった。それを見つけよという問題。b個は40%以下になるという制約がある
    • 平均と分散を求めておいて正規化し、平均からの逸脱度が高いものを選べば良さそう
  • (ML)Identifying Spammers
    • Spammer or notの0/1判定機械学習問題
    • 人ごとに、「訪れたページ：その時間」の組がいくつか与えられる
    • 時系列データ機械学習？
  • 428点なら50位

Div2

  • Connect4
    • ゲームの勝敗を判定する関数の実装
    • 制約も小さく、やるだけ
  • Treasure
    • DPだが、各マスに保持する場合の数は最大値のものだけでいいことに気づけばいい
    • dp[i][j] 場所(i,j)に最大値で到る場合の数
  • Data Center
    • どのビルをデータセンターにすればいいか？
    • チェビシェフ距離なので45度回転してマンハッタン距離にしてx,y分離し、x,yそれぞれ別々に解けるそう (チェビシェフとマンハッタンは45度回転で可換)

  • (ML)Broken Message
    • 各値の前後に出る値の統計をとっておく
    • 前も後ろも統計が使えるなら、2つの統計値を「掛け算」して判定する（確率で考えるとそうなる）。これで69点取れた
  • (ML)Malicious Data 
from scipy.stats import multivariate_normal # 多変量正規分布
...
# それに沿った乱数データを生成し、probabilityが低いものをfakeとして採用しているっぽい。これは慣れてないと厳しい...
for i in range(10000):
    a,b,c = np.random.uniform(-3,3),np.random.uniform(0,3),np.random.uniform(-3,3)
    if multivariate_normal.pdf([a,b,c], mean, cov) < 0.00089:
        X_fake.append((a,b,c))
assert len(X_fake) > 1000
X_fake = X_fake[:1000]

  • 387点なら50位

B - Big Integers

f:id:peroon:20210208213028j:plain

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

    // input
    ll N,M,K;
    cin>>N>>M>>K;

    ll ma = max(N,M);

    VI A;
    rep(i,ma-N)A.push_back(0);

    VI B;
    rep(i,ma-M)B.push_back(0);

    rep(i,N){
      ll a;cin>>a;
      A.push_back(a);
    }

    rep(i,M){
      ll b;cin>>b;
      B.push_back(b);
    }

    // 終了関数
    auto x = [](){
      p("X");exit(0);
    };
    auto y = [](){
      p("Y");exit(0);
    };

    rep(i,ma){
      if(A[i]>B[i])y();
      if(A[i]<B[i])x();
    }
    p("Same");
   
    return 0;
}

01BFSクラスで解く、器物破壊高橋君

ライブラリ 
struct ZeroOneBFS{
  ll H,W;
  VS S;
  VV d; // distance

  const int dx[4] = {-1, 0, 1,  0};
  const int dy[4] = { 0, 1, 0, -1};

  bool in_range(ll i, ll j){
    if(0<=i && i<H && 0<=j && j<W){
      return true;
    }else{
      return false;
    }
  }

  ZeroOneBFS(VS _S){
    S = _S;
    H = S.size();
    W = S[0].size();
    d.resize(H, VI(W,-1));
  }

  // その文字を1つ見つけて場所を返す(y,x)
  PII search(char c){
    rep(i,H){
      rep(j,W){
        if(S[i][j]==c)return PII(i,j);
      }
    }
    debug("not found");return PII(-1,-1);
  }

  // 文字（地図）更新
  void update(ll y, ll x, char c){
    S[y][x] = c;
  }
  void update(PII pos, char c){
    update(pos.first, pos.second, c);
  }

  void debug_print(){
    rep(i,H){
      debug(d[i]);
    }
  }

  // start位置から01bfs
  void calc(PII start){
    deque<PII> que;
    que.push_back(start);
    d[start.first][start.second]=0;

    while(!que.empty()){
      PII a = que.front(); que.pop_front();
      ll y=a.first;
      ll x=a.second;
      // 上下左右を見る
      rep(i,4){
        ll ny = y + dy[i];
        ll nx = x + dx[i];
        if(!in_range(ny,nx))continue;
        if(d[ny][nx]!=-1)continue;
        if(S[ny][nx]=='.'){
          d[ny][nx] = d[y][x];
          que.push_front({ny,nx}); // 前に入れる
        }else{
          d[ny][nx] = d[y][x]+1;
          que.push_back({ny,nx}); // 後に入れる
        }
      }
    }
  }

  ll distance(PII pos){
    return d[pos.first][pos.second];
  }
};

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

    // input
    ll H,W;cin>>H>>W;
    VS S(H);
    rep(i,H)cin>>S[i];

    auto bfs = ZeroOneBFS(S);
    auto start = bfs.search('s');
    auto goal = bfs.search('g');
    bfs.update(start,'.');
    bfs.update(goal,'.');
    bfs.calc(start);
    if(bfs.distance(goal)<=2)yes();
    no();
    
    return 0;
}

全ての都市をそれぞれ1回は訪れる最小コスト（始点と終点は違ってよい, bit DP）を関数化した

ライブラリ 
// G 距離行列
// G[i][j]==-1なら道なしとする
// グラフが連結であるかどうか
bool is_connected(VV& G){
  ll N = G.size();
  dsu uf(N);
  rep(i,N){
    FOR(j,i+1,N){
      if(G[i][j]>=0)uf.merge(i,j);
    }
  }
  return uf.groups().size()==1;
}

// 全ての都市（頂点）をそれぞれ1度は訪れるための最小移動距離（始点に戻る必要なし）
// G : 距離行列 (-1なら道なしとする)
// (N : 頂点数)
// bitDPを使うので計算量 N^2 x 2^N
// 到達不可能ならinfを返します
ll visit_all_city(VV& G){
  if(!is_connected(G)){
    debug("グラフが連結でないので全てを訪れることはできません");
    return inf;
  }
  ll N = G.size();
  // dp[i][j]
  // i : 訪れた都市のフラグ
  // j : 現在位置
  VV dp(1LL<<N, VI(N, -1)); // -1 : not assigned yet

  // メモ化再帰
  // f : 現在訪れた箇所はフラグ1とした訪問状態
  // now : 現在地
  function<ll(ll,ll)> rec = [&](ll f, ll now){
    if(dp[f][now]!=-1) return dp[f][now];
    // 次、どこに行こうかな
    ll mi = inf;
    rep(i, N){
      if(f>>i&1)continue; // already visited
      if(G[now][i]==-1)continue; // 道なし
      ll d = G[now][i] + rec(f|1LL<<i, i);
      chmin(mi, d);
    }
    return dp[f][now] = mi;
  };

  // 全てを訪れたならそこからの移動距離は0
  ll all = (1LL<<N)-1;
  rep(i,N){
    dp[all][i]=0;
  }
  ll mi = inf;
  rep(i,N){
    chmin(mi, rec(1LL<<i, i));
  }
  return mi;
}