kurarrr's memooo

主に競プロ備忘録

ARC 087 D - FT Robot

AtCoder 競プロ

問題概要

'F'と'T'からなる文字列Sと座標x,yが与えられる. Fは1つ前進,Tは左右いずれかに90°回転の命令を表す.
(0,0),x軸正方向向きからSの命令列を実行した時,(x,y)にいくことができるか。 1<=|S|<=8*103

解法

x,y各方向について,Fの塊のたびに(正規表現的に言うとF+),dp[i] = (iに存在できるかどうか)として,
dp[i+count(F)] = dp[i], dp[abs(i-count(F))] = dp[i]を更新していく。
O(N2)で十分間に合う.

メモ

bitset使って pos = (pos<<i) | (pos>>i)って書くと配列二つ使わずにスマートに書けるっぽい.かっこいい.

コード

#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 = 8003;
const ll lmod = 1e9+7;

int cnt[2][MAX_N];
bool dp[4][MAX_N];

int main(){
  string S; int N,x,y,a;
  cin >> S >> x >> y ;
  N = S.length();
  S = S + "T";
  a = 0;
  while(S[a]=='F') a++;
  x -= a;
  fill(dp[0],dp[0]+MAX_N*4,false);
  int cnt = 0, flag = 0;
  dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = true;
  int xprev = 0 ,xnow = 1 ,yprev = 2 ,ynow = 3;
  REP(i,a,N+1){
    if(S[i]=='F') cnt++;
    else{
      if(cnt!=0){
        int now,prev;
        if(!flag) prev = xprev, now = xnow, swap(xprev,xnow);
        else prev = yprev, now = ynow, swap(yprev,ynow);
        fill(dp[now],dp[now]+N,false);
        rep(i,N+1){
          if(i+cnt<MAX_N) dp[now][i+cnt] |= dp[prev][i];
          dp[now][abs(i-cnt)] |= dp[prev][i];
          // if(dp[now][i+cnt]) cout << "flag = " << flag << ", i+cnt = " << i+cnt << endl;
          // if(dp[now][abs(i-cnt)]) cout << "flag = " << flag << ", i-cnt = " << i-cnt << endl;
        }
      }
      cnt = 0;
      (flag += 1) %= 2;
    }
  }
  cout << (((dp[xprev][abs(x)] && dp[yprev][abs(y)])) ? "Yes" : "No") << endl;
  return 0;
}

ARC088 D - Wide Flip (500)

AtCoder 競プロ 必要条件の列挙

問題概要

ビット列Sが与えられる。K以上の範囲を選んでその区間のSを反転させることができる時、最大のKを求めよ。
1<= |S| <= 105

解法

k文字目のみを変えようとした時、[0,k-1]->[0,k]を反転させることで変えることができる。
同様に[k+1,N]->[k,N]でも変えることができる。
これを使うとS[k]!=S[k+1]の時、前半を使えばk、後半を使えばN-kでS[k]=S[k+1]にできる。
この時、max(k,N-k)が大きい順から(つまり中心に近い方から)どちらかの1文字だけ変化させていくと、Sの全てを揃えることができる。
必要十分なKはS[k]!=S[k+1]なるkのmax(k,N-k)の最小値(K'とする)であることがわかる。
なぜなら、K > K'であればmax(k,N-k)が最小となるS[k],S[k+1]を揃えることができないし、
K<=K'であれば前述のようにSを全て揃えることができるからである。
よって答えはmin_(S[k]!=S[k+1])(max(k,N-k))で求められる。

メモ

解説放送の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>;
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;
const ll lmod = 1e9+7;

string S; int N;

int main(){
  cin >> S ; N = S.length();
  int ans = INF;
  rep(i,N-1){
    if(S[i]!=S[i+1]) ans = min(ans,max(i+1,N-i-1));
  }
  if(ans==INF) ans = N;
  cout << ans << endl;
  return 0;
}

Typical DP Contest F - 準急

AtCoder 競プロ

問題概要

ある路線には駅 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 - 数

AtCoder 競プロ DP 桁DP

問題概要

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 - すぬけそだて――トレーニング――

AtCoder 競プロ

問題概要

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- すぬけそだて――ごはん――

AtCoder 競プロ

問題概要

自然数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

AtCoder 競プロ

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