ありよりのあり

\主に競プロ備忘録/

Typical DP Contest F - 準急

問題概要

ある路線には駅 1 から駅 N までの N 個の駅がある。
準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。
連続する K個以上の駅に止まらないような組み合わせは何通り考えられるか、mod 109+7で求めよ。
2≤K≤N≤106

解法

駅に止まる→1 止まらない→0とすると、1がK個以上連続しないN個のbit列を考えれば良い。
1がK個以上連続しない条件を満たすためには、 i個目に1を置こうとした時、最後に0を置いたのがi-K+2,..,i-1のどこかであり、 i個目に0を置こうとした時、最後に0を置いたのがi-K+1,i-K+2,..,i-1のどこかであれば良い。
すると、dp[i]:=(最後に0を置いたのがi番目であるようなビット列)と考えれば重複なく数え上げられ、漸化式も立てられることがわかる。
この時、1番目、N番目には1を置かなければならないのでdp[1]=dp[N]=0。 また0番目には0があるとして、dp[0]=1とする。
漸化式はdp[i] = sum(i-K+1<=j<=i-1)(dp[j]) (i != 1,N) となる。これを累積和で処理するとO(N)。
i=N+1まで計算すれば、dp[N+1]はN+1に0を置く場合の数で、dp[N]=0としているからN番目には1が置かれていることになる。
よってdp[N+1]は答えと一致する。

メモ

最初O(N2)のdpを考えたがオーダーを落とせなかった。
意外とO(N)の解法を最初から考えた方がよかったかもしれない。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 1000006, MAX_C = 102;
const ll lmod = 1e9+7;

ll sum[MAX_N],dp[MAX_N];

int main(){
  int N,K; cin >> N >> K ;
  sum[1] = dp[0] = 1LL;
  dp[1] = dp[N] = 0LL;
  // sum[i] := [0,i)のdpの和
  REP(i,1,N+2){
    if(i!=1 && i!=N) dp[i] = (sum[i] - sum[max(0,i-K)] + lmod) % lmod;
    sum[i+1] = (sum[i] + dp[i] + lmod) % lmod;
  }
  cout << dp[N+1] << endl;
  return 0;
}

Typical DP Contest E - 数

問題概要

N以下の正整数であって、十進法表記したときの各桁の数の和がDの倍数であるものの個数をmod 1e9+7で求めよ。 1<=D<=102,1<=N<=10104

解法

