土下座しながら探索中

主に競技プログラミング

SRM 573 Div2

250:
1つ先のをみて自分より大きければリターンする値に加え、自分の値を代入する

コード;

class SkiResortsEasy {
	public:
	int minCost(vector <int> altitude) {
	  int res = 0;
	  for(int i=0;i<altitude.size()-1;i++)		
	    {
	      if(altitude[i] < altitude[i+1])
		{
		  res += altitude[i+1] - altitude[i];
		  altitude[i+1] = altitude[i];
		}
	    }
	  return res;
	}
};

500:

問題概要:
vectorに個人の強さがint値として入っており、その中の3人でチームをつくる
0,1,2番は自分のチームである
チームの強さは(0番の強さ)+(1番の強さ)+(2番の強さ)ー(3人の中で一番弱い人の強さ)、つまりチーム内で1番強い人と2番めに強い人の強さの合計できまる
自分のチーム以外の人を最適に組み合わせたとき自分のチームは最大何位になる
か?

解法:
自分のチーム以外の人で一番強い人、一番弱い人、自分のチームに勝つために必要な値以上の値を持っている人の中で一番小さい値をもつ人を選んで消していった
最初に0、1、2の値から自分のチームの力を得て、その後0、1、2をvector内から削除する
次に、昇順でソートする
こうすることで残った人の中の最強はvectorのend、最弱はvectorのbeginとなる
そして最強と最弱を選び、自分のチームに勝つために必要最低限の値をlower_boundでとってくる
これを(最強の値)+(自分のチームに勝つために必要最低限の値)が自分のチームの値よりも大きい限り繰り返す
ループを繰り替えした値+1が答えとなる

class TeamContestEasy {
public:

  int worstRank(vector <int> strength) {
    int my_strength = 0;
    int men = (1<<30);
    for(int i=0;i<3;i++)
      {
	vector<int>::iterator it = strength.begin();
	if(men > (*it))
	  men = (*it);
	my_strength += (*it);
	strength.erase(it);
      }
    my_strength -= men;

    sort(all(strength));
    int cnt = 1;

    while(strength.size() > 2)
      {
	vector<int>::iterator tuyo = (strength.end()-1);
	vector<int>::iterator yowa = strength.begin();
	vector<int>::iterator tyuu = lower_bound(all(strength),my_strength+1-(*tuyo));
	assert(!(tyuu == tuyo && tyuu == yowa));
	if(tyuu == tuyo)
	  tyuu--;
	else if(tyuu == yowa)
	  tyuu++;

	int diff = (*tuyo) + (*tyuu);
	if(diff <= my_strength)
	  break;
	  
	cnt++;
	strength.erase(tuyo);
	strength.erase(tyuu);
	strength.erase(yowa);
	    
      }
    return cnt;		

  }
};

1000:
まだやってぬ

コメント:
まぁ、今回はリアルタイムで参加してないんです。
起きたのがコーディング開始20分前で登録画面についたのが17分前でした。
私はてっきり登録は10分前までだと思っていましたが、締め切られていました。
はて、何分前まで登録可能だったのやら?
今後は30分前までには登録しておこうとおもいます。
なので今回はコンテストが終わった後にpracticeでやりました。
それでもまで1000はやってないのですが、、
コンテスト中はすごくもどかしかったです。
前日風邪をひいて寝込んでいたこともあり早く起きれませんでした。
もとより朝には弱いので10時からは厳しい;;