perogram

F - Enclose All 参考リンクのみ cpp c++

Quiz

https://atcoder.jp/contests/abc151/tasks/abc151_f

参考

内容

  • 中心を平均などで適当に決め、一番遠い点の方に少し近づける調整を繰り返す
  • 計算量 O(N x R)
    • R : 繰り返し回数(求められる精度によって調整?)
int n;
double x[1005], y[1005], d, e;
double dist(double a, double b)
{
  return a * a + b * b;
}

int main()
{
  scanf("%d", &n);

  // center
  double X = 0;
  double Y = 0;
  for (int i = 0; i < n; i++)
  {
    scanf("%lf%lf", &x[i], &y[i]);
    X += x[i];
    Y += y[i];
  }
  X /= n;
  Y /= n;

  double P = 0.1;
  // 収束するまで繰り返す
  for (int i = 0; i < 30000; i++)
  {
    // 中心と点0の距離
    d = dist(X - x[0], Y - y[0]);

    int f = 0;
    // 中心と点0以外の距離
    for (int j = 1; j < n; j++)
    {
      e = dist(X - x[j], Y - y[j]);
      // 中心から一番離れている点を探す
      if (d < e)
      {
        d = e;
        f = j;
      }
    }
    X += (x[f] - X) * P;
    Y += (y[f] - Y) * P;
    P *= 0.999;
  }
  cout << setprecision(20);
  p(sqrt(d));
  // printf("%.3lf %.3lf\n%.3lf", X, Y, sqrt(d));
}

その他 O(N4)でたぶん解ける解法

B - Fusing Slimes 泥臭いエスパー解法

Quiz

https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b

AC

https://atcoder.jp/contests/dwacon6th-prelims/submissions/9431139

解法

  • N=5の場合の順列(4! = 24通り)を全て描いて観察する

f:id:peroon:20200112072126j:plain

  • 隣り合う丸の間(上記画像のアーチ)の本数を数える。すると、

f:id:peroon:20200112072712p:plain

  • (コンテスト中は24, 36, 44, 50を見て手が止まってしまった)
  • 上記画像のように分解して法則をエスパーすると、各アーチの本数が数えられ、解ける

Code

// a^b mod p
ll mod_pow(ll a, ll b){
    if(b==0) return 1;
 
    // 肩が奇数
    if(b%2==1){
        return a * mod_pow(a, b-1) % mod;
    }
    else{
        return mod_pow(a*a % mod, b/2) % mod;
    }
}

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

    // input
    ll N; 
    cin >> N;

    VI factorial(N+5, 0);
    factorial[0] = 1;
    factorial[1] = 1;
    FOR(i, 2, N+5){
      factorial[i] = factorial[i-1] * i % mod;
    }

    VI A(N);
    rep(i, N){
      cin >> A[i];
    }

    VI D;
    rep(i, N-1){
      ll d = A[i+1] - A[i];
      D.push_back(d);
    }

    ll sum = 0;
    ll F = factorial[N-1];
    ll a = 0;
    rep(i, N-1){

      // a += F/(i+1); // 割れない (modとってるから)
      a += F * mod_pow(i+1, mod-2); // 割る代わりに逆元
      
      a %= mod;
      sum += D[i] * a % mod;
      sum %= mod;
    }
    p(sum);

    return 0;
}

Problem D: Tunnel (立命館大学競技プログラミング合宿2019 Day2)

f:id:peroon:20200109125140j:plain

Quiz

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/D

問題意図のみ説明

f:id:peroon:20200109125604p:plain

  • 貪欲に(柱の角に向かって引く)取ればいいんじゃないの?と思ったが違った
  • 画像のように、柱の上辺を交差するように引くと合計が小さくなる

解法

立命館大学競技プログラミング合宿2019 問題と解説のリンク

立命館大学(理系−全学統一方式・学部個別配点方式、薬学方式) (2020年版大学入試シリーズ)

立命館大学(理系−全学統一方式・学部個別配点方式、薬学方式) (2020年版大学入試シリーズ)

  • 作者:
  • 出版社/メーカー: 教学社
  • 発売日: 2019/05/25
  • メディア: 単行本

Day 1 (立命館大学)

Day 2 (会津大学)

Day 3 (北海道大学)

