2018-03-07

SRM688 div1 easy ParenthesesDiv1Easy

考えたこと

文字列長が1000なのに操作回数10回の制限でよくわからない
とりあえず実験するけどよくわからない
括弧列を+1/-1に置き換えるやつをしてみる
+1/-1の累積和で-1になったところがあったらそこを1回は操作しないとだめ
操作しないといけない場所がきたらそこを左端、')'を右端にするような区間で反転しても正しい括弧列になるような区間にしたい
条件がかなり厳しいけど操作回数10回で実現するには最適なの操作をしないとだめそうだしとか考える
色々実験しても操作回数10回になるようなのは思いつかない
75分経ちそうだったので適当な貪欲を書いて投げたら落ちた
-----解説を見た-----
正しい括弧列の部分列は反転しても影響がないから無視
すると))))))((((((((みたいな列になる
前半の')'をひっくり返して後ろ半分を')'に反転すれば正しい括弧列になる
2回あれば確実にできる

操作で不変な部分に注目するくらいは思いついてもよかった
操作回数の制限が異様に厳しいんだからきれいな構成が存在する方向でもっと考えるべきだった
あと実装が下手

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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); }

class ParenthesesDiv1Easy {
   public:
   vector <int> correct(string s)
  {
    string ss = s;
    ll n = s.size();
    if(n%2) return {-1};

    vector<ll> x(n);
    REP(i, n) x[i] = (s[i]=='('?1:-1);

    vector<bool> able(n);
    REP(i, n) {
      ll now = 0, idx = -1;
      bool flag = true;
      FOR(j, i, n) {
        now += x[j];
        if(now < 0) flag = false;
        if(flag && now == 0) idx = j;
      }
      FOR(j, i, idx+1) able[j] = true;
    }

    ll idx = -1, cnt = 0;
    REP(i, n) {
      if(able[i]) continue;
      if(s[i] == ')') s[i] = '(', idx = i;
      cnt++;
    }
    if(cnt == 0) return {};

    vector<int> ans;
    if(idx != -1) {ans.PB(0); ans.PB(idx);}

    vector<bool> n_able(n);
    REP(i, idx+1) n_able[i] = able[idx-i];
    REP(i, idx+1) able[i] = n_able[i];

    cnt /= 2;
    for(int i=n-1; i>=0; --i) {
      if(able[i]) continue;
      cnt--;
      s[i] = ')';
      if(cnt == 0) {
        idx = i;
        break;
      }
    }
    ans.PB(idx); ans.PB(n-1);

    return ans;
  }
};

2018-03-07

SRM687 div1 easy AlmostFibonacciKnapsack

競技プログラミング SRM

考えたこと

ナップザックDPの復元とか考えつつ問題文を読むと制約的に論外
上から貪欲にとっていくやつを考える
7とかが3+4でつくれるけど先に6を取っちゃうとだめ
漸化式の性質を何かうまく使う…？
とりあえず漸化式の要素を順番に書いていってみるけどよくわからない
2,3,2+3-1,2+3*2-2,2*2+3*3-3,… で係数もフィボナッチ数列っぽくなってるけど何か使える気にならない
i項目まででどういう数字をつくれるのかを実験する
3項目までで2～7がつくれる
4項目の6と合わせると8～13がつくれるので2～13がつくれる
5項目の9と合わせると11～22がつくれるので2～22がつくれる
つくれない-1のケースが存在しない気がしてくる
つくれる区間に穴が空いちゃうようなケースについてちゃんと考えてみるとなさそう
貪欲に上から取っていくような構成ができそう
最初に考えたように小さい方の数だと貪欲だとだめそうなのがある
4項目よりあとのだと貪欲で構成できそうなのでx>=6の間は貪欲に使ってよさそう
2～5は最初の3項の和で作れる
1をつくるのは a[i]+1 = a[i-1]+a[i-2] を利用して作れる
貪欲にやったら通った

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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};

class AlmostFibonacciKnapsack {
   public:
   vector <int> getIndices(long long x)
  {
    vector<ll> v;
    ll a=2, b=3;
    v.PB(a); v.PB(b);
    while(a+b-1 < 1e18) {
      ll tmp = b;
      b = a+b-1;
      a = tmp;
      v.PB(b);
    }

    vector<int> ans;
    ll idx = v.size()-1;
    while(x > 5 && idx >= 2) {
      if(x > v[idx]) {
        x -= v[idx];
        ans.PB(idx+1);
        // cout << x << endl;
      }
      idx--;
    }

    if(x == 5) {
      ans.PB(1); ans.PB(2);
    } else if(x == 4) {
      ans.PB(3);
    } else if(x == 3) {
      ans.PB(2);
    } else if(x == 2) {
      ans.PB(1);
    } else if(x == 1) {
      // ans.back() を消して ans.back()-1, ans.back()-2 を追加
      ll tmp = ans.back();
      ans.pop_back();
      ans.PB(tmp-1); ans.PB(tmp-2);
    }

    return ans;
  }
};

2018-03-07

SRM686 div1 easy BracketSequenceDiv1

競技プログラミング SRM

考えたこと

開括弧を選んでそれに対応する閉じ括弧のパターンが何通りあるか数えるみたいなので考える
正しい括弧列ならば開括弧の数は(括弧列の長さ/2)になるはず
与えられる括弧列の長さが最大40なのでその半分なら開括弧の選び方を全列挙できる
もし開括弧が閉括弧より多ければ文字列を反転すればいい
開括弧に対応させられる閉括弧の数を知りたい
閉括弧について後ろから累積和を取ればいい気持ちになる
後ろの開括弧から試すと (閉括弧の数 - 使った分の閉括弧の数) の積でいける気持ちになる
sampleを試すと([)]みたいなのを余計に数えている
次に出て来る種類の違う開括弧までで閉括弧の数を数える
()())) で一番最初の開括弧なら太字の3個みたいな
sample4が一生通せない
冷静になって考え直すと([])を数えられてない
開括弧を指定したところで対応した閉括弧の数を高速に数えられる気がしない
-----解説を見た-----
半分全列挙 or DP
半分全列挙
- 前半と後半でそれぞれ使う括弧を列挙しておく
- 前半と後半でマージできるものの数を数える
DP
- dp[l][r] = [l,r)で正しい括弧列の部分文字列の数
- dp[l][r] = prod(dp[l][x] * dp[x+1][r] | s[l]とs[i]が対応が取れている)

それっぽい解法を思いついた気持ちになって考えてたけど的外れだったらしい
だめな方針なことにもうちょっと早く気づきたかった…
|S| <= 40 で半分全列挙を考えもしなかったのはだめ
半分全列挙はTLギリギリっぽいので思いつけたらDPの方がよさそう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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};

ll dp[55][55];
class BracketSequenceDiv1 {
   public:
   long long count(string s)
  {
    ll n = s.size();

    function<ll(ll,ll)> func = [&](ll l, ll r) -> ll {
      if(dp[l][r] >= 0) return dp[l][r];
      if(l==r) return 1;
      ll ret = func(l+1, r);
      FOR(i, l+1, r) {
        if((s[l]=='('&&s[i]==')') || (s[l]=='['&&s[i]==']')) {
          ret += func(l+1,i) * func(i+1, r);
        }
      }
      return dp[l][r] = ret;
    };

    memset(dp, -1, sizeof(dp));
    return func(0, n) - 1;
  }
};

2018-03-07

SRM685 div1 easy MultiplicationTable2

競技プログラミング SRM

考えたこと

ある数字iを削除できるのは(j$k) == iとなるj,kが存在しない事みたいな気持ちになる
削除する対象の数字を探索するのにO(n)、削除判定O(n^2)で繰り返すのにO(n)で間に合いそうという気持ちになる
数字が削除できるならするを繰り返すコードを書く
サンプルで落ちる
よくよく考えると2個以上まとめて削除しないとみたいなのがあるね
逆に集合に追加していくみたいな方面で考える
数iを追加するなら (i$i)、(i$j)、(j$i) (jはすでに集合に含まれている要素) も集合に含まれていないとだめ
集合の要素、集合に追加しないといけない要素をもって最低限必要な要素を追加していく
集合に最初に追加する要素をn通り試すのでO(n)
集合に追加しうるのは最大O(n)回
追加しないといけない要素の判定でO(nlogn)
O(n^3logn)でいけそう
出すと通る

削除するコードを書いてたら遅くなりすぎた
考察したらせめてサンプルくらいは試しましょう（ア）

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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 del[55];
class MultiplicationTable2 {
   public:
   int minimalGoodSet(vector <int> table)
  {
    int nn = table.size(), n = sqrt(nn);

    int ret = INF;
    for(int st=0; st<n; ++st) {
      set<int> s;
      stack<int> ns;
      ns.push(st);
      while(ns.size()) {
        int x = ns.top(); ns.pop();
        s.insert(x);
        if(s.find(table[x+x*n]) == s.end()) ns.push(table[x+x*n]);
        for(int i: s) {
          if(s.find(table[i+x*n]) == s.end()) ns.push(table[i+x*n]);
          if(s.find(table[x+i*n]) == s.end()) ns.push(table[x+i*n]);
        }
      }
      chmin(ret, (int)s.size());
    }

    return ret;
  }
};

2018-03-06

codeforces #433 div2 D. Jury Meeting

競技プログラミング Codeforces

問題ページ Problem - D - Codeforces

考えたこと

頂点iに住んでいる人が2往復以上したほうがいいことはない
日付について区間[l,l+k]で議論をすると考える
lより前の最も安いチケットで頂点0へ行き、l+kよりもあとの最も安いチケットで頂点0から出発する
各頂点jについて ticket1[i][j] = (i以前で最も安いチケットの値段), ticket2[i][j] = (i以後で最も安いチケットの値段) みたいなのを求めたくなる
これがわかっていればlを全て試して最も安いものを出力すればいいだけ
愚直にやるとO(nmax(d))になって当然だめ
lとして取りうるのは飛行機が出発する時間だけ
r=l+kとして取りうるのは飛行機が到着する時間だけ
更新が点に対してchmin、区間和みたいなのを求めたい気持ちになる
セグ木を貼る
dp1[i] = sum(ticket1[i][j] | 0<=j<n) みたいなのとすれば O(MlogN) でdp1が求まる
同様にticket2についてdp2も求まる
累積minを取って全てのlについて試せばいけそう
オーバーフローとかm=0で散々バグらせたけど通った
-----解説を見た-----
冷静になって考えると単純に配列を持っておくだけで更新ができるのでセグ木いらない
全ての頂点から出発するところまで計算しておけばあとは一点が更新されるだけなので総和の更新も簡単にできる

ソースコード

セグ木で書いたやつ

#define __USE_MINGW_ANSI_STDIO 0
#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 = 1e13;
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};

template <typename monoid>
class segmentTree {
public:
  using M = monoid;
  using T = typename M::value_type;

  int sz;
  vector<T> x;

  segmentTree(int n = 1e5) {
    sz = 1; while(sz < n) sz *= 2;
    init();
  }
  void init() { x.assign(sz*2, M::id()); }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) return x[k];
    return M::f(query(a, b, 2*k+1, l, (l+r)/2),
                query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, sz);}
  // 点更新
  void update(int i, const T &val) {
    i += sz-1;
    x[i] = M::g(x[i], val);
    while(i > 0) {
      i = (i-1) / 2;
      x[i] = M::f(x[i*2+1], x[i*2+2]);
    }
  }
};

