Typical DP Contest G : 辞書順

問題リンク : G: 辞書順 - Typical DP Contest | AtCoder
問題概要 :
文字列sと自然数Kが与えられる
sから得られる連続でない部分文字列のうち、辞書順でK番目のものを求めよ

解法 :
他の人のブログを参考に解いたので、
コードにある通り

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;



ll K,dp[1000100][30]; // dp[i][j] := 場所iで文字jを使う数
string s;

int compute() {
  for(int i=(int)s.size()-1;i>=0;i--) {
    for(char c='a';c<='z';++c) {
      if( s[i] == c ) {
	dp[i][c-'a'] = 1; // c単体
	for(char h='a';h<='z';h++) { // 既にi番目にcを置いたので後に何が来ても良い
	  dp[i][c-'a'] += dp[i+1][h-'a'];
	  if( dp[i][c-'a'] > K ) { // 愚直に計算するとlong longでも計算できないのでK以上はK+1にまとめる
	    dp[i][c-'a'] = K + 1LL;
	    break;
	  }
	}
      } else {
	dp[i][c-'a'] = dp[i+1][c-'a']; // s[i]はcではないためiより前に置いたものを使う
      }
    }
  }
  {
    ll sum = 0;
    rep(i,26) {
      sum += dp[0][i];
      if( sum >= K ) break;
    }
    if( sum < K ) return puts("Eel");
  }

  string answer = "";
  rep(i,(int)s.size()) {
    for(char c='a';c<='z';c++) {
      if( dp[i][c-'a'] == 0 ) continue;
      if( K > dp[i][c-'a'] ) { // i番目にcを置いてもKには到達しないので使わない
	K -= dp[i][c-'a'];
      } else { // 初めて K <= dp[i][c-'a'] となった場所なのでcを使う必要がある
	answer += string(1,c);
	while( s[i++] != c ); --i; // s[i] != c なら s[i] == c であるような場所まで進まなければいけない
	--K; 
	break;
      }
    }
    if( !K ) break;
  }
  cout << answer << endl;
}

int main() {
  cin >> s >> K;
  compute();
  return 0;
}

UVa 1577 : Low Power

問題リンク :
https://uva.onlinejudge.org/external/15/1577.pdf

問題概要 :
n台のマシーンがある
各マシーンは２つの回路を持っていて、
各回路はk個のバッテリーを持っている
つまり、全てのマシーンにバッテリーをセットするためには2*n*k個のバッテリーが必要となる
また、バッテリーのパワーは整数として表される
各マシーンにバッテリーをセットしたい
マシーンにバッテリーをセットすると、２つの回路内のバッテリーのパワーの最小値の差分が出力される
各マシーンが出力する値の最大値を最小化するようにバッテリーをマシーンにセットし、その値を出力せよ

解法 :
二分探索
バッテリーはパワーが小さい順にソートしておく
二分探索で最大値の最小値xを決める
xを決めたとき、最大値の最小値がx以下になるようにバッテリーをセットできるかチェックする
これは前から貪欲に回路の最小値のペアを作っていくことでチェックできる
バッテリーのうち一番小さい値は必ず回路の最小値となる
その値の次の値と差分をとったときに、差分がx以下ならそれらを２つの回路の最小値とする
そうでないなら今一番小さい値は前の回路のいずれかに入れてしまう

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,k,p[1000100];

bool check(int maxi_diff) {
  int remain = 0;
  int pair_cnt = 0;
  rep(i,2*n*k) {
     //iとi+1を回路の最小値とする
     //iとi+2を最小値のペアとしないのは、そうした場合i+1がi+3以降とペアになる必要がでてきて、
     //i+2が存在しない分だけその差分が離れてしまうから、それだったらiとi+1をペアにしたほうが良い
    if( pair_cnt < n && i+1 < 2*n*k && p[i+1]-p[i] <= maxi_diff ) {
      remain += ( k - 1 ) * 2;
      ++pair_cnt, ++i;
    } else {
      if( remain ) --remain;
      else         return false;
    }
  }
  return true;
}

void compute() {
  sort(p,p+2*n*k);
  int L = 0, R = p[2*n*k-1]-p[0];
  while( L + 1 < R ){
    int M = ( L + R ) / 2;
    if( check(M) ) R = M;
    else           L = M;
  }
  if( check(L) ) printf("%d\n",L);
  else if( check((L+R)/2) ) printf("%d\n",(L+R)/2);
  else printf("%d\n",R);
}

int main() {
  while( scanf("%d %d",&n,&k) != EOF ) {
    rep(i,2*n*k) scanf("%d",p+i);
    compute();
  }
  return 0;
}

