ichirin2501's diary

いっちりーん。

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;
  }
};