ferinの競プロ帳

競プロについてのメモ

SRM664 div1 easy BearPlays

考えたこと

  • 操作回数KでO(K)はできないならどうせ周期性という気持ちになる
  • 周期性で O(min(A+B, K)) くらいにはなりそうという気持ちになるが足りない
  • 適当に実験したら実は周期が短いのがわかるのでは?と思い実験する
  • 3*10^6回実行しても周期性がないのがある
  • 周期が長すぎて周期性つかえない気持ちになってくる
    -----解説を見た-----
  • 何もわからないので解説を見る
  • 小さい方を2倍するとか考えずにとりあえずAを2倍する処理ということにする
  • 大きい方を2倍したとしても mod A+B を取るとこれは問題の操作に一致する
  • したがってK回操作を行ったときAは ret = A*2^K mod A+B になる
  • min(ret, A+B-ret) が答え

どうせ周期性だろうと思ったら違った…
大きい方を2倍したらどうなるか考える発想がなかった
mod A+Bを取るのが全く思いつかなかった

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

//二分累乗法 xのe乗
ll binpow(ll x, ll e) {
  ll a = 1, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
    else {a = (a*p) % MOD; e--;}
  }
  return a % MOD;
}

class BearPlays {
   public:
   int pileSize(int A, int B, int K)
  {
    MOD = A+B;
    int ret = A*binpow(2,K)%MOD;
    return min(ret, A+B-ret);
  }
};

SRM663 div1 easy ABBADiv1

考えたこと

  • とりあえずinitial→targetじゃなくて逆に戻していく動作を考える
  • 先頭にBなら取り除いて残りを反転、末尾にAなら取り除くの2パターンがある
  • 愚直にやると2Nくらいかかりそうだけど冷静に考えるとそこまでパターン数は多くない気がしてくる
  • 2通りに派生しつづけるようなケースがなさそうな気持ちになる
  • |init| = 1, |target| = 50のケースを何個か作って試しても一瞬で終わるしだめなケースが思い浮かばない
  • 投げたら通った(は?)
  • 解説を読んで冷静になって考えるとtargetの部分集合とその反転しか作られるケースはないので2乗オーダーくらいしかケースはない
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

class ABBADiv1 {
   public:
   string canObtain(string init, string target)
  {
    function<bool(string)> solve = [&](string s) -> bool {
      if(s.size() < init.size()) return false;
      if(s == init) return true;
      bool ret = false;
      if(s[0] == 'B') {
        string t = s.substr(1);
        reverse(ALL(t));
        ret |= solve(t);
      }
      if(s.back() == 'A') {
        s.pop_back();
        ret |= solve(s);
      }
      return ret;
    };

    return solve(target) ? "Possible" : "Impossible";
  }
};

AGC021 B - Holes

問題ページ
B - Holes

考えたこと

  • Rがめっちゃでかいのは別に気にしなくてよさそう
  • 穴pに落ちる範囲の面積を求めて面積比を確率として求めるみたいなのを考える
  • 穴pと他の穴qの垂直二等分線を引き、穴pが属する領域の凸多角形を求めるみたいなのをやりたくなる
  • 穴pが属するのがどの領域なのかわからん
  • 垂直二等分線の交点群の凸包を取ればいいのではみたいな気持ちになるけど自明にだめ
    -----解説を見た-----
  • 穴pに落ちる範囲を角度で求める
  • 凸包を求めてその両端の穴との角度の関係を求める

幾何ができない現役ICPCerなのでつらい

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const double EPS = 1e-8;
const double INF = 1e12;
const double PI = atan(1)*4;

//point
typedef complex<double> P;
namespace std {
    bool operator < (const P& a, const P& b) {
        return real(a) != real(b) ? real(a)<real(b) : imag(a)<imag(b);
    }
    bool cmp_y(const P &a, const P &b){
        return imag(a) != imag(b) ? imag(a)<imag(b) : real(a)<real(b);
    }
}
double cross(const P& a, const P& b) {
    return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
    return real(conj(a)*b);
}
// line
struct L : public vector<P> {
    L(const P& a, const P& b) {
        push_back(a); push_back(b);
    }
};
// polygon
typedef vector<P> G;