UVa 13039 : Fibonacci Triangle

問題リンク :
https://uva.onlinejudge.org/external/130/13039.pdf

問題概要 :
1番目のフィボナッチ数を2, 2番目のフィボナッチ数を３とする
i番目のフィボナッチ数と同じ長さの線分がそれぞれa[i]個存在する
これらの線分を使って作れる三角形の本数の最大値を求めよ

解法 :
これもlaycrsさんの解説をみて解いた

三角形のうち一番長い線分の長さをF、Fの１つ前のフィボナッチ数の長さをF1とする
この時に考えられる三角形の構成は次のとおり

1. F が３本
2. F が２本 + なんでも良いので１本
3. F が１本 + F1が２本

短い線分から順番に三角形を作っていくことを考えたとき、
最大の辺の長さより前のものをできる限り消費したいので、
3,2,1の順番で三角形を作っていくとよい

コード:

nclude<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int main() {
  int T;
  cin >> T;
  while( T-- ) {
    int n;
    cin >> n;
    vector<ll> vec(n);
    rep(i,n) cin >> vec[i];
    ll sum = 0, prev = 0;
    rep(i,n) {
      while( i-1 >= 0 && vec[i] && vec[i-1] >= 2LL ) {
        vec[i-1] -= 2LL, prev -= 2LL, --vec[i];
        ++sum;
      }
      while( prev && vec[i] >= 2LL ) {
        vec[i] -= 2LL, --prev;
        ++sum;
      }
      while( vec[i] >= 3LL ) {
        vec[i] -= 3LL;
        ++sum;
      }
      prev += vec[i];
    }
    cout << sum << endl;
  }
  return 0;
}

UVa 13036 : Birthday Gift to SJ - 2

問題リンク :
https://uva.onlinejudge.org/external/130/13036.pdf

問題概要 :
フィボナッチ数の積として表されるような数で、a以上b以下のものの最大値を求めよ

解法 :
laycrsさんの解説を読んで解いた
フィボナッチ数のうち2から89までを前半、それ以降を後半として列挙する
前半のフィボナッチ数を入れた配列をX、後半のフィボナッチ数を入れた配列をYとする
Xの各要素について、b/X[i]となるようなYの最大値を求める

これでも結構時間がかかるので、
素因数分解した時に、全て他のフィボナッチ数で表されるようなものは配列から除外した(8と144だけかな

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll MAX = 1000000000000000000LL;

vector<ll> sasami_san_kawaii(vector<ll> vec) {
  vector<ll> S;
  S.push_back(1);
  rep(i,(int)vec.size()) {
    ll coef = vec[i];
    vector<ll> tmp = S;
    tmp.push_back(coef);
    rep(j,(int)S.size()) {
      ll v = S[j];
      while( v <= v * coef && v * coef <= MAX ) {
        v *= coef;
        tmp.push_back(v);
      }
    }
    S = tmp;
  }
  S.erase(S.begin());
  sort(S.begin(),S.end());
  S.erase(unique(S.begin(),S.end()),S.end());
  return S;
}


int main() {

  vector<ll> X,Y;
  {
    vector<ll> fib1,fib2;
    fib1.push_back(2);
    fib1.push_back(3);
    fib1.push_back(5);
    fib1.push_back(13);
    fib1.push_back(21);
    fib1.push_back(34);
    fib1.push_back(55);
    fib1.push_back(89);

    fib2.push_back(233);
    fib2.push_back(377);
    while( 1 ) {
      int size = (int)fib2.size()-1;
      ll tmp = fib2[size] + fib2[size-1];
      if( tmp > MAX || tmp < 0 ) break;
      fib2.push_back(tmp);
    }
    X = sasami_san_kawaii(fib1);
    Y = sasami_san_kawaii(fib2);
  }
  int T;
  cin >> T;
  while( T-- ) {
    ll a,b;
    cin >> a >> b;
    ll maxi = -1LL;
    rep(i,(int)Y.size()) {
      if( Y[i] < a ) continue;
      if( Y[i] > b ) break;
      maxi = max(maxi,Y[i]);
      if( maxi == b ) break;
    }
    rep(i,(int)X.size()) {
      if( X[i] < a ) continue;
      if( X[i] > b ) break;
      maxi = max(maxi,X[i]);
      if( maxi == b ) break;
    }
    
    rep(i,(int)X.size()) {
      if( X[i] > b ) break;
      if( a <= X[i] && X[i] <= b ) maxi = max(maxi,X[i]);
      if( maxi == b ) break;
      ll v = b / X[i];
      if( v < 233LL ) continue;
      
      int pos = lower_bound(Y.begin(),Y.end(),v) - Y.begin();
      if( 0 <= pos && pos < (int)Y.size() && Y[pos] > v ) --pos;
      if( pos < 0 || (int)Y.size() <= pos ) continue;
      maxi = max(maxi,X[i] * Y[pos]);
    }
    cout << maxi << endl;
  }
  return 0;
}

Typical DP Contest F : 準急

問題リンク：

F: 準急 - Typical DP Contest | AtCoder

解法：
dp[i] := i番目の駅に停まらない数 = dp[max(0,i-K)] + ... + dp[i-1]
初期値は dp[0] = 1, dp[1] = 0
また、dp[N] = 0
dp[1]=dp[N]=0は、必ずその駅にとまることを意味する
dp[i]は
max(0,i-K)駅では停車せず、開区間(max(0,i-K),i)の各駅で停車する総数と
....
(i-2)駅では停車せず、(i-1)駅で停車する総数と
閉区間[max(0,i-K),i]のどの駅にも停車しない総数の和として表される
愚直に数えると間に合わないのでdpの総和を持っておく

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll mod = 1000000007LL;
const int MAX = 1000010;
ll dp[MAX];
int N,K;

int main() {
dp[0] = 1;
dp[1] = 0;
cin >> N >> K;
/*-- debug
REP(i,2,N+2) {
if( i == N ) { dp[i] = 0; continue; }
for(int j=max(0,i-K);j<i;j++) {
( dp[i] += dp[j] ) %= mod;
}
}
cout << dp[N+1] << endl;
debug -- */

ll sum = 1;
REP(i,2,N+2) {
if( i == N ) {
dp[i] = 0;
} else {
dp[i] = sum;
( sum += dp[i] ) %= mod;
}
if( i - K >= 0 ) { sum -= dp[i-K]; while( sum < 0LL ) sum += mod; }
}
cout << dp[N+1] << endl;
return 0;
}

Typical DP Contest E : 数

問題リンク : E: 数 - Typical DP Contest | AtCoder

解法 :
桁DP
dp[桁][余り][現在の桁までがNのこの桁までと一致しているか] := 総数

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

const ll mod = 1000000007LL;
ll D,dp[10010][110][2]; // dp[桁][余り][Nとぴったりか] := 総数
string N;

void compute() {
  reverse(N.begin(),N.end());
  dp[(int)N.size()][0][1] = 1LL;
  for(int i=(int)N.size();i>=1;i--) {
    for(ll remain=0;remain<D;remain++) {
        rep(sameN,2) {
          rep(digit,10) {
            ll new_remain = (remain + (ll)digit) % D;
            if( sameN && digit > ( N[i-1] - '0' ) ) continue;
            int new_sameN = sameN;
            if( sameN && digit < ( N[i-1] - '0' ) ) new_sameN = 0;
            ( dp[i-1][new_remain][new_sameN] += dp[i][remain][sameN] ) %= mod;
          }
      }
    }
  }
  cout << ( dp[0][0][0] + dp[0][0][1] -1LL + mod ) % mod << endl;
}

int main() {
  cin >> D >> N;
  compute();
  return 0;
}

AOJ 2607 : Invest Master

問題リンク : Invest Master | Aizu Online Judge

問題概要：
n日間の株価の情報が与えられる
初日にx円所持しているので、株の売買を行い最終日の所持金を最大化せよ
株の売買に手数料はかからないものとする
また、最終日の所持金の最大値は高々１０＾５である

解法：
動的計画法
最終日の所持金の最大値は高々１０＾５なので途中にその金額より大きくなることはない
また、株の売買に手数料はかからないため、その日に買った株をその日に売っても損しない
このことから、一日ごとの所持金の最大化をすればよい
dp[i] := 現在i円持っているときの翌日の所持金の最大値

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,d,x,p[11][11],dp[100010];//??


int main() {
  cin >> n >> d >> x;
  rep(i,d) rep(j,n) cin >> p[i][j];
  int maxi = x;
  rep(day,d-1) {
    memset(dp,0,sizeof(dp));
    rep(i,maxi+1) dp[i] = i;
    int tmp = maxi;
    rep(i,n) {
      REP(j,p[day][i],maxi+1) {
        dp[j] = max(dp[j],dp[j-p[day][i]]+p[day+1][i]);
        tmp = max(tmp,dp[j]);
      }
    }
    maxi = tmp;
  }
  cout << maxi << endl;
  return 0;
}