template <typename T>
struct mono {
  using value_type = T;
  static constexpr T id() {return LLINF;}
  static T f(const T &a, const T &b) { return a+b; }
  static T g(const T &a, const T &b) { return min(a, b); }
};

using segtree = segmentTree<mono<int>>;

VVI ti[2];
int dp1[1000010], dp2[1000010];
signed main(void)
{
  int n, m, k;
  cin >> n >> m >> k;
  REP(i, m) {
    int d, f, t, c;
    cin >> d >> f >> t >> c;
    if(t == 0) {
      ti[0].PB({d, f-1, c});
    } else {
      ti[1].PB({d, t-1, c});
    }
  }
  sort(ALL(ti[0]));
  sort(ALL(ti[1]));

  REP(i, 1000010) dp1[i] = dp2[i] = LLINF;

  segtree seg1(n);
  REP(i, ti[0].size()) {
    int l = ti[0][i][0] + 1;
    seg1.update(ti[0][i][1], ti[0][i][2]);
    chmin(dp1[l], seg1.query(0, n));
  }

  segtree seg2(n);
  for(int i=(int)ti[1].size()-1; i>=0; --i) {
    int r = ti[1][i][0] - 1;
    seg2.update(ti[1][i][1], ti[1][i][2]);
    chmin(dp2[r], seg2.query(0, n));
  }

  FOR(i, 1, 1000001) chmin(dp1[i], dp1[i-1]);
  for(int i=1000000; i>=0; --i) chmin(dp2[i], dp2[i+1]);

  int ans = LLINF;
  REP(l, 1000001) {
    int r = l+k-1;
    if(r > 1000000) break;
    chmin(ans, dp1[l] + dp2[r]);
  }
  if(ans == LLINF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}

セグ木使わずに書いた版

#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 = 1e13;
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};

