naoya_t@topcoder

過去問マラソン(#11):SRM153

過去問マラソン | 12:05 |

戦闘用ローカルマシンにgitを入れたので、SRM152までのコードを昨日gitでcommit&pushしたつもりだったがディレクトリごと消えていた。git操作ミスか？

過去問マラソン的にはここに全部書いてるからまあいいけど、gitスキル的にやばい…

• *.cppファイルを自分で一括消去してるっぽい。…重複排除しようと思ってgit rmを使ったのを思い出した

TimeMachineが最後にバックアップした1/11の分（※USB足りないのでTimeMachine用1TBHDDは普段は繋いでない）まで覚えててくれました。SRM150の分まで入ってる。TimeMachine++

Easy(250): Inventory

• 問題読んでも全然頭に入ってこないよー
• とりあえずコード書いたけどSample Caseの最後のやつが合わない
• なるほど。有理数演算しないと駄目か。
• 前に書いたはずのFractionクラスのコードを引っ張り出す
  • https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20091227/1261925153
• これでどうだ
  • 30%ルールに引っかかるお
  • いろいろ削って最小限にしないとダメか
  • テンプレートとか駄目なのかなあ
• 削った。submit
• failed system test
  • なに！
  • sales[i]==0 || daysAvailable[i]==0 ってdaysAvailableだけ見ればいいか
  • submit#2
  • failed system test (again)
  • あ、わかった。Fraction<int>では精度が足りない。long longにしよう
  • submit#3
  • passed system test

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

typedef long long T;

T gcd(T m, T n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (m > n) m %= n; else n %= m;
  }
}

class Fraction {
  T numer, denom;

public:
  Fraction(){ init(0,1); }
  Fraction(T n, T d=1){ init(n,d); }
  Fraction(const Fraction& other){ init(other); }

  Fraction& init(T n, T d); // impl.below
  Fraction& init(const Fraction& other); // impl.below

  double value() {
    if (numer == 0) return 0;
    if (denom == 1) return (double)numer;
    return (double)numer / denom;
  }

  Fraction& operator+=(const Fraction& other); // impl.below
  Fraction& operator/=(T n){ return init(numer, denom*n); }
};

Fraction& Fraction::init(T n, T d)
{
  if (d < 0) n=-n, d=-d;
  if (n==0) {
    numer = 0, denom = 1;
  } else {
    T g = gcd(n,d);
    numer = n / g, denom = d / g;
  }
  return *this;
}
Fraction& Fraction::init(const Fraction& other){
  numer = other.numer, denom = other.denom;
  return *this;
}
Fraction& Fraction::operator+=(const Fraction& other)
{
  T g = gcd(denom, other.denom), l=denom/g*other.denom;// l=denomm*other.denom/gcd
  T n = numer*(other.denom/g) + other.numer*(denom/g);
  return init(n,l);
}

//
class Inventory {
 public:
  int monthlyOrder(vector <int> sales, vector <int> daysAvailable) {
    int n=sz(sales), d=0;
    Fraction sum;
    rep(i,n) {
      //if (sales[i]==0 || daysAvailable[i]==0) continue;
      if (daysAvailable[i]==0) continue;

      Fraction expected(sales[i]*30, daysAvailable[i]);
      sum += expected;
      d++;
    }
    sum /= d;
    return (int)ceil( sum.value() );
  }
};

Medium(450):

Easyで時間かけすぎたので後で

Hard(1000):