SRM572 DIV2
250---
0があるかどうか確認しながら負の要素を数えるだけなので略
500---
問題概要:
2つのstring、startとgoalが与えられる
NextとPrevという操作を行いstartをgoalにすることができるか?
できるならそれに必要な最小コストを、できないなら-1をリターンしろ
Next、Prevは好きなタイミングで好きなだけ使える
start内に同じアルファベットは存在しない goalも同様
解法:
start[0] から start[start.size()-1] までループでみていきそれぞれコストを計算していく
for i 0からstart.size()-1まで
if start[i] < goal[i]
コスト += (goal[i]-start[i])*nextCost
else
コスト += (start[i]-goal[i])*prevCost
でコストが計算できる
最小のコストを返すのでstart[i]をgoal[i]にするために増やすなら増やす、減らすなら減らせば最小となる
ただ、もしstart[i]をgoal[i]にそろえる過程でstartの別のアルファベットと同じアルファベットになってしまったらそれは-1を返さなければならない
例えば、"ab" -(Next)-> "bb" となってしまったら-1を返す必要がある
なぜらなばgoal内のアルファベットは全て異なるので同じアルファベットがでた時点でどうあがいてもgoalには到達できない
"bb" -(Next)-> "cc"であることに注意
"bb" -(Next)-> "bc"とはできない
アルファベットがかぶるかどうかは以下のようにして事前にチェックできる
for i 0からstart.size()-1まで
for j i+1からstart.size()-1まで
if start[i] < start[j] && goal[i] > goal[j]なら
return -1
else if start[i] > start[j] && goal[i] < goal[j]なら
return -1
もしstart[i]がstart[j]より小さいにもかかわらずgoal[i]のほうがgoal[j]より大きいのであればstart[i]はstart[j]と同じアルファベットにならざるを得ない
例えば
start -> "ab", goal -> "cb"のとき
"ab" -(Next)-> "bb"となってしまう
startのbをcより大きくして後から戻そうとしても結局cでならんでしまいだめである
コード:
class NextOrPrev { public: int getMinimum(int nextCost, int prevCost, string start, string goal) { for(int i=0;i<start.size();i++) for(int j=i+1;j<start.size();j++) if((start[i] < start[j] && goal[i] > goal[j]) || (start[i] > start [j] && goal[i] < goal[j])) return -1; int res = 0; for(int i=0;i<start.size();i++) if(start[i] < goal[i]) res += (goal[i]-start[i])*nextCost; else if(start[i] > goal[i]) res += (start[i]-goal[i])*prevCost; return res; } };
1000---
やってぬ
コメント:
250点問題で全部かけて判定している人が絶対1人はいると思ったら案の定いたわけで、challengeしてみたがなぜか数字が入力できなくて結局他の人にとられてしまった
なぜ入力できなかったのか?先に他の人がchallenge成功していたわけでもないし、他の問題でも同様に数字が入力できなかった
そんなこんなで頭をかかえる中別の人のコードをサンプルでchallengeしたら普通に通ってしまい減点される
なぜ入力できなかったのか?
わかりません
なぜなんだ・・・
あとそういうことがあったからといって冷静さを失わずにchallengeしてほしいと思った