dp[0][i][j] := (下からi桁までの数で、modがjであるものの数)
dp[1][i][j] := (下からi桁までの数で、modがjかつ各桁がNの同じ桁の数以下のものの数)
とすると、 dp[0][i+1][j']にはdp[0][i][j]から、dp[1][i+1][j']には次置く数(=k)とNの同じ桁の数(=c)によって遷移が決まる。
k>cならば満たさないのでdp[1][i+1][j'] += 0
k=cならばそれまでの桁が条件を満たしていないといけないので dp[1][i+1][j'] += dp[1][i][j]
k<cならばなんでもいいのでdp[1][i+1][j'] += dp[0][i][j]
完全にGrenachaさんの解説見てやったアレ。

メモ

上の桁から考えてしまってdp[1][i][j]が出なかった。
定義の立て方が曖昧な気がする。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 10004, MAX_C = 102;
const ll lmod = 1e9+7;

ll dp[2][MAX_N][MAX_C];

int main(){
    int N,D; string s;
    cin >> D >> s ;
    N = s.size();
    dp[0][0][0] = dp[1][0][0] = 1LL;
    rep(i,N){
        rep(j,D){
            rep(k,10){
                int c = int(s[N-1-i]-'0');
                (dp[0][i+1][(j+k)%D] += dp[0][i][j]) %= lmod;
                (dp[1][i+1][(j+k)%D] += (k>c ? 0LL : dp[k==c][i][j])) %= lmod;
            }
        } 
    }
    cout << dp[1][N][0] - 1LL << endl;
  return 0;
}

COLOCON 2018 D - すぬけそだて――トレーニング――

問題概要

N,X,t[N]が与えられる。 スタミナXを持っていて、単位時間に1回復する。 t[i]にログインできるとして、j(1<=j<=N)回プレイした時に使える最大のスタミナはいくつか、全て出力せよ。 なおゲームをプレイするとその度に使い切るものとする。 1<=N<=3500,1<= X,t[i] <= 109,t[i] < t[i+1]

解法

dp[i][j] := i回プレイして、t[j]に最後にログインした時の使ったスタミナの最大値 (最後にいつログインしたかによって残ってるスタミナが決まるため) とすると、O(N3)のDPが組める。 for i in N
for j in N
dp[i][j] = max_(1<=k<j)(dp[i-1][k]+min(X,t[j]-t[k]))

ただしこれは間に合わない。 遷移はスタミナが満タンになる直前か満タンになった直後のみを考えれば十分なため(解説に詳しく書いてある)、 dp[i][j]からの遷移を考える際には、t[k]-t[j]<=X、すなわちt[k]<=t[j]+Xを満たす最大のkを求め、 k(スタミナが満タンになる直前)とk+1(スタミナが満タンになった直後)への遷移のみを考えれば良い。 コードではind[i]として二分探索で求めている。 t[N]まで行っても最大まで回復しない時は、kが最後になり、k+1はdpからはみ出すので考えなくても良い。

メモ

やっぱりDP弱すぎる。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 5003, MAX_C = 30;
const ll lmod = 1e9+7;

int N; ll X;
ll t[MAX_N],dp[MAX_N][MAX_N];
int ind[MAX_N];

int main(){
    cin >> N >> X ;
    rep(i,N) scanf("%lld",t+i);
    rep(i,N){
        // ind[i] := iからスタミナがXを超えない最大のjを選ぶ
        ind[i] = int(upper_bound(t,t+N,t[i]+X)-t)-1;
    }
    t[N] = 0;
    fill(dp[0],dp[0]+N,X);
    rep(i,N){
        ll _max = 0;
        rep(j,N){
            _max = max(_max,dp[i][j]);
            dp[i+1][ind[j]] = max(dp[i+1][ind[j]],dp[i][j]+min(X,t[ind[j]]-t[j]));
            dp[i+1][ind[j]+1] = max(dp[i+1][ind[j]+1],dp[i][j]+min(X,t[ind[j]+1]-t[j]));
        }
        printf("%lld\n",_max);
    }
  return 0;
}

COLOCON 2018 C- すぬけそだて――ごはん――

問題概要

自然数A,Bが与えられる。 A <= m <= Bなる自然数を選んだ全てが互いに素でなければならないという制約のもと非負整数個選ぶとき、選び方は何通りか。 1 <= A <= B <= 1018 B - A <= 35

解法

全探索して間に合う。その理由は解説参照。 特に6の倍数、その他の2の倍数、3の倍数で分けたりしなくても 全探索の過程で枝が切られるため単純に実装すれば良い。

別解としてA <= m,n <= Bが1でないgcdを持つとき制約から35以下の素数になるため、 prime[11] = {2,3,5,7,11,13,17,19,23,29,31}としてどれを素因数に持つかを11bitで持ち、DPしても良い。 dp[0] = 1 for(m:A<=m<=B) for(bit:1<<11) if(mがbitの素因数を持っていない) dp[bitにmを入れた時の次の状態] += dp[bit] みたいな感じ。O(N*211)。

メモ

反省オブザイヤー。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005, MAX_C = 30;
const ll lmod = 1e9+7;

ll gcd(ll a,ll b){
    //  a >= b
    if(a<b) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}

ll solve(ll a,ll b,vector<ll> &vec){
  if(a>b) return 1LL;
  ll res = solve(a+1,b,vec);
  bool ok = true;
  for(auto c:vec){
    if(gcd(a,c)!=1LL){
      ok=false;
      break;
    }
  }
  if(ok){
    vec.pb(a);
    res += solve(a+1,b,vec);
    vec.pop_back();
  }
  return res;
}

int main(){
    ll A,B; cin >> A >> B ;
  vector<ll> vec;
  cout << solve(A,B,vec) << endl;
  return 0;
}

ARC085 E - MUL

E - MUL

問題概要

整数a1,a2,..,aNが与えられる。 ある自然数kを選び、N以下の全てのkの倍数ik(i>=1)についてa_ik = 0にするという操作が可能な時、 a1,a2,...,aNの総和の最大値を求めよ。 1<=N<=100, |ai| <= 109

解法

MinCutする。 1〜Nの整数をノードとし、S,T2つのノードを加える。 ここで辺をカットしていき、S側にあるものを0にし、T側にあるものを0にしないと決める。 Mincutは最小カットなので、最大値を求めるためにMincutを理想の状態からの最小ペナルティと考える。 理想の状態は正の数だけ取ることだから、ai >= 0なるaiの和を先に求めておく。 ai>=0なるiに対してはT側にあるのが理想であり、逆にS側にあるとaiのペナルティがあるからiからTに対してai(>=0)の辺を張る。 ai<0なるiに対してはS側にあるのが理想であり、T側にあると-aiのペナルティがあるからSからiに対してai(>0)の辺を張る。 またi,j(jはiの倍数)に対して、iがS側、jがT側にあると矛盾するからiからjに対してINFの辺を張る。 逆にiがT側、jがS側の時は矛盾しないのでjからiには辺を張らなくて良い。 以下の条件でグラフを形成しSからTへのMaxFlow = MinCutを求め、理想の状態から引く。

メモ

典型問題らしいが、やるのは初めてだった。 よく見ると蟻本にも書いてあった。 使い方については解説放送と、 診断人さんの神スライドで勉強した。 解答でのiからjに辺を張ってjからiに張らないのがわからなかったのだが、スライドの29ページで理解した。 i -> j のみに辺を張ることでiがS側、jがT側にある時にはMinCutが成立しないようになる。 毎回図を書かないと理解できなさそう。 MaxFlowの実装についてはtubo28さんのDinic法の実装を参考にした。 そのうち自分で実装したい(いつになるんだ)

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 102;
const ll lmod = 1e9+7;

using Flow = ll;

struct Edge {
  int to, from;
  Flow cap;
  Edge(int from, int to, Flow f) : from(from), to(to), cap(f) {}
};

using Graph = vector<vector<Edge>>;

struct Dinic {
    int n, s, t;
    std::vector<int> level, prog, que;
    std::vector<std::vector<Flow>> cap, flow;
    std::vector<std::vector<int>> g;
    Flow inf;
    Dinic(const Graph &graph)
        : n(graph.size()),
          cap(n, std::vector<Flow>(n)),
          flow(n, std::vector<Flow>(n)),
          g(n, std::vector<int>()),
          inf(std::numeric_limits<Flow>::max() / 8) {
        for (int i = 0; i < n; i++) {
            for (auto &e : graph[i]) {
                int u = e.from, v = e.to;
                Flow c = e.cap;
                cap[u][v] += c;
                cap[v][u] += c;
                flow[v][u] += c;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    }
    inline Flow residue(int u, int v) { return cap[u][v] - flow[u][v]; }
    Flow solve(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        Flow res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1);
        level[s] = 0;
        que[r++] = s;
        while (l != r) {
            int v = que[l++];
            if (v == t) break;
            for (const int &d : g[v])
                if (level[d] == -1 && residue(v, d) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = d;
                }
        }
        return level[t] != -1;
    }
    Flow augment(int v, Flow lim) {
        Flow res = 0;
        if (v == t) return lim;
        for (int &i = prog[v]; i < (int)g[v].size(); i++) {
            const int &d = g[v][i];
            if (residue(v, d) == 0 || level[v] >= level[d]) continue;
            const Flow aug = augment(d, std::min(lim, residue(v, d)));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            res += aug;
            lim -= aug;
            if (lim == 0) break;
        }
        return res;
    }
};

int main(){
  int N; cin >> N ;
  Graph g(N+2);
  ll a[MAX_N];
  ll _sum = 0;
  rep(i,N){
    scanf("%lld",a+i);
    if(a[i]>0) _sum += a[i];
  }
  const int S = N,T = N+1;
  rep(i,N){
    if(a[i]<0){
      g[S].pb(Edge(S,i,-a[i]));

    }else{
      g[i].pb(Edge(i,T,a[i]));
    }
  }
  rep(i,N){
    int num1 = i+1;
    for(int num2 = num1*2; num2 <= N; num2 += num1){
      g[num1-1].pb(Edge(num1-1,num2-1,LINF));
    }
  }
  Dinic dn(g);
  cout << _sum - dn.solve(S,T) << endl;
  return 0;
}

DDCC本戦2017 B - GCDロボット

問題概要

N,Z,aiが与えられる。 全てのiについて、gcd(X,a[i])=gcd(Z,a[i])なる最小のXを求めよ。 1<=N<=105,1<=Z,a[i]<=1018

解法

答えから書くと、lcm_(0<=i<N)(gcd(a[i],Z))。 各iについてgcd(a[i],Z)を求めて、それぞれのlcmを求める。 一応lcmは分割統治でやったけど、そうしなくても大丈夫っぽい。 gcd(a,b)はO(log(max(a,b)))なので、 gcdを求めるのがO(Nlog1018) lcmを求めるのがO(logN*log1018)から、 全体でO(Nlog1018)。

メモ

lcm()について、return a*b/gcd(a,b);と書くとオーバーフローする。 すんなり解けたけど証明はできないな...と思ったので解説を見ると、 ベクトルで考えるといいよ、と書いてあってスッキリ。

以下引用

gcd, lcm 系の操作は、整数を (素因数 2 の個数, 素因数 3 の個数, 素因数 5の個数, ...) という無限次元のベクトルに変換すると見通しがよくなることが多いです。 実は、gcd はこのベクトルの各要素について min を取る操作であり、lcm は max を取る操作です。 つまりこの問題は、あるベクトルの列 ai とベクトル X が与えられ、以下の条件を満すベクトル Z を探せ すべての i, j について、min(Xj ,(ai)j ) = min(Zj ,(ai)j ) という問題になります。 明らかにこの条件はベクトルの各要素に対し独立なので、要素ごとに考えると、結局 Zj = max(min(Xj ,(ai)j )) とすれば良いことがわかります。 よってこの操作を元の整数に戻すと、Z = lcm(gcd(X, ai)) となります。

補足すると各要素(j)について、Zjをmax_(0<=i<N)(min(Xj,(ai)j))よりも小さくすると、あるiについて Zj < min(Xj,(ai)j)となるため矛盾するので、Zj = max(min(Xj,(ai)j))が示せる。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005;
const ll lmod = 1e9+7;

int N;
ll Z,a[MAX_N];

ll gcd(ll a,ll b){
  if(a<b) swap(a,b);
  // a >= b
  if(b==0) return a;
  return gcd(b,a%b);
}

ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}

ll solve(int l,int r){
  if(abs(r-l)<=1) return a[l];
  else return lcm(solve(l,(l+r)/2),solve((l+r)/2,r));
}

int main(){
  cin >> N >> Z ;
  rep(i,N) scanf("%lld",a+i);
  rep(i,N) a[i] = gcd(Z,a[i]);
  cout << solve(0,N) << endl;
  return 0;
}

ARC 084 D - Small Multiple

問題概要

Kの正の倍数の10進数での各桁の和として最小のものを求めよ。 2<=K<=105

解法

1を以下の2種類の操作でKの倍数にすることを考える。 1. 1増やす 2. 10倍する この2種類の操作で全ての自然数が作れる。 また、1の位の数が9の時には1を使わないとすると(2を使えばそうする必要はないため)、 各桁の和は1,2の操作で 1. 1増える 2. 変わらない よってmod 0〜K-1のノードを作り、1,2の操作に対応する辺(距離は各々1,0)を張る。 その時mod 1 のノードからmod 0のノードへの最短路+1が答え。 Dijkstra法を用いればO(KlogK)で求められるので十分間に合う。

解説動画を見たらアア…ってなった。

メモ

Kの倍数 -> mod Kのグラフで考える。 知らないと絶対できなさそう。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_K = 100005;
const ll lmod = 1e9+7;

int K;

class edge{
  public:
    ll cost;int to;
  edge(ll cost,int to)
    :cost(cost),to(to){}
};
vector<edge> e[MAX_K];
ll d1[MAX_K];

void dijkstra(int start,vector<edge> graph[],ll d[]){
  priority_queue<Pl,vector<Pl>,greater<Pl>> que;
  fill(d,d+MAX_K,LINF);
  d[start] = 0LL;
  que.push(Pl(0LL,start));
  while(!que.empty()){
    P p=que.top(); que.pop();
    int v=p.second; //行き先
    if(d[v]<p.first)  continue;
    rep(i,graph[v].size()){
      edge e=graph[v][i];
      if(d[v]+e.cost<d[e.to]){
        d[e.to]=d[v]+e.cost;
        que.push(P(d[e.to],e.to));
      }
    }
  }
  return ;
}



int main(){
  cin >> K ;
  rep(i,K){
    e[i].pb(edge(1LL,(i+1)%K));
  }
  REP(i,1,K){
    e[i].pb(edge(0LL,(i*10)%K));
  }
  dijkstra(1,e,d1);
  cout << d1[0] + 1LL << endl;
  return 0;
}