練習会 SRM 232 DIV 1

凡ミスはもう嫌です

Easy WordFind

間違えた。後で書く。

Medium CommunicableDisease

n人のうち汚染されてる人とされてない人がいて、その人たちが接触するのを何回か行う。最終的な結果として誰が汚染されてて誰がされてないかが渡されるので、最初のn人のうち誰が汚染されていて、誰が汚染されていなくて、また誰が特定できないかを調べなさい。

普通に探索。

#define rep(i, c)   for(int i = 0; i < c; ++i)
#define reps(i,s,c) for(int i = s; i < c; ++i)
#define all(c)    (c).begin(), (c).end()
#define each(i, c)  for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

#define EPS 1e-9

using namespace std;

class CommunicableDisease {
  int contacts(string C) {
    int c=1;
    each(ch, C)if(*ch==' ')c++;
    return c;
  }
public:
  string findSource(vector <string> contact, string results) {
    int N=results.length();
    int C=contacts(contact[0]);
    vector<set<int> > V(N);
    stringstream *I = new stringstream[N];
    rep(i, N) {
      V[i].insert(i);
      I[i] << contact[i];
    }
    rep(i, C) {
      vector<set<int> > t = V;
      rep(j, N) {
        int to;
        I[j] >> to;
        V[to].insert(all(t[j]));
      }
    }
    string res(N, 'I');
    while(true) {
      bool ch = false;
      rep(i, N)
        if(results[i] == 'N') {
          each(j, V[i]) {
            if(res[*j] != 'N') {
              res[*j] = 'N';
              ch = true;
            }
          }
        } else {
          int S = V[i].size();
          int c = 0, at;
          each(j, V[i])
            if(res[*j] == 'N')
              ++c;
            else
              at = *j;
          if(S-c == 0) return "INVALID";
          if(c == S-1 && res[at] != 'C') {
            res[at] = 'C';
            ch = true;
          }
        }
      if(!ch)
        break;
    }
    delete[] I;
    return res;
  }
};

Hard SalesPromotion

商品がたくさんあります。ポイントを持っています。特定の数だけ商品が半額になります。半額にならない商品はすべて特定の割合だけ値引きされます。ポイントで支払うときにお金は一切使えません。商品の値段と、何ポイントで買えるかのリストが渡されるので、ポイントを全て使い、特定の数だけ商品を必ず半額で支払い、残りの商品をすべて特定の割合だけ値引きして買ったとき、一番お金を使わなくて済むとき幾ら使いますか。

ただのDPですね。はい。で解けるはずだったんだけど、

vectorをint[]に変換する関数呼び忘れたｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ俺アホスｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

死にたい

#define rep(i, c)   for(int i = 0; i < c; ++i)
#define reps(i,s,c) for(int i = s; i < c; ++i)
#define all(c)    (c).begin(), (c).end()
#define each(i, c)  for(typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)

#define EPS 1e-9
#define INF 1000000000

using namespace std;

int dp[15001][51];//dp[j][k] -> j points and k half price items
int tmp[15001][51];
int pv[50];
int pr[50];

class SalesPromotion {
  void parse(vector<string> it) {
    rep(i, it.size()) {
      istringstream ss(it[i]);
      ss >> pv[i] >> pr[i];
      cerr<<pv[i]<<' '<<pr[i]<<endl;
    }
  }
public:
  int bestPrice(int points, int halfPrice, int discount, vector <string> items) {
    rep(i, points+1)rep(j, halfPrice+1)
      dp[i][j]=INF;
    dp[points][halfPrice] = 0;
    parse(items); // これ忘れてたｗｗｗｗｗｗｗｗｗｗｗｗｗ
    rep(i, items.size()) {
      rep(j, points+1)rep(k, halfPrice+1)
        tmp[j][k]=INF;
      rep(j, points+1)rep(k, halfPrice+1) {
        if(j >= pv[i])
          tmp[j-pv[i]][k] <?= dp[j][k];
        if(k > 0)
          tmp[j][k-1] <?= dp[j][k] + ((pr[i]+1)/2);
        tmp[j][k] <?= dp[j][k] + (int)((99+pr[i]*(100-discount))/100);
      }
      rep(j, points+1)rep(k, halfPrice+1)
        dp[j][k]=tmp[j][k];
    }
    return dp[0][0];
  }
};