SRM582 DIV2 -Level1,2

やっと緑コーダーになれました。
SYSTEMテストで2回連続で落ちていて、3度目の正直。
Challengeを今までまったくしておらず、ちゃんとコード書けることが大事だからいらないかなと思っていました。
ただ、撃墜できること=自分のコードの抜け漏れがチェックできる、ということにもつながるのでこれからはちょっと力を入れていきたいです。

Level1
<問題>
①2以上のある整数Nが与えられる。
②a>=1,b>1,a<b, a*b*b=Nとなる数字が存在する場合はYes、
 そうでない場合はNoを返す。

<解き方>
単純に実装するだけです。
全探索でもよいのですが、Yesならb*bは必ず存在するので
bを1からb*b<=Nまでまわして判定しました。

<コード>
class SemiPerfectSquare {

public: string check(int N) {

for(int i=1;i*i<=N;i++){
if(N%(i*i)==0 && N/(i*i)<i)return "Yes";
}
return "No";
}

};

Level2
<問題>
①魔法少女の強さの順列、敵の強さの順列と各敵の数が与えられる。
②魔法少女は1匹敵を倒すたびに疲れが1増える。最初は0。
③このとき、全ての敵を倒した時に魔法少女の中で最も大きい疲れが最小となるものを返す。全ての敵を倒せない場合はー1を返す。

<解き方>
全ての魔法少女が全ての敵を倒すことができる理想の状態を考えると、
各魔法少女は「N=全ての敵の数/全ての魔法少女の数」の敵を倒せばよい。
ただそうでないケースも存在するので、その場合をシミュレーションで実装する。

まずは魔法少女と敵を強さの昇順にソートして例外処理を行う。
一番強い魔法少女の強さより、最も強い敵の強さが高ければ
全ての敵を倒せないのでー1を返す。

次に、魔法少女が倒すことができない敵が出た時は次の魔法少女に移り、
「N=残りの敵の数/残りの魔法少女の数」を再計算してあげる。

すべてシミュレーションが終了した時、最も高い疲れの値を返してあげればよい。

<関数>
2つの配列について、一つの配列の値に対してソートできれば簡単になる。

<コード>
class SpaceWarDiv2 {

public: int minimalFatigue(vector<int> mS, vector<int> eS, vector<int> eC) {
vector <pair <int, int> > enemy;
int n=0,girl=mS.size();
int ans=0;
vector<int> girlF(mS.size(),0);

FORE(i,0,eS.size())enemy.push_back(make_pair(eS[i],eC[i]));

sort(mS.begin(),mS.end());
sort(enemy.begin(),enemy.end());

if(mS[(int)mS.size()-1]< enemy[(int)enemy.size()-1].first)return -1;

FORE(i,0,enemy.size())n+=enemy[i].second;
int num=(n+girl-1)/girl;

int curg=0,cure=0;
int curn=num;
while(curg<mS.size() && cure<enemy.size()){
if(mS[curg]>=enemy[cure].first){
while(1){
enemy[cure].second--;
curn--;
girlF[curg]++;
if(enemy[cure].second==0 || curn==0){
if(enemy[cure].second==0)cure++;
if(curn==0){
curg++;
curn=num;
}
break;
}
}
}
else{
curg++;
if(curg==girl)break;
n=0;
FORE(i,cure,(int)enemy.size())n+=enemy[i].second;
num=(n+girl-curg-1)/(girl-curg);
curn=num;
}
}
FORE(i,0,(int)mS.size())ans=max(ans,girlF[i]);

return ans;
}

};

このエントリーをはてなブックマークに追加