保存されている過去のバージョンの一覧

2014年11月07日20時17分16秒
2014年11月07日18時41分13秒

yukicoder No.10 - ＋か×か

Source

ニコニコミュニティ
問題文

問題概要

$N$ 個の整数 $A_1,A_2,\ldots,A_N$ と整数 $T$ が与えられる．
$N$ 個の整数を，左結合で，足し算か掛け算をした時，$T$ になるようにしたい．
つまり，$(\cdots ((A_1\ {\rm op}_1\ A_2)\ {\rm op}_2\ A_3)\ {\rm op}_3 \cdots {\rm op}_{N-1}\ A_N) = T$ にしたい．
ただし，${\rm op}_k \in \{+,\times\}$．
このような ${\rm op}_1,{\rm op}_2,\ldots,{\rm op}_{N-1}$ を求める問題．
答えが存在することは保証されている．
ただし，答えが複数存在するなら，$+$ の方が $\times$ より小さいとして，辞書順最小のものを求める．

解法

動的計画法＋経路復元．
状態として（何番目の整数まで使ったか，$x$）を取り，そこまでで $x$ が作れるかどうかを求めれば良い．
ここで，足し算と掛け算しかないので，値は減ることがなく，$x$ は $x \leq T$ の範囲のみ調べれば良い．
時間計算量，空間計算量ともに $O(NT)$．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}

int N, T, A[51];
int dp[51][100001];

int main(){
  int i, j, k;

  reader(&N,&T);
  rep(i,N) reader(A+i);
  rep(j,T) dp[N][j] = 0; dp[N][T] = 1;
  for(i=N-1;i>=0;i--) rep(j,T+1){
    dp[i][j] = 0;
    if(j+A[i] <= T && dp[i+1][j+A[i]]) dp[i][j] = 1;
    if(j*A[i] <= T && dp[i+1][j*A[i]]) dp[i][j] = 1;
  }

  j = A[0];
  REP(i,1,N){
    if(j+A[i] <= T && dp[i+1][j+A[i]]){ mypc('+'); j += A[i]; continue; }
    if(j*A[i] <= T && dp[i+1][j*A[i]]){ mypc('*'); j *= A[i]; continue; }
  }
  mypc('\n');

  return 0;
}

Current time: 2024年04月18日16時53分30秒
Last modified: 2014年11月07日20時17分16秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：