特殊なルールで変換される携帯電話の変換結果候補の組み合わせ数を求める問題。
解法
トライアンドエラーで解いた問題。
連続した数字の長さがｎ文字だとして、ｎ-1文字目までの組み合わせからｎ文字目の組み合わせをボトムアップで求めることが出来ます。
n-1文字の末尾がイになる組み合わせだったら次はウになる組み合わせかアになる組み合わせにしか分岐しません。
memo[n][1](1は1文字のア)かmemo[n][3]に足されます。
ここまでは当たり前にできたのですが。
なんでn%5==1とn%3==1の時だけ１を足さないといけないのか理由が分かりません。
直感的にn%5==1になるとき+１が必要なのではと理由もわからず思いつき試してみたらうまくいきました。
#include<stdio.h>
#include<iostream>
#include<string.h>
long long int memo5[100001][6];
long long int memo3[100001][4];
long long int perm5[100001],perm3[100001];
long long int mod=100000007;
int main(){
memset(memo5,0,sizeof(memo5));
memset(memo3,0,sizeof(memo3));
memo5[1][1]=1;
memo3[1][1]=1;
perm5[1]=perm3[1]=1;
for(int n=2;n<=100000;n++){
int i=n-1;
memo5[n][1]=(memo5[i][1]+memo5[i][2]+memo5[i][3]+memo5[i][4]+memo5[i][5]+(n%5==1))%mod;
memo5[n][2]=memo5[i][1];
memo5[n][3]=memo5[i][2];
memo5[n][4]=memo5[i][3];
memo5[n][5]=memo5[i][4];
perm5[n]=(memo5[n][1]+memo5[n][2]+memo5[n][3]+memo5[n][4]+memo5[n][5])%mod;
memo3[n][1]=(memo3[i][1]+memo3[i][2]+memo3[i][3]+(n%3==1))%mod;
memo3[n][2]=memo3[i][1];
memo3[n][3]=memo3[i][2];
perm3[n]=(memo3[n][1]+memo3[n][2]+memo3[n][3])%mod;
}
char text[100001];
while(1){
scanf("%s",text);
if(text[0]=='#')break;
int count=0;
char c=text[0];
long long int ans=1;
for(int i=0;i<strlen(text)+1;i++){
if(text[i]==c){
count++;
}else{
if(c=='8'||c=='0')ans=(ans*perm3[count])%mod;
else ans=(ans*perm5[count])%mod;
c=text[i];
count=1;
}
}
std::cout<<ans<<"\n";
}
}
1084
数字を並べたカードを入れ替えて連続した数の掛け算を行うとき最大の数を求める問題。
仮説
この問題はある２枚のカードを入れ替えるというよりも、注目しているｋ枚の範囲のカードのうち一番小さいカードを、ｋ枚の外側にある一番大きなカードと入れ替えたらどうなるかという点に注目して解く。
問題はカードの入れ替えを何度も行ってもよいらしいということです。
つまり途中までカードの得点を下げて最後に一気に成績点を上げる可能性が残されています。
1085 Spellcasters
各魔法使いについて自分とペアを組める人の最低値を二分探索で探すだけです。
後はそれより大きな人とは必ずペアが組めるので足しこめば計算終了です。
#include<stdio.h>
#include<algorithm>
#include<vector>
struct wiz{
int no,r;
bool operator<(const wiz& w)const{
return r<w.r;
}
};
void calc(int n,int s){
std::vector<wiz> vs;
std::vector<wiz>::iterator it;
int r;
wiz w;
for(int i=0;i<n;i++){
scanf("%d",&r);
w.r=r;
vs.push_back(w);
}
std::sort(vs.begin(),vs.end());
for(int i=0;i<n;i++)vs[i].no=i;
int ans=0,m;
for(int i=0;i<n-1;i++){
w.r=s-vs[i].r;
it=std::upper_bound(vs.begin(),vs.end(),w);
if(it==vs.end())continue;
m=std::max((*it).no,i);
if(i==m)m++;//自分自身とはペアは組めないのでひいておく
ans+=n-m;
}
printf("%d\n",ans);
}
int main(){
int n,s;
while(1){
scanf("%d %d",&n,&s);
if(n==0&&s==0)break;
calc(n,s);
}
}
1086 Live Schedule
日数、連続公演の数、疲労度を基準にした動的計画法で合格。
暑い、、夏バテ、アイスがないなら死んでるな。
#include<stdio.h>
#include<string.h>
#include<algorithm>
int memo[32][7][52];//日数、連続公演の数、疲労度
void setData(int c,int d,int w,int x){
int Es[32][32];//売り上げ[地域の数][日数]
int Fs[32][32];//疲労度[地域の数][日数]
memset(memo,-1,sizeof(memo));
//収益の読み込み
for(int i=0;i<c;i++){
for(int j=0;j<d;j++){
scanf("%d",&Es[i][j]);
}
}
//疲労度の読み込み
for(int i=0;i<c;i++){
for(int j=0;j<d;j++){
scanf("%d",&Fs[i][j]);
}
}
//日数、連続公演回数、疲労度を基準に動的計画法を適用する
int ans=0,sumE,sumF;
memo[0][0][0]=0;
for(int i=0;i<d;i++){
for(int j=0;j<=x;j++){
for(int k=0;k<=w;k++){
//日数、連続公演回数、疲労度のループ
if(memo[i][j][k]==-1)continue;
memo[i+1][j][k]=std::max(memo[i][j][k],memo[i+1][j][k]);//この日は公演を行わない
ans=std::max(memo[i+1][j][k],ans);
for(int l=0;l<c;l++){
sumE=memo[i][j][k];
sumF=k;
for(int m=l;m>=0;m--){
if(Es[m][i]==0)break;
sumE+=Es[m][i];
sumF+=Fs[m][i];
if(w<sumF)break;
int add=(m!=l?1:0);
if(add==1&&x==j)break;
memo[i+1][j+add][sumF]=std::max(sumE,memo[i+1][j+add][sumF]);
ans=std::max(memo[i+1][j+add][sumF],ans);
}
}
}
}
}
for(int j=0;j<=x;j++){
for(int k=0;k<=w;k++){
ans=std::max(memo[d][j][k],ans);
}
}
printf("%d\n",ans);
}
int main(){
int c,d,w,x;
while(1){
scanf("%d %d %d %d",&c,&d,&w,&x);
if(c==0&&d==0&&w==0&&x==0)break;
setData(c,d,w,x);
}
}
1087 Dimensional Analysis
解法
再帰下降構文解析に*と/のオペレータを組み込み、+と-が適切に行われているか試すだけの問題です。
素直に実装します。
#include<stdio.h>
#include<string>
#include<map>
#include<iostream>
#include<vector>
struct D{
int ds[10];
int size;
bool isAddOrDellOK(const D& d){
for(int i=0;i<size;i++)if(d.ds[i]!=ds[i])return false;
return true;
}
D mult(const D& d){
D re;
for(int i=0;i<size;i++)re.ds[i]=ds[i]+d.ds[i];
re.size=size;
return re;
}
D div(const D& d){
D re;
for(int i=0;i<size;i++)re.ds[i]=ds[i]-d.ds[i];
re.size=size;
return re;
}
};
std::map<std::string,D> deriveds,vds;
bool isAllOK;
D saiki(std::string formula,int& p,int pr,int n){
D re,a;
re.size=a.size=n;
while(formula.size()>p){
char c=formula[p];
if(c=='('){
p++;
re=saiki(formula,p,0,n);
p++;
}else if(c==')'){
return re;
}else if(c=='+' || c=='-'){
if(pr>=1){
return re;
}
p++;
a=saiki(formula,p,1,n);
if(re.isAddOrDellOK(a)==false){
isAllOK=false;
}
}else if(c=='*'){
if(pr>=2){
return re;
}
p++;
a=saiki(formula,p,2,n);
re=re.mult(a);
}else if(c=='/'){
if(pr>=2){
return re;
}
p++;
a=saiki(formula,p,2,n);
re=re.div(a);
}else{
std::string str="";
int k=0;
while(formula[k+p]!='\0'){
str+=formula[k+p];
if(vds.find(str)!=vds.end())break;
k++;
}
re=vds[str];
p=p+k+1;
}
}
return re;
}
void setData(int n,int m,int p){
deriveds.clear();
vds.clear();
std::string name,dName;
isAllOK=true;
D d;
std::vector<std::string> vec;
std::string formula;
for(int i=0;i<m;i++){
std::cin>>name;
d.size=n;
for(int i=0;i<n;i++){
std::cin>>d.ds[i];
}
vec.push_back(name);
deriveds[name]=d;
}
std::cin>>formula;
for(int i=0;i<p;i++){
std::cin>>name>>dName;
vds[name]=deriveds[dName];
}
int point=0;
D kekka=saiki(formula,point,0,n);
if(isAllOK==false){
//std::cout<<">>>>>>>>>>error\n";
//for(int i=0;i<n;i++){
// std::cout<<" "<<kekka.ds[i];
//}
std::cout<<"error\n";
}else{
std::string ans="undefined";
for(int i=0;i<vec.size();i++){
if(kekka.isAddOrDellOK(deriveds[vec[i]])==true){
ans=vec[i];
}
}
std::cout<<ans<<"\n";
//std::cout<<"\n\n>>>>>>>"<<ans<<"\n>>>>>>>";
//for(int i=0;i<n;i++){
// std::cout<<" "<<kekka.ds[i];
//}
//std::cout<<"\n";
}
}
int main(){
int n,m,p;
while(1){
scanf("%d %d %d",&n,&m,&p);
if(n==0&&m==0&&p==0)break;
setData(n,m,p);
}
}
最終更新：2013年02月14日 23:16