G convex_hull(G ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end(), cmp_y);
  G r(2*n);
  for(int i = 0; i < n; i++){
    while(k>1 && cross(r[k-1]-r[k-2],ps[i]-r[k-2]) < -EPS)k--;
    r[k++] = ps[i];
  }
  for(int i = n-2, t = k; i >= 0; i--){
    while(k>t && cross(r[k-1]-r[k-2],ps[i]-r[k-2]) < -EPS)k--;
    r[k++] = ps[i];
  }
  r.resize(k-1);
  return r;
}

int x[105], y[105];
map<PII, int> mp;
double ans[105];
signed main(void)
{
  int n;
  cin >> n;
  G ps;
  REP(i, n) {
    cin >> x[i] >> y[i];
    ps.PB(P(x[i], y[i]));
    mp[{x[i], y[i]}] = i;
  }

  G poly = convex_hull(ps);
  REP(i, poly.size()) {
    P p = poly[(i==0?poly.size()-1:i-1)] - poly[i];
    P q = poly[(i==poly.size()-1?0:i+1)] - poly[i];
    double theta = PI - acos(dot(p, q)/abs(p)/abs(q));
    ans[mp[{poly[i].real(), poly[i].imag()}]] = theta/2/PI;
  }

  REP(i, n) cout << fixed << setprecision(9) << ans[i] << endl;

  return 0;
}

AOJ1347 Shopping

問題ページ
Shopping | Aizu Online Judge

概要

n個の店が並んだ商店街がありi番目の店は位置iにある。ある店dを訪れてからある店cを訪れなければならないというm個の制約の元で位置0から位置n+1まで歩くときの最小距離を求めろ。

n <= 10000, m <= 500

考えたこと

  • 区間だし終端でソートする
  • 前の区間と交差しないか包含するか交差するの3パターンになりそう f:id:ferin_tech:20180224035225p:plain
  • 交差するか包含する場合は引き返すのをまとめてやった方がよさそう
  • どこまでまとめて引き返すべきかを計算する
  • 出すと落ちる
  • 一旦交差しない区間が来た後、交差する区間が来るパターンを見落としていた
  • 直すと通った

区間グラフ系の問題苦手だ…

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

signed main(void)
{
  int n, m;
  cin >> n >> m;
  vector<PII> v;
  REP(i, m) {
    int c, d;
    cin >> c >> d;
    if(c < d) v.PB({d, c});
  }
  sort(ALL(v));

  if(v.size() == 0) {
    cout << n+1 << endl;
    return 0;
  }

  int ret = n+1;
  for(int i=0; i<m; ++i) {
    // cout << "i:" << i << endl;
    int l = v[i].second, r = v[i].first;
    int idx = i;
    for(int j=i+1; j<m; ++j) {
      if(v[j].second <= r) {
        r = v[j].first;
        chmin(l, v[j].second);
        idx = j;
      }
      // cout << l << " " << r << " " << idx << endl;
    }
    ret += (r-l)*2;
    i = idx;
  }

  cout << ret << endl;

  return 0;
}

DP高速化

dp[i][j] = min(dp[i][k] + cost[k]) みたいなdpの遷移がうまくやると高速にできるみたいなテクのまとめ

ConvexHullTrick

以下の二つのクエリに答えられるというテク

  • 直線y=ax+bを追加する
  • x=iのときの最小(最大)のyを求める

追加する直線の傾きが単調、最小クエリのxが単調であると実装が楽になる。
O(n^2) → O(n) or O(nlogn) に高速化

詳しくは以下を見てください。
Convex-Hull Trick - sataniC++, Convex Hull Trick - 競技プログラミング+αなブログ, 蟻本p304