VVI ti[2];
int dp1[1000010], dp2[1000010];
signed main(void)
{
  int n, m, k;
  cin >> n >> m >> k;
  REP(i, m) {
    int d, f, t, c;
    cin >> d >> f >> t >> c;
    if(t == 0) {
      ti[0].PB({d, f-1, c});
    } else {
      ti[1].PB({d, t-1, c});
    }
  }
  sort(ALL(ti[0]));
  sort(ALL(ti[1]));

  REP(i, 1000010) dp1[i] = dp2[i] = LLINF;

  VI seg1(n, -1);
  int cnt = 0, sum = 0;
  REP(i, ti[0].size()) {
    if(cnt < n) {
      if(seg1[ti[0][i][1]] == -1) {
        seg1[ti[0][i][1]] = ti[0][i][2];
        cnt++;
        if(cnt == n) {
          REP(j, n) sum += seg1[j];
          chmin(dp1[ti[0][i][0]+1], sum);
        }
      } else {
        chmin(seg1[ti[0][i][1]], ti[0][i][2]);
      }
    } else {
      if(seg1[ti[0][i][1]] > ti[0][i][2]) {
        sum -= seg1[ti[0][i][1]];
        seg1[ti[0][i][1]] = ti[0][i][2];
        sum += seg1[ti[0][i][1]];
        chmin(dp1[ti[0][i][0]+1], sum);
      }
    }
  }

  VI seg2(n, -1);
  cnt = 0, sum = 0;
  for(int i=(int)ti[1].size()-1; i>=0; --i) {
    if(cnt < n) {
      if(seg2[ti[1][i][1]] == -1) {
        seg2[ti[1][i][1]] = ti[1][i][2];
        cnt++;
        if(cnt == n) {
          REP(j, n) sum += seg2[j];
          chmin(dp2[ti[1][i][0]-1], sum);
        }
      } else {
        chmin(seg2[ti[1][i][1]], ti[1][i][2]);
      }
    } else {
      if(seg2[ti[1][i][1]] > ti[1][i][2]) {
        sum -= seg2[ti[1][i][1]];
        seg2[ti[1][i][1]] = ti[1][i][2];
        sum += seg2[ti[1][i][1]];
        chmin(dp2[ti[1][i][0]-1], sum);
      }
    }
  }

  FOR(i, 1, 1000001) chmin(dp1[i], dp1[i-1]);
  for(int i=1000000; i>=0; --i) chmin(dp2[i], dp2[i+1]);

  int ans = LLINF;
  REP(l, 1000001) {
    int r = l+k-1;
    if(r > 1000000) break;
    chmin(ans, dp1[l] + dp2[r]);
  }
  if(ans == LLINF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}

2018-03-06

codeforces #433 div2 C. Planning

競技プログラミング Codeforces

問題ページ
Problem - C - Codeforces

考えたこと

順列を全部試すのが無理なのはそれはそう
制約がだいぶでかいのでdpはつらそう
隣同士をswapするとコストがどう変化するかを考える
i,i+1をswapするとコストが +c[i]-c[i+1] 変化する
sortするような感じで最適化できないかと思ったけど動かせない範囲があるし厳しい気持ちになる
遅延時間の総和はnk分になる
delay[i] = (i番目のflightの遅延時間) とすると delay[i]*c[i] を最小化する感じになる
sum(delay) = nk になるようにうまく振り分けていきたい
順列なので当然同じ位置に複数flightがあってはいけない
これをdelay[i]で簡単な制約として書くのが無理な気持ちになる
i番目のflightを最適な位置に挿入するを繰り返すみたいなのを考える
挿入位置を探すのを何か高速な方法でしたい
単調性がないのでにぶたんもできないし不可能では？
逆に時刻tに飛ばすべきflightを挿入する
時刻tに飛ばすことが可能なflightのうちc[i]が最も大きいものを挿入すればいいのでは？
c[i]が大きいものを後ろに回したらその分コストが増えるので得することがなさそう
その時点で飛ばせるflightのうちc[i]が大きいものを飛ばすgreedyでよさそう
これはpriority_queueを使えばいいのでO(nlogn)でできる

貪欲でいいことに気づくのが遅すぎた…
順列をbitでO(2^n)に落とすのじゃなくてO(n)とかO(nlogn)に落とす系苦手な気がしている

ソースコード

#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, k;
  cin >> n >> k;
  VI a(n);
  REP(i, n) cin >> a[i];

  priority_queue<PII> que;
  REP(i, k) que.push({a[i], i+1});

  VI ans(n);
  int ret = 0;
  FOR(i, k, n) {
    que.push({a[i], i+1});
    PII p = que.top(); que.pop();
    ret += p.first * (i+1 - p.second);
    ans[p.second-1] = i+1;
  }
  int idx = n+1;
  while(que.size()) {
    PII p = que.top(); que.pop();
    ret += p.first * (idx - p.second);
    ans[p.second-1] = idx;
    idx++;
  }

  cout << ret << endl;
  REP(i, n) cout << ans[i] << " ";
  cout << endl;

  return 0;
}

