ありよりのあり

\主に競プロ備忘録/

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

CODE FESTIVAL qual C - D Yet Another Palindrome Partitioning

問題概要

文字列Sが与えられる。 Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。 1 <= |S| <= 2*105

解法

回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」となる。 文字列sに対して以下を満たすようにh(s)を定める。

'a' の出現回数 % 2 -> h(s)の1ビット目 'b' の出現回数 % 2 -> h(s)の2ビット目 .... 'z' の出現回数 % 2 -> h(s)の26ビット目 ここで、h(s) = (0 または 1<<k) (0<=k<26)であればsは回文条件を満たす。

Sに対して、a[i] = h(S[0,i))と定める。 すると、h(S[l,r)) = a[l] ^ a[r] である。

以下のようなDPが組める。以下0<=k<26とする。 opt(i) = min(S[0,i)の分割回数),opt(0)=0として、 opt(i) = min_(0<=j<=i かつ a[j]^a[i]=0 or 1<<k )(opt(j)+1) ただこれはO(N2)なので間に合わない。

ここで, a[j]^a[i] = 0 <-> a[i] = a[j] a[j]^a[i] = 1< a[i] = a[j] ^ (1<<k) cf. (ab)c = abc,aa=0 であることに注目すれば,(すなわち同じか1bitしか変わらない) h(s)を引数とすれば遷移式には26個のminを取れば良いことがわかる。

すなわちdp[x]=min(h(s[0,x))なるsの交換回数)として、 初期状態 dp[0] = 0, 遷移式 dp[x] = min(dp[x],dp[x1<<k]) dp[a[N]]が答えとなる。 ただし、a[N]=0の時dp[a[N]]=1となるので、max(dp[a[N]],1)とする。

メモ

O(N2)っぽい解法は思いついたが書けなかった。 回文条件の言い換えは応用が多そうなので押さえておきたい。 それとxorをスマートに書けるように。 a[0]=a[1<<k]=1として初期化したら通らなかったのだがなぜだろう。

コード

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

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

int dp[1<<26];
int a[MAX_N]; //[0,i)のハッシュ値
int C = 26;
string S;

int main(){
  cin >> S ;
  int N = S.size();
  rep(i,N){
    int b = S[i] - 'a';
    a[i+1] = a[i] ^ (1<<b);
  }
  fill(dp,dp+(1<<26),INF);
  dp[0] = 0;
  REP(i,1,N+1){
    rep(j,C){
      int bit = 1<<j;
      dp[a[i]] = min(dp[a[i]],dp[a[i]^bit]+1);
    }
  }
  cout << max(1,dp[a[N]]) << endl;
  return 0;
}

CODE FESTIVAL qual B - D 101 to 010

問題概要

ビット列Sが与えられる。 "101" -> "010" の変換ができる。最大何回できるか。

解法

dp[i] = (i番目までの文字で最大何回変換できるか) とおく。 変換には二種類あり、もともとある101を変換するか、変換によってできた101を変換するかである。 後者は、101の前または後ろに1が並んでいるケースに限られる。 ex1. 10111 -> 01011 -> 00101 -> 00000 ex2. 11101 -> 11010 -> ... よって101を見つけて、前後に1の列があればその変換から広がるdp[i]の値の変化を追っていけばいいことがわかる。 またSの前後に番兵の'0'を置いておくと末端の処理を書かなくていいので楽。

メモ

DPっぽいというのはわかったが、書けなかった... やるだけとか言えるようになりたい

コード

#include<stdio.h>
#include<iostream>
#include<string>

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

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

int dp[MAX_N];

