読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM572 DIV2

Topcoder SRM

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してほしいと思った