naoya_t@hatenablog

いわゆるチラシノウラであります

SRM540 - Easy落ちまくり回

Room41 - LayCurseさんの部屋
Challenge Phaseでは落とされなかったけれどSystem Testで落ちて0点
1655→1600

Easy(250) ImportantSequence.cpp

  • 途中でオーバーフローの可能性に気づいてlong longに切り替え
  • 50000000000000000LLとか打ってるけどゼロの数かぞえてません
  • cons, car, cdr とか気にしないで(べ、べつに難読化のためじゃないんだからね)
  • 121.32点 (39'31'') → 0点 (Failed System Test)
    • ケース {8, -3, 14, -5, 18, 4, -3}, "+-+-+--" で落ちてる。期待値は5、自分実装では7。
    • '-' で移動する時に値の範囲を1〜INT_MAXでcropしないとダメじゃん
    • オーバーフロー以外の理由で落ちるとか論外
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#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 pair<ll,ll> i_i;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

class ImportantSequence {
 public:
  i_i smaller(i_i a, i_i b) {
    if (cdr(a)<car(b) || cdr(b)<car(a)) return cons(0,-1);
    i_i re=cons(max(car(a),car(b)),min(cdr(a),cdr(b)));
    return re;
  }
  int getCount(vector<int> B, string operators) {
    int N=sz(B);
    vector<i_i> a(N+1), r(N+1);
    a[0] = cons(0,1);
    r[0] = cons(1,50000000000000000LL);
    rep(i,N){
      ll b = B[i];
      if (operators[i] == '+') {
        //r:1 .. b-1
        r[i+1] = cons(1,b-1);
        r[i] = smaller(r[i],r[i+1]);
        a[i+1] = cons(b-car(a[i]),-cdr(a[i]));
      } else {
        r[i+1] = cons(car(r[i])-b,cdr(r[i])-b);
        a[i+1] = cons(car(a[i])-b,cdr(a[i]));
      }
      // r[i+1] = smaller(r[i+1], cons(1,50000000000000000LL)); ///この1行を追加すれば通る
    }
    vector<i_i> q(N+1);
    i_i ans(1,50000000000000000LL);
    rep(i,N+1) {
      ll b = car(a[i]);
      i_i q;
      if (cdr(a[i]) > 0) {
        q = cons(car(r[i])-b,cdr(r[i])-b);
      } else {
        q = cons(b-cdr(r[i]),b-car(r[i]));
      }
      ans = smaller(ans,q);
    }
    ll d = cdr(ans) - car(ans);
    if (d > INT_MAX) return -1;
    return (d >= 0) ? d+1 : 0;
  }
};

Medium(550) RandomColoring

  • 残り35分
  • 50^3 x 50^3 x 40ステップ は間に合わないよね
  • d2, d1 それぞれRGB各チャンネル毎に計算したものを引き算とか?
  • もうちょいな感じあったけど時間切れ