SRM424 DIV2
250pt
大文字アルファベットのみからなる文字列の文字'A','Z'だけを反転させる。
与えられる文字列は最大50文字。
class MagicSpell { public: string fixTheSpell(string spell){ stack<char> s; for(int i=0;i<spell.size();i++){ if(spell[i]=='A' || spell[i]=='Z')s.push(spell[i]); } for(int i=0;i<spell.size();i++){ if(spell[i]=='A' || spell[i]=='Z')spell[i]=s.top(),s.pop(); } return spell; } };
適当に書いた、O(2n)の愚鈍なアルゴリズム。
両端から走査すればO(n/2)
500pt
整数Nを生成する掛け算の項の最小個数を求める問題(意訳)。
ただし1つの項の値は9以下。生成できない場合は-1を返す。
整数Nの範囲は1〜1000000000まで。
1項のみの最大値は9
2項のみの最大値は81
3項のみの最大値は729
…
と整数Nを生成できる範囲を求めたあとで、ループで検索する解法はTLEになる。
なんでこんな解法を最初に書いてしまったのか、問題文に嵌められたに違いない。
生成する掛け算は整数Nを素因数分解した各々の値を9以下の1つの項にまとめたものになる。
というわけで、素因数分解して順番に9以下の項を生成する際に項を数えれば良い。
2桁以上の素数を因数に持つ整数Nは必ず-1。
class ProductOfDigits { public: int smallestNumber(int N){ vector<int> v; for(int i=2;i*i<=N;i++){ for(;N%i==0;N/=i){ if(i>10)return -1; v.push_back(i); } } if(N>1){ if(N>10)return -1; v.push_back(N); } int ans=1,sum=1; for(int i=0;i<v.size();i++){ sum*=v[i]; if(sum>=10)sum=v[i],ans++; } return ans; } };