せかいの世界(備忘録)

音楽・ITに関する色々なものを触ってみたり、競プロの記録を残したりします。

ABC190 F - Shift and Inversions

問題

atcoder.jp

解法

  • k=0における転倒数はBITで求められる。
  • $a_i$にkを足してmodNをとるという操作は、数列の先頭の要素が削除されて最後尾に追加されるという操作と等しい。
  • $a_i$ が削除されると転倒数が$a_i$減り($a_i$を転倒数として数えられるのは、0から$a_i-1$までなので)、最後尾に追加すると転倒数が$N-1-a_i$増える。そのため、各kにおける転倒数はO(1)で求められる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())

using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
}

template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};


int main() {
  int n;
  cin >> n;
  vi a(n);
  rep(i,n)cin >> a[i];
  BIT<ll> bit(n);
  ll cnt = 0;
  rep(i,n){
    cnt+=i-bit.sum(a[i]);
    bit.add(a[i],1);
  }
  rep(k,n){
    print(cnt);
    cnt = cnt-a[k]+n-1-a[k];
  }
  return 0;
}

競プロ典型90問 008 - AtCounter(★4)

問題

https://atcoder.jp/contests/typical90/tasks/typical90_h

解法

DPで解く。基本的な考え方はナップサック 問題と同じで、dp[i][j]:=i番目まで見て、状態jとなる個数の数え上げとする。
文字列t="atcoder"とした時、遷移先は以下の2通り。

  • dp[i+1][j]+=dp[i][j]
  • dp[i+1][j+1]+=dp[i][j] (if s[j] == t[j])

コード

mint dp[101010][8];

string t = "atcoder";
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  dp[0][0] = 1;
  rep(i,n){
    rep(j,8){
      dp[i+1][j]+=dp[i][j];
      if(s[i]== t[j])dp[i+1][j+1]+=dp[i][j];
    }
  }
  cout<<dp[n][7].x<<endl;
  return 0;
}

DDCC2020_qual D - Digit Sum Replace

問題

atcoder.jp

解法

  • 各桁をどの順番で足し合わせても答えは変わらない
  • 桁を2つ選んで足し合わせたとき、繰り上がりが起きない場合は桁が一つ減り、起きる場合は桁はそのままで桁和が9減る。
  • 桁上がりが起きる回数は(桁和-1)/9回

コード

int main(){
  int n;
  cin >> n;
  ll digit = 0, sum = 0;
  rep(i,n){
    ll d,c;
    cin >> d >> c;
    digit+=c;
    sum+=d*c;
  }
  cout<<(sum-1)/9 + (digit-1)<<endl;
}

SoundHound C - Ordinary Beauty

問題

atcoder.jp

解法

  • 数列の要素が隣り合うm-1か所について、数字の差がdになる確率を考える。
  • 2個のサイコロを振って差がdになる確率は、
\displaystyle{

  \begin{cases}
    \frac{n}{n^2}  & (d = 0)\\
    \frac{2(n-d)}{n^2} & ( d > 0)
  \end{cases}

}
  • どの箇所も確率は等しいので、上記で求めた確率をm-1倍する。

コード

int main() {
  ll n,m,d;
  cin >> n >> m >> d;
  double ans = 0;
  if(d == 0) ans = 1/(double)n;
  else ans = 2*(n-d)/(double)(n*n);
  ans*= (m-1);
  printf("%.10lf\n",ans);
  return 0;
}

ABC140 E - Second Sum

問題

atcoder.jp

解法

  • 範囲を列挙してそこに含まれる2番目に大きい数を探すのではなく、順列の値X[i]それぞれに対してX[i]が2番目に大きくなるような範囲を数え上げる
  • X[i]より大きい値を一つだけ含み、j<=iとなる最小値jを求める。また、X[i]より大きい値を一つも含まず、i<=kとなる最大値kを求める。
  • また、X[i]より大きい値を一つだけ含み、i<k'となる最大値k'を求める。また、X[i]より大きい値を一つも含まず、j'<=iとなる最小値j'を求める。
  • jk+j'k'がX[i]が2番目に大きくなるような範囲の数になる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())

using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
}