私の取り組み方と感想

  • 半数が解けている問題は解けるようにする
  • 大学生・高校生が運営しているコンテスト、解説が親切なことが多くて良い

セグメント木で使える演算子

目的

  • これってセグ木でできる?をまとめる
  • 参考コードを探すときの高速化

モノイド

モノイドの例(随時追記)

beetさんのまとめ

  • 和、積、min, max, gcd, lcm
  • 他にもたくさん「セグ木に載せるモノイドまとめ(未完)」

セグ木がいらない例

  • 和(累積和でいい)
  • XOR (累積XOR)でいい

The Book of Trees: Visualizing Branches of Knowledge

The Book of Trees: Visualizing Branches of Knowledge

  • 作者:Manuel Lima
  • 出版社/メーカー: Princeton Architectural Press
  • 発売日: 2014/04/08
  • メディア: ハードカバー

K - 巨大企業 / Conglomerate ~LCA~

Quiz

https://atcoder.jp/contests/past201912-open/tasks/past201912_k

AC

https://atcoder.jp/contests/past201912-open/submissions/9277571

解法

Code

// LCA set
VV G;
const int N_MAX = 150010;
const int MAX_LOG_V = 20;
ll depth[N_MAX] = {};
ll parent[MAX_LOG_V][N_MAX] = {};
void dfs(ll index, ll prev, ll _depth){
    depth[index] = _depth;
    parent[0][index] = prev;
 
    for(ll to : G[index]){
        if(to==prev){
            continue;
        }
        dfs(to, index, _depth+1);
    }
    return;
}
ll LCA(ll a, ll b){
    if(a==b){
        return a;
    }
    // aよりbが深い(または同じ)と仮定する
    if(depth[a] > depth[b]){
        swap(a, b);
    }
    // bを根側に辿っていく
    ll diff_depth = depth[b] - depth[a];
    FOR(k, 0, MAX_LOG_V){
        if(diff_depth >> k & 1){
            b = parent[k][b];
        }
    }
    // aとbの深さが揃った
    if(a==b){
        return a;
    }
    // 大きい歩幅で共通親までジャンプ
    for(int k=MAX_LOG_V-1; k>=0; k--){
        if(parent[k][a] != parent[k][b]){
            a = parent[k][a];
            b = parent[k][b];
        }
    }
    // 1つ上がLCA
    return parent[0][a];
}
void prepare_LCA(ll N, ll root=0){
    dfs(root, -1, 0);
    // ダブリングで親 2^k
    FOR(k, 1, MAX_LOG_V){
      // FOR(i, 1, N+1){
      FOR(i, 0, N){
        ll p = parent[k-1][i];
        if(p==-1) continue;
        parent[k][i] = parent[k-1][p];
      }
    }
}
// LCA set end

その他

グラフ描画

20 19
1 4
2 11
3 12
5 1
6 13
7 13
8 4
9 6
10 20
11 1
12 1
13 20
14 10
15 8
16 8
17 20
18 10
19 18
20 1

f:id:peroon:20200102020127p:plain

E - Handshake ~二分探索・累積和・格子点~

f:id:peroon:20191229232631p:plain

9 14
1 3 5 110 24 21 34 5 3

の場合の図 (サンプル2)

Quiz

https://atcoder.jp/contests/abc149/tasks/abc149_e

AC

https://atcoder.jp/contests/abc149/submissions/9230235

解説

  • editorialより複雑なことをしてしまった気がするが、解けたので共有
  • 全組み合わせをplotした後、和が大きい方から取っていく処理は、グリッド上でx+y=aなる右下がりの直線上か、それより上にある点で数えられる
  • パラメータ a を二分探索し、M点取れるa, M点取れないaの境界を探す
  • その境界のaを使って数えた時、点数がMより大きくなった場合は削る
  • (境界だけど)取りすぎちゃった例(M=5点取りたいのに6点取ってしまった)
3 5
1 2 3
答え 24

6+5+5+4+4+4 = 28
取りすぎちゃった4を1つ削って24

f:id:peroon:20191229233923p:plain

計算量

  • 二分探索の中で二分探索をしているのでO(N (logN)2)
  • 105 x 16 x 16 = 25600000 = 2.5 x 107
  • ややギリギリで間に合う (100ms)

グラフ

https://www.desmos.com/calculator