問題例

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君
Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry 解説
Codeforces Round #185 (Div. 1) B. Cats Transport 解説

Knuth-Yao Speedup

X[i][j] = min_{i<=s<j} (X[i][s] + X[s+1][j]) + W[i][j] の形のDPを高速化するテク
WがQI(Quandrangle Inequality)かつ単調なときに使える
O(n^3) → O(n^2) に高速化

詳しくは以下を見てください。
Knuth-Yao speedup - 週刊 spaghetti_source - TopCoder部

問題例

KUPC2012 J - 刺身 解説
SPOJ BRKSTRNG - Breaking String 解説

Hu-Tucker Algorithm, Garsia-Wachs Algorithmといったより強いのもあるらしい。
最適二分探索木問題(KUPC 2012 問題J 「刺身」) - (iwi) { 反省します - TopCoder部

monotone minima

2変数関数f(i,j)で各行の最小値が右下へ単調に下がっていくとき、各行の最小値を高速に求められるテクf:id:ferin_tech:20180223072028p:plain O(n^2) → O(nlogn) に高速化

詳しくは以下を読んで下さい。
Totally Monotone Matrix Searching (SMAWK algorithm) - 週刊 spaghetti_source - TopCoder部

問題例

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君 解説

Divide and conquer

dp[i][j] = min_{0<=k<i} {dp[i-1][k] + w(k,j)} の形のDPを高速化するテク
wがQIなら最小値を達成するkに単調性が存在し高速化することができる
Knuth-Yao speedupとこれはargminの単調性を使ってdpテーブルを埋める順を変えてるイメージ

コードを見てもらうのが一番わかりやすいと思うのでコードをのせます。[l,r]の区間ではargminが[optl,optr]の区間に存在するようになっています。dp[i][mid]を区間[optl,optr]を線形に探索することで求めます。するとargminの単調性より[l,mid-1]ではargminが取りうる区間が[optl,optm]、[mid+1,r]ではargminが取りうる区間が[optm,optr]となります。argminが存在しうる範囲が狭まっていくので全てを計算する必要がなく計算量が落ちます。真面目に計算するとO(NKlogN)になるらしい。

function<void(int,int,int,int,int)>
func = [&](int i, int l, int r, int optl, int optr) {
  if(l > r) return;
  int mid = (l+r)/2, optm = -1;
  FOR(j, optl, min(mid+1, optr+1)) {
    if(dp[i][mid] > dp[i-1][j] + W[j+1][mid]) {
      dp[i][mid] = dp[i-1][j] + W[j+1][mid];  // [j+1, mid]
      optm = j;
    }
  }
  func(i, l, mid-1, optl, optm);
  func(i, mid+1, r, optm, optr);
};
// dpの初期値を設定
REP(i, n) dp[0][i] = W[0][i];
FOR(i, 1, n) REP(j, k) dp[i][j] = LLINF;
// DPする
FOR(i, 1, k) func(i, 0, n-1, 0, n-1);
cout << dp[k-1][n-1] << endl;

問題例

Codeforces Round #190 (Div. 1) E. Ciel and Gondolas 解説
Codeforces Round #438 F. Yet Another Minimization Problem 解説

あとはセグ木を使って高速化とかがありそう
とりあえずDPっぽかったら漸化式を書いて高速化できる形になっていたらQIとかを確認するとかするとよさそう

参考ページ
直前合宿 講義スライド

Codeforces Round #438 F. Yet Another Minimization Problem

問題ページ
Problem - F - Codeforces

解法

dp[i][j] = (i個目の部分列でj番目までをカバーしたときの最小コスト) としたDPを考える。DPの漸化式は dp[i][j] = min_{k<j} {dp[i][k] + (k+1番目からj番目を一つの部分列にいれたときのコスト)} となる。コスト関数をW(i,j)=([i,j]を一つの部分列としたときのコスト)として定義する。これはQIと単調性が存在するのでdevide and conquerを用いることができるので遷移をO(n)からO(logn)に落とすことができ問題ない計算量になる。
コスト関数を求めるのにO(n^2)かけて前計算などやろうとすると当然TLEするので何か別の方法で高速に求める必要がある。尺取り法を用いてコスト関数を求めることで解くことができる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

bool flag[100010];
int a[100010], dp[25][100010];

int sum, L, R, cnt[100010];
inline void add(int idx) { sum += cnt[a[idx]]++; }
inline void del(int idx) { sum -= --cnt[a[idx]]; }
int W(int l, int r) {
  while(L > l) add(--L);
  while(L < l) del(L++);
  while(R < r) add(++R);
  while(R > r) del(R--);
  return sum;
}

signed main(void)
{
  int n, k;
  cin >> n >> k;
  REP(i, n) cin >> a[i], --a[i];
  cnt[a[0]]++;

  function<void(int,int,int,int,int)>
  func = [&](int i, int l, int r, int optl, int optr) {
    if(l > r) return;
    int mid = (l+r)/2, optm = -1;
    FOR(j, optl, min(mid+1, optr+1)) {
      int ncost = dp[i-1][j] + W(j+1, mid); // [j+1, mid]
      if(dp[i][mid] > ncost) {
        dp[i][mid] = ncost;
        optm = j;
      }
    }
    func(i, l, mid-1, optl, optm);
    func(i, mid+1, r, optm, optr);
    return;
  };

  REP(i, n) dp[0][i] = W(0, i);
  FOR(i, 1, k) REP(j, n) dp[i][j] = LLINF;

  FOR(i, 1, k) func(i, 0, n-1, 0, n-1);

  cout << dp[k-1][n-1] << endl;

  return 0;
}

Codeforces Round #190 (Div. 1) E. Ciel and Gondolas

問題ページ
Problem - E - Codeforces

解法

dp[i][j] = (i番目のゴンドラでj人目までを乗せたときの最小値) としたDPを考える。漸化式はdp[i][j] = min_{k<j} (dp[i][k] + (k+1人目からj人目を一つのゴンドラに乗せたときのコスト)) となる。W(i,j)を区間[i,j]の人を一つのゴンドラに乗せるときのコストとすると、これは二次元累積和の要領で前計算O(n^2)、クエリO(1)で求められる。
このDPを愚直に実装するとO(KN^2)でTLEする。ここでW(i,j)の性質に注目すると単調性とQIが成り立っているのでdivide and conquerを用いて計算量を落とすことができ、O(KNlogN)で求められる。
定数倍がやたらきついのと入力TLEに注意。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

int u[4010][4010], W[4010][4010], dp[805][4010];
signed main(void)
{
  int n, k;
  scanf("%d %d ", &n, &k);
  REP(i, n) {
    REP(j, n) {
      u[i][j] = getchar() - '0';
      getchar();
    }
  }

  function<void(int,int,int,int,int)>
  func = [&](int i, int l, int r, int optl, int optr) {
    if(l > r) return;
    int mid = (l+r)/2, optm = -1;
    FOR(j, optl, min(mid+1, optr+1)) {
      if(dp[i+1][mid] > dp[i][j] + W[j+1][mid]) {
        dp[i+1][mid] = dp[i][j] + W[j+1][mid];  // [j+1, mid]
        optm = j;
      }
    }
    func(i, l, mid-1, optl, optm);
    func(i, mid+1, r, optm, optr);
  };

  FOR(w, 1, n+1) {
    for(int l=0, r=l+w; r<n; ++l, ++r) {
      W[l][r] = u[l][r];
      if(w >= 2) W[l][r] += W[l+1][r] + W[l][r-1] - W[l+1][r-1];
    }
  }
  FOR(i, 1, k) REP(j, n) dp[i][j] = INF;
  REP(i, n) dp[0][i] = W[0][i];

  REP(i, k) func(i, 0, n-1, 0, n-1);
  cout << dp[k-1][n-1] << endl;

  return 0;
}