ありよりのあり

\主に競プロ備忘録/

Educational Codeforces Round 38 D. Buy a Ticket

問題概要

N頂点M辺の無向グラフと各辺の距離が与えられる.
また各頂点に対してコストc[i]が与えられる.
各i (1<=i<=N)に対し min_j(2dist(i, j)+c(j))を求めよ.
2 <= N <= 2
105, 1 <= M <= 2*105

解法

Dijkstraで各頂点とそのコストを初期位置としてキューに入れると,
各頂点に対し各(始点のコスト)+(始点からの距離)を更新していくので解ける.

メモ

始点複数のDijkstraを初めて見たのでできなかった. 言われて見ると,そうだね,という感じ.
オーダーがすごく見積もりにくい気がするのだけどまあO(E+Vlog(V))かな
こういうタイプは無向グラフには使えないので注意.
一回やってれば解けそう.

コード

Educational Codeforces Round 38 C. Constructing Tests

問題概要

0,1からなる行列で,どのMxMの小行列をとってもいずれかの要素に0が含まれる行列をM-free Matrixという.
整数xが与えられ,1の要素数を最大化したNxNのM-free Matrixで,1の要素数がxであるようなN,Mを答えよ.
というクエリがt個与えられるので各々出力せよ.
1 <= x <= 109, 1 <= t <= 100

解法

NxN行列に対して左上から重ならないようにMxMの小行列を取っていけば求めるN,Mが
N2 - (floor(N/M))2 = x を満たしていれば良いことがわかる.
S = floor(N/M)とすると, x<=109 から N<=105ほどまで全探索すれば十分であることがわかる.
(正確には floor(N/M) ~ N/M として評価すれば上から挟める)

N,Sを見つければ,floor(N/M) = S なるMが存在するかという問題を解けば良い.
これは M=floor(N/S)として上の式を満たすかどうかを確かめれば十分であり,満たさなければ他の解を探索する.
厳密には, N = SM + k (0<=k<M)と表されるので,
S
M <= N < (S+1)M <-> N/(S+1) <M <= N/S (1) から,
floor(N/(S+1)) < floor(N/S) であれば良い(*1の範囲が整数を跨いでいる)
そのようなMは複数あるかもしれないが,存在する場合はN/Sで十分となる.

メモ

難しく考えすぎて解けなかった..

コード

ARC 058 E - 和風いろはちゃん / Iroha and Haiku

問題概要

整数N,X,Y,Zが与えられる.
整数1〜10から成り,XYZを含む要素数Nの数列をmod1e9+7で求めよ.
なお{a_i}がXYZを含むとは
sum(x<=i<y)(a_i) = X, sum(y<=i<z)(a_i) = Y, sum_(z<=i<w)(a_i) = Z
を満たす 0 <= x < y < z < w <= N が存在することとする.
1 <= N <= 40, 1 <= X,Z <= 7, 1 <= Y <= 5

解法

数え上げDP.
数列{a}に対し全単射写像f({a})が存在すれば,各0<=i<N,f({a}),1<=k<=10に対し
dp[i+1][f({a}+{k})] += dp[f({a})] とすると, O(10N*size(f))で求められる.

問題はこの写像をどう定義するか. 単に数列を並べたもの,もしくは数列自体にするとsize(f)=10Nとなりとても終わらない.
この問題だと末尾から和がX+Y+Z-1以下になるような部分だけを覚えておけばいいことがわかる.
ex. X,Y,Z = 5,7,5 , {a} ={1,3,4,4,1,1,6,2}だと {4,1,1,6,2} の部分.
これは 1 = 1, 2 = 10, 3 = 100,..とすればうまくいく.
ex. f({1,2,3}) = 110100となる
X+Y+Z-1以下だけ見ていけば良いので, size(f) = 2X+Y+Z-1 になる.
下からX+Y+Z,Y+Z,Zのビットが立っているようなものがXYZを含む数列になるので,
そのようなものを数え上げる.(コードだとjインデックスの最後に置いている)
この写像の立て方をしなくても,このような数列に対しインデックスをつけて下処理すればできるっぽい kmjpさんのブログ

メモ

和の通り数をコンビネーションで解こうとして無理だった.
(数え上げDPの典型処理ができなかった.)

コード

ARC 081 E - Don't Be a Subsequence

問題概要