int main() {
  int n;
  cin >> n;
  vi a(n), idx(n);
  rep(i,n){
    cin >> a[i];
    a[i]--;
    idx[a[i]]=i;
  }
  set<int> s;
  ll ans = 0;
  for(ll x = n-1;x>=0;x--){
    int i = idx[x];
    s.insert(i);
    vi l(2,-1);
    vi r(2,n); 

    auto it_l = s.find(i);
    rep(j,2){
      if(it_l == s.begin())break;
      it_l--;
      l[j] = *it_l;
    }
    
    auto it_r = s.find(i);
    rep(j,2){
      it_r++;
      if(it_r == s.end())break;
      r[j] = *it_r;
    }

    vl cntL(2), cntR(2);
    cntL[0] = i-l[0];
    cntL[1] = l[0]-l[1];
    cntR[0] = r[0]-i;
    cntR[1] = r[1]-r[0];
    ans+= (x+1)*(cntL[0]*cntR[1] + cntL[1]*cntR[0]); 
  }
  cout<<ans<<endl;
  return 0;
}

ARC110 C - Exoswap

問題

atcoder.jp

解法

  • 各数字を目的の位置に移動させるためには、素直にswapするしかない。
  • 1から順番にswapしていけばいい。いくら他の数字をswapしていも、結局1を1番目にするという操作は必要。
  • 得られた操作手順を確認し、重複がある場合やちょうどn-1回でない場合は-1を返す。

コード

int main() {
  int n;
  cin >> n;
  vi p(n), ip(n), flag(n, 0), ans;
  rep(i, n) {
    cin >> p[i];
    p[i]--;
    ip[p[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    for (int j = ip[i]; j > i; j--) {
      ip[p[j - 1]]++;
      ip[p[j]]--;
      swap(p[j], p[j - 1]);
      ans.push_back(j);
    }
    if (sz(ans) >= n) {
      cout << -1 << endl;
      return 0;
    }
  }
  rep(i, n) {
    if (p[i] != i) {
      cout << -1 << endl;
      return 0;
    }
  }
  if (sz(ans) != n - 1) {
    cout << -1 << endl;
    return 0;
  }
  for (auto e : ans) {
    if (flag[e]) {
      cout << -1 << endl;
      return 0;
    }
    flag[e] = 1;
  }
  for (auto e : ans) cout << e << endl;
  return 0;
}

ABC137 E - Coins Respawn

問題

atcoder.jp

解法

  • ゲーム開始からの経過時間をT分として T×P枚のコインの支払いが要求される→一回の移動で獲得できるコインの枚数をすべて-Pすればよい。
  • 獲得できるコインの枚数を負にした値を移動コストと考えれば、最短経路問題となる。
  • 頂点1からNまでを移動する経路の中に負の閉路があると、無限ループとなり最大値が求まらない。逆に言うと、それらの経路の外にあるような負の閉路は無視していい。 →DFSで頂点1, 頂点Nの両方ともから到達できない頂点は無視する。
  • 負のコストを持つグラフの最短経路をベルマンフォード法で求める。

コード

template <class T>
void print(vector<vector<T>>& df) {
  for (auto& vec : df) {
    print(vec);
  }
}

struct edge {
  int from;
  int to;
  ll cost;
};

vector<edge> G[3000];
vi to[3000], rto[3000];
bool ok[2][3000];

void dfs(int u, int r) {
  if (ok[r][u]) return;
  ok[r][u] = true;
  if (r == 0) {
    for (auto v : to[u]) {
      dfs(v, r);
    }
  } else {
    for (auto v : rto[u]) {
      dfs(v, r);
    }
  }
}

int main() {
  int n, m, p;
  cin >> n >> m >> p;
  vl dist(n, (ll)1e10);
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    c -= p;
    edge e;
    e.to = b;
    e.cost = -c;
    G[a].push_back(e);
    to[a].push_back(b);
    rto[b].push_back(a);
  }

  dfs(0, 0);
  dfs(n - 1, 1);

  bool updated = true;
  int step = 0;
  dist[0] = 0;
  while (updated) {
    updated = false;
    rep(u, n) {
      for (auto e : G[u]) {
        int v = e.to;
        int cost = e.cost;
        if (!(ok[0][u] && ok[1][u])) continue;
        if (!(ok[0][v] && ok[1][v])) continue;
        int d = dist[u] + cost;
        if (dist[v] > d) {
          updated = true;
          dist[v] = d;
        }
      }
    }
    step++;
    if (step > n) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << max(0LL,-dist[n - 1]) << endl;
  return 0;
}