2018-03-06

codeforces #361 div2 D. Friends and Subsequences

競技プログラミング Codeforces

問題ページ
Problem - D - Codeforces

sparseTableのverifyとして解いた。

解法

区間の左端lを固定して考えてみる
区間[l,r]についてmax(a) - min(b)を考えると単調に増えていく
max(a) - min(b) の数列は [-2, -1, -1, 0, 0, 0, 0, 1, 2, 3] みたいな単調増加する列になるはず
この数列で0の数を数えれば左端がlのとき条件を満たす区間の数がわかる
0の数を数えるのは二分探索をつかえばできる
区間max,minを取るのはsparsetableでO(1)なので二分探索の判定はO(1)でできる
したがって合計O(nlogn)でできる

ソースコード

#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

constexpr auto LLINF = (1LL<<60);
constexpr auto INF = (1LL<<30);
constexpr auto MOD = 1e9+7;

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};

template <typename S>
class sparseTable {
public:
  using T = typename S::T;
  int n;
  vector<int> log2;
  vector<vector<T>> t;

  sparseTable(int nn) {
    n = nn;
    log2.assign(n+1, 0);
    for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
    t = vector<vector<T>>(log2[n]+1, vector<T>(n));
  }
  void init(vector<T> v) {
    for(int i=0; i<n; ++i) t[0][i] = v[i];
    for(int j=1; j<=log2[n]; ++j) {
      int w = 1LL<<(j-1);
      for (int i = 0; i+(w<<1) <= n; ++i) {
        t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
      }
    }
  }
  // [l, r]
  T query(int l, int r) {
    int j = log2[r - l];
    return S::op(t[j][l], t[j][r-(1 << j)+1]);
  }
};

// 集合T、結合則・可換・冪等律が成り立つ二項演算op
struct minnimum {
  using T = int;
  static T op(const T& a, const T& b) { return min(a, b); }
};
struct maximum {
  using T = int;
  static T op(const T& a, const T& b) { return max(a, b); }
};

signed main(void)
{
  int n;
  cin >> n;
  VI a(n), b(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];

  sparseTable<maximum> sp1(n);  sp1.init(a);
  sparseTable<minnimum> sp2(n); sp2.init(b);

  int ret = 0;
  REP(l, n) {
    if(a[l] > b[l]) continue;

    // (lb, ub]
    int lb = l-1, ub = n-1;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(sp1.query(l, mid) - sp2.query(l, mid) >= 0) {
        ub = mid;
      } else {
        lb = mid;
      }
    }
    int rmin = ub;
    if(sp1.query(l, rmin) != sp2.query(l, rmin)) continue;

    // [lb, ub)
    lb = l, ub = n;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(sp1.query(l, mid) - sp2.query(l, mid) <= 0) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    int rmax = lb;

    ret += rmax - rmin + 1;
  }

  cout << ret << endl;
  return 0;
}

ferinの競プロ帳

競プロについてのメモ

SRM688 div1 easy ParenthesesDiv1Easy

考えたこと

ソースコード

SRM687 div1 easy AlmostFibonacciKnapsack

考えたこと

ソースコード

SRM686 div1 easy BracketSequenceDiv1

考えたこと

ソースコード

SRM685 div1 easy MultiplicationTable2

考えたこと

ソースコード

codeforces #433 div2 D. Jury Meeting

考えたこと

ソースコード

codeforces #433 div2 C. Planning

考えたこと

ソースコード

codeforces #361 div2 D. Friends and Subsequences

解法

ソースコード