英小文字から成る文字列Sが与えられる.
Sの部分列でないような最短の文字列を求めよ.
ここでS'がSの部分列とは S'[i] = S[a_i] (1<=i<=|S'|) なる単調増加なa_iが存在するものとする.

解法

まず,S[i,N)で一番最初に出てくる文字j(j='a'〜'z')を後ろから見て行き,c[i][j]とする.
dp[i] := S[i,N) の部分列の最短長さ とすれば,
先頭にjを使って文字列を作る場合は dp[c[i][j]+1]+1 となるから
dp[i] = min_j( dp[c[i][j]+1] + 1) で後ろから遷移していけば求められる.
c[N][j] = N, dp[N] = 1, dp[N+1] = 0 に注意する.
もうその文字がない場合はi=Nとし,それに対応するのがdp[N+1] = 0,
また空文字列に対する答えは'a'としてdp[N] = 1.

dp[i] が求められれば前から dp[i] = dp[c[i][j]+1] + 1であるようなjをaから見て行き,
そのようなjを連結して出力すれば良い.

メモ

文字列に関するDPに不慣れだったのと,逆に辿っていくのに時間がかかった.

コード

第3回ドワコン予選 D - ネタだけ食べたい寿司

問題概要

{X_i},{Y_i} (0<=i<N, X_i > Y_i) と自然数Mが与えられる.
各i についてX_i,Y_i を選んでいく.
ただし,X_iを選べるのはM回までで,i<N-1でM回選んでしまうとそれ以降のY_iは得られない.
得られる合計を最大化せよ.
1 <= N,M <= 105

解法

まず, M>=Nのケースは全てX[i]を選べば良い.
その他のケースについて,Z[i] := [0,i) で得られるM-1個以下の和の最大値 とする.
これは最小値を取り出すpriority_queueを用いれば更新できる.
sum(0<=i<N) Y[i] を求めておいて,以降X[i]を取るものを選び X[i] - Y[i]を足す.
i個目を最後に選ぶとそれ以降を取れなくなってしまうから, sum(i<j<N)(Y[i])を引けば良く
後ろから X[i] - Y[i]+ Z[i] - sum
(i<j<N)(Y[i])をの最大値を見ていけば良い.

メモ

M=1のケースに注意.
超典型っぽいのにseg木とか考えてやたら時間を使ってしまったので反省.

コード

#include "bits/stdc++.h"

#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 RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

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

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

priority_queue<int,vector<int>,greater<int>> que;
int X[MAX_N],Y[MAX_N],Z[MAX_N];

int main(){
  int N,M; cin >> N >> M;
  rep(i,N) scanf("%d%d",X+i,Y+i);
  int ans = 0;
  if(N<=M){
    rep(i,N) ans += X[i];
    cout << ans << endl;
    return 0;
  }
  rep(i,N) ans += Y[i];
  int temp = 0; fill(Z,Z+N,0);
  rep(i,M-1) que.push(X[i]-Y[i]), temp += X[i] - Y[i];
  // Z[i] := [0,i) から M-1個 とった時のmax(sum(X[j]-Y[j]))
  if(M>1){
    REP(i,M-1,N){
      Z[i] = temp;
      if(que.top()<X[i]-Y[i]){
        temp += X[i]-Y[i]-que.top();
        que.pop(); que.push(X[i]-Y[i]);
      }
    }
  }
  temp = 0; int ma = -INF;
  RREP(i,N-1,M-1){
    ma = max(ma,X[i]-Y[i]+Z[i]-temp);
    temp += Y[i];
  }
  cout << ans + ma << endl;
  return 0;
}

みんなのプロコン 2018 C - 駆引取引

問題概要

Nターンのゲームをする. 値段x[i],価値v[i],費用c[i] が与えられる.
先手は前からx[i]を売るか,それまで得た値段を払ってmax_(i in {1..N})(v[i])を得てゲームを終了する.
後手は先手の価値を最小化するように価値を取り除く
先手の最大スコアを求めよ.

解法

dp[i][S] := (Sの品物が残っている状態でiターン目から得られる最大の価値)
solve(i,S) := (iターン目からSが残っている状態で得られる最大の価値) とする.
Sはビット列で管理する.

dp[i][S]が分かっていれば
先手はゲームを終了/売るのうち最大の方を選べば良く,
売るの方を選択すると後手は利益を最小化するように品物を除いてくるので solve(i,S) := max(dp[i][S], min_(s in 残っている品物のうちどれか)(solve(S\s)) で解ける.
これはメモ化すれば N*2N. 答えは solve(0,all) になる.

dp[i][S]を求める. まず全てのSについて価値valと費用costを出し,
費用がiターンまでに得た値段以下のものを dp[i][S] = val とする.
次に全てのSについて,iがSに含まれていなければ dp[i∪S] = max(dp[i∪S],dp[S]) と遷移すれば解ける.

O(N2*2N)で,軽めのO(108)ぐらいなので間に合う.

メモ

CODE THANKS FESTIVALのFとほとんど同じだし,良く出る遷移っぽい.
また配列サイズ間違うクソみたなバグを埋め込んでしまった. vectorで管理した方がいいのかなあ.

コード

#include "bits/stdc++.h"

#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 RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

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

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

ll dp[20][(1<<18)];
ll x[20],c[20],v[20],s[20],cost[(1<<18)],val[(1<<18)];
int N;

inline bool contain(int bit,int i){
  return (bit>>i)&1;
}

int main(){
  cin >> N;
  Pl vc[20];
  rep(i,N) cin >> x[i];
  rep(i,N) cin >> c[i];
  rep(i,N) cin >> v[i];
  s[0] = 0LL;
  rep(i,N) s[i+1] = s[i] + x[i];
  rep(i,N) rep(j,1<<N) dp[i][j] = 0LL;
  fill(cost,cost+(1<<18),0LL);
  fill(val,val+(1<<18),0LL);
  
  rep(j,1<<N){
    rep(k,N) if(contain(j,k)) cost[j] += c[k], val[j] += v[k];
  }
  rep(i,N){
    rep(j,1<<N) if(cost[j]<=s[i]) dp[i][j] = max(dp[i][j],val[j]);
  }

  rep(i,N){
    rep(j,1<<N){
      if(__builtin_popcount(j)>N-i) continue;
      rep(k,N) if(contain(j,k)) dp[i][j] = max(dp[i][j],dp[i][j^(1<<k)]);
    }
  }

  map<P,ll> memo;
  function<ll(int,int)> solve = [&](int a,int b){
    if(memo.count(P(a,b))) return memo[P(a,b)];
    if(a==N) return 0LL;
    ll res = dp[a][b];
    ll temp = LINF;
    rep(i,N) if(contain(b,i)) temp = min(temp,solve(a+1,b^(1<<i)));
    return memo[P(a,b)] = max(res,temp);
  };
  cout << solve(0,(1<<N)-1) << endl;
  return 0;
}

天下一2016 予選B C - 天下一プログラマーコンテスト1999

問題概要

N人で総当たり戦を行う.
勝ち数が同じ場合はindexで順位をつける.
Pの確率で結果を間違う時,元どおりの順位となる確率を求めよ.

解法

solve(i,j) := [i,N)が正しい順位で,i人めがj勝の確率 としてメモ化再帰.
答えはsolve(0,N-1)になる.
m勝n敗した人がj勝する確率は(n=N-1-m)
sum_(0<=k<=j)(mCk * nC(j-k) * pn-j+2k * (1-p)m+j-2k) となる.

メモ

あんまり難しくなかったのにアホみたいなとこにいくつかハマったのでメモ.
3029/2回勝負あるからコンビネーションが計算できないやん
-> pk,(1-p)kの係数を考えようとする
-> 良くみると1人N-1回までしかないから足りる
-> というかN2/2までならdoubleが1e300ぐらいまでいけるので足りるね.
comb(0,1) = 0, comb(0,0) = 1 を忘れる.
P=0の時NoneになるのでP=0 -> 0.0を出力するようにした
-> 良く考えれば3人で各1勝みたいなケースは1じゃない
-> Noneになる原因はpow(0,-EPS)=infでinf*0があることだったのでpow(a,max(b,0))に

コード

#include "bits/stdc++.h"

#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 RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

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

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

double comb(int n,int k){
  if(n==0){
    if(k==0) return 1.0;
    else return 0.0;
  }
  if(n<k) return 0.0;
  double res = 1.0;
  k = min(k,n-k);
  RREP(i,n,n-k+1) res *= i;
  RREP(i,k,1) res /= i;
  return res;
}

int A[MAX_N][MAX_N],N;
P ab[MAX_N];
double PP;
map<P,double> memo;

double solve(int p, int q){
  if(memo.count(P(p,q))) return memo[P(p,q)];
  int a,b; tie(a,b) = ab[p]; a = -a;
  int c = N-1-a;
  double res = .0;
  rep(j,q+1){
    double win = .0;
    // j勝する
    rep(k,j+1){
      win += comb(a,k)*comb(c,j-k)*pow(PP,max(double(c-j+2*k),0.0))*pow(1.0-PP,max(double(a+j-2*k),0.0));
    }
    if(p==N-1) res += win;
    else{
      int a2,b2; tie(a2,b2) = ab[p+1]; a2 = -a2;
      if(b<b2) res += win * solve(p+1,j);
      else res += win * solve(p+1,j-1);
    }
  }
  return memo[P(p,q)] = res;
}

int main(){
  double p,q; scanf("%d %lf/%lf",&N,&p,&q);
  PP = p/q;
  // if(abs(PP)<EPS){
  //   cout << "0.000000000000000" << endl;
  //   return 0;
  // }
  rep(i,N) rep(j,N) cin >> A[i][j];
  rep(i,N) ab[i].second = i;
  rep(i,N) rep(j,N) if(A[i][j]) ab[i].first--;
  sort(ab,ab+N);
  printf("%.10f\n",solve(0,N-1));
  return 0;
}