int main(){
  int N;
  string S;
  cin >> N >> S;
  fill(dp,dp+N,0);
  S = "0" + S + "0";
  REP(i,1,N+1){
    dp[i+1] = max(dp[i],dp[i+1]);
    if(S[i-1]=='1'&&S[i]=='0'&&S[i+1]=='1'){
      int a,b;
      a = i-1;
      b = i+1;
      while(1){
        if(S[a]=='0') break;
        dp[i+1] = max(dp[i+1],dp[a-1]+i-a);
        a--;
      }
      while(1){
        if(S[b]=='0') break;
        dp[b] = max(dp[b],dp[i-2]+b-i);
        b++;
      }
    }
  }
  // rep(i,N+2) cout << dp[i] << ",";
  // cout << "" << endl;
  // rep(i,N+2) cout << S[i] << ",";
  // cout << "" << endl;
  cout << dp[N+1] << endl;
  return 0;
}

蟻本練習問題(反転)

反転

問題訳
20個のビット列が与えられる。1つを反転させると両隣のビットも反転される。
全てを0にするのに必要な反転の最小回数は?

解法
最初のビットを反転するかを決めると、全部決まるので2通り

メモ
配列を初期化するのと最初の反転をカウントするのを忘れていた。

コード

#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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
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;

int a[22],c[22];

int main(){
  rep(i,20) cin >> a[i] ;
  rep(i,20) c[i]=a[i];
  int ans=INF;
  rep(j,2){
    int cnt=0;
    rep(i,20) a[i]=c[i];
    if(j){
      a[0]^=1; a[1]^=1; cnt++;
    }
    rep(i,19){
      if(a[i]==1){
        a[i]^=1; a[i+1]^=1; a[i+2]^=1;
        cnt++;
      }
    }
    if(a[19]==0) ans=min(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

問題訳
5x6のマスがあり、1マスを反転させると隣接4マスも反転するようなパズルがある。
パズルの答えを示せ。(最小回数でなくとも良い)

解法
1行目を決めるとパタパタ決まる。

メモ
またも配列の初期化ミスってしんどいことに…

コード

#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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
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=1002,MAX_K=102;

int a[5][7],c[5][7],ans[5][7];
int dx[5]={0,-1,0,1,0};
int dy[5]={0,0,1,0,-1};

void rev(int i,int j){
  rep(k,5){
    if((i+dy[k]>=0 &&i+dy[k]<5)&&(j+dx[k]>=0 && j+dx[k]<6)){
      c[i+dy[k]][j+dx[k]]^=1;
    }
  }
}

void calc(){
  rep(i,5) rep(j,6) scanf("%d",&a[i][j]);
  bool ok=false;
  rep(i,1<<6){
    rep(j,5) rep(k,6) c[j][k]=a[j][k];
    rep(j,5) rep(k,6) ans[j][k]=0;
    rep(j,6){
      ans[0][j]=(i>>j)&1;
      if(ans[0][j]){
        rev(0,j);
      }
    }
    REP(j,1,5){
      rep(k,6){
        if(c[j-1][k]){
          rev(j,k);
          ans[j][k]=1;
        }
      }
    }
    ok=true;
    rep(k,6){
      if(c[4][k]) ok=false;
    }
    if(DEBUG){
      cout << "cnt" << i << endl;
      rep(k,5){
      rep(j,5) cout << ans[k][j] << " " ;
        cout << ans[k][5] << endl;
      }
      cout << "--------" << endl;
      rep(k,5){
        rep(j,5) cout << c[k][j] << " " ;
        cout << c[k][5] << endl;
      }
      cout  << endl;
    }
    if(ok) break;
  }
  if(ok){
    rep(i,5){
      rep(j,5) cout << ans[i][j] << " " ;
      cout << ans[i][5] << endl;
    }
  }
}

int main(){
  int n;
  cin >> n ;
  rep(i,n){
    cout << "PUZZLE #" << i+1 << endl;
    calc();
  }
  return 0;
}

蟻本練習問題(DP)

基本的な動的計画法

問題訳(かなり意訳)

N(1\leq N \leq 350) 列に1,2,…,N個ずつ三角形でボーリングのピンが並んでいる。
ボーリングのピンには点数 K(0 \leq K \leq 99) がついていて、ボールは三角形の一番上から下の二つの隣接するピンを倒すことができ、一番下に向けて動く。
得られる最大の点数は何点か。

ex.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

この場合だと 7 -> 3 -> 8 -> 7 -> 5 で30点が最高点。

解法
かなりわかりやすい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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
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=351;

int dp[MAX_N][MAX_N],a[MAX_N][MAX_N];

int main(){
  int N;
  cin >> N ;
  rep(i,N){
    rep(j,i+1) scanf("%d",&a[i][j]);
  }
  fill(dp[0],dp[MAX_N-1],-1);
  dp[0][0]=a[0][0];
  rep(i,N-1){
    rep(j,i+1){
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+1][j]);
      dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+a[i+1][j+1]);
    }
  }
  int ans=-1;
  rep(i,N) ans=max(ans,dp[N-1][i]);
  cout << ans << endl;
  return 0;
}

問題訳
自然数 N(1\leq N \leq 10^{6}) が与えられる。
Nを 2^{k} (k \geq 0) の和だけで表す方法は何通りあるか。

解法 まず書き出してみる。
1=1 …1
2=2=1+1 …2
3=1+2,1+1+1 …2
4=4=2+2=1+1+2=1+1+1+1 …4
5=1+(4の表し方) …4
Nの組み合わせ数をdp[N]とすれば、N=奇数の時 dp[N]=dp[N-1]は容易に得られる。
なぜならNは奇数であるため、和で表した時少なくとも1つ、1が入るためである。
一方、Nが偶数であれば1を一つも使わずに表すことができるため、これは成り立たない。
しかし、その時は分解した和が全て偶数だからN/2を和で表したものを2倍したものと考えることができる。 よって、

$$ dp[n]=\begin{cases} dp[n-1] & (n=odd) \\ dp[n-1] + dp[n/2] & (n=even) \end{cases} $$

#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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=1e7;

ll dp[MAX_N];

int main(){
  int N;
  cin >> N ;
  dp[1]=1;
  REP(i,2,N+1){
    if(i%2) dp[i]=dp[i-1]%int(mod);
    else dp[i]=(dp[i/2]+dp[i-1])%int(mod);
  }
  cout << dp[N] << endl;
  return 0;
}

問題訳
毎秒、木1と木2のどちらかからりんごが落ちてくる。牛のベシーは木の真下にいればりんごをキャッチすることができる。
最大移動回数W(1\leq W \leq 30)回の元で、T(1\leq T \leq 1000)秒間の間に最大何個のりんごを得られるか。

解法
i秒後、j回移動して得られる最大のりんごの数をdp[i][j]とする。
今どちらかにいるかは j%2 +1 で得られる。 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])と、
今いる場所に落ちてくるなら dp[i][j]++ を繰り返せば答えが得られる。
木をN本に拡張してもできそう。その場合は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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_T=1002,MAX_W=31;

int dp[MAX_T][MAX_W];

int main(){
  int T,W;
  cin >> T >> W ;
  fill(dp[0],dp[T+1],0);
  REP(i,1,T+1){
    int fall;
    cin >> fall ;
    rep(j,W+1){ 
      if(j>0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
      else dp[i][j]=dp[i-1][j];
      int now = j%2+1;
      if(now==fall) dp[i][j]++;
    }
  }
  int ans=-1;
  rep(j,W+1) ans=max(ans,dp[T][j]);
  cout << ans << endl;
  return 0;
}

問題訳 次のN時間で最大の牛乳を得られるようにしたい。
搾乳することができる時間はM区間あり、それぞれでs_iからe_iまで時間がかかり、effi_iだけ牛乳が得られる。
また、牛は一回搾乳をするごとにR時間休ませる必要がある。(つまりi個目の区間で搾乳をするとe_i+Rから搾乳を再開できる)

入力
N M R
s_1 e_1 effi_1
. .
s_M e_M effi_M

$$ 1\leq R \leq N \leq 10^{6}
1 \leq M \leq 10^{3}
1 \leq s_i \leq e_i \leq N
1 \leq effi_i \leq 10^{6}
$$

解法区間を開始時間でソートする。
区間に関するDPを立てて解く。
dp[i] := (i番目以降の区間を用いた場合の最大搾乳量)とする。
i番目の区間で搾乳をしないとすると、dp[i+1]だけ搾乳できる。
搾乳をするならば、開始時間がe_i+R以上になるような最小の数をj\leq iとすれば、
dp[j]+effi_i だけ搾乳することができる。そのようなjは二分探索で発見できる。
よって dp[i]=max(dp[i+1],dp[j]+effi_i)
求める答えはdp[0]
計算時間は検索で二分探索を用いているのでO(MlogM)。 M〜103なので二分探索を用いなくても間に合う。

メモ
何に関するDPを立てるのかパッと思いつかなかった。Nでやるとちょっと怖そうだしなーと。
Nに関するDPでもできるっぽい
POJ-3616 : Milking Time
後ろからやるの、思いつかない。

#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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_M=1002;

vector<pair<P,ll>> term;
ll dp[MAX_M];

int main(){
  int N,M,R;
  cin >> N >> M >> R ;
  term.resize(M);
  rep(i,M){
    int s,e;
    ll ef;
    scanf("%d%d%lld",&s,&e,&ef);
    term[i].first.first = s;
    term[i].first.second = e;
    term[i].second = ef;
  }
  sort(ALL(term));
  dp[M-1] = term[M-1].second;
  for(int i=M-2;i>=0;i--){
    pair<P,ll> temp;
    temp.first.first = term[i].first.second+R;
    temp.first.second = -1;
    int _m = lower_bound(term.begin(),term.end(),temp) - term.begin();
    if(_m==M) dp[i] = max(dp[i+1],term[i].second);
    else dp[i] = max(dp[i+1],dp[_m]+term[i].second);
  }
  cout << dp[0] << endl;

  return 0;
}
  • POJ3280 – Cheapest Palindrome
    N種類のアルファベットからなるM字の文字列が与えられる。
    各アルファベットの追加と削除のコストが与えられた時、文字列を回文にするためのコストを求めよ。
    input
    N M
    S(M文字の文字列)
    a (aを追加するコスト) (aを削除するコスト)

    (M番目のアルファベット) (追加するコスト) (削除するコスト)
     1 \leq N \leq 26 , 1 \leq M \leq 2*10^{3}, 1\leq cost \leq 10^{4}

解法
区間DP。
dp[i][j] := [i,j)を回文にするコストとする。
すると
S[i] = S[j-1] のとき S[i][j] = min(dp[i][j-1] + cost[S[j-1]] , dp[i+1][j] + cost[S[i]] , dp[i+1][j-1])
そうでないとき S[i][j] = min(dp[i][j-1] + cost[S[j-1]] , dp[i+1][j] + cost[S[i]] )
である。これを(i,j) = (0,2),(1,3),..,(M-2,M), (0,3),…,(M-3,M),…,(0,M)と回していけば良い。
dp[i][i+1] = 0 (1文字でもともと回文のため)
求める答えは dp[0][M]。計算量はO(M2)

メモ
区間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>

#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;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60,lmod=1e9+7;
const int MAX_N=2003;

ll dp[MAX_N][MAX_N];
map<char,ll> cost;

int main(){
  int N,M;
  cin >> N >> M ;
  string S;
  cin >> S ;
  rep(i,N){
    char c;
    ll a,b;
    cin >> c >> a >> b ;
    cost[c] = min(a,b);
  }
  fill(dp[0],dp[MAX_N-1],0);
  REP(j,2,M+2) REP(i,0,M-j+2) {
    ll temp = min(dp[i][i+j-1]+cost[S[i+j-1]],dp[i+1][i+j]+cost[S[i]]);
    if(S[i]==S[i+j-1]) dp[i][i+j] = min(temp,dp[i+1][i+j-1]);
    else dp[i][i+j] = temp;
    //cout << i << ","<< i+j << ":" << dp[i][i+j] << endl;
  }
  cout << dp[0][M] << endl;
  return 0;
}

参考
基本的な動的計画法(5題)
大いに参考にさせていただきました…