Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-12

SRM386 div2 (過去問)

01:24

Easy - TrophyShelf

トロフィーが一例に並べられている. 一例を前から見た場合, あるトロフィーはその前にあるトロフィーより高さが高くなければ, 見えない. トロフィーを前から, 後ろから見た場合, 何本見えるかを返す.

これはやるだけの問題です.

class TrophyShelf {
public:
  vector <int> countVisible(vector <int> trophies) {
    vector <int> ret(2, 1);
    int maxl = trophies[0], maxr = trophies[trophies.size()-1];

    for (int i=1; i<trophies.size(); i++)
      if (trophies[i] > maxl) {
        ret[0]++;
        maxl = trophies[i];
      }

    reverse(trophies.begin(), trophies.end());

    for (int i=1; i<trophies.size(); i++)
      if (trophies[i] > maxr) {
        ret[1]++;
        maxr = trophies[i];
      }

    return ret;
  }
};

Medium - CandidateKeys

ちょっと問題文の意味が読み取れませんでした. 行数が高々10なので, いろいろな列の組み合わせで全探索をすれば良さそうなのですが, どのような条件の時にカウントすればいいのかがいまいちわかりません. 眠くなったので今日はもう無理と判断. 後日再チャレンジします.