SRM 712 div2 med RememberWordsEasy

考えたこと

O(max(d_1,d_2)max(w_1,w_2))で愚直にDPするのは無理。考察の方針が思い浮かばなかったのでとりあえず手で試してみる。区間の端を0単語とすると1～d1までの和の単語数までは全て実現することが可能そう。区間の端を決め打ってその区間で実現できる最小と最大の単語数を考えた時、その間の単語数は全て実現することが可能そう。したがって、d1日目に覚える単語数を決め打てば、そのときに実現することが可能かどうか判定できそう。
O(w_1)で探索していくコードを書いて提出するとシステスで落ちた…実装がバグっている部分を直して提出を繰り返したら5WAくらいで何とか通せた。

学び

無駄に場合分けを増やして混乱してバグらせるをしない。
こういう問題はちゃんと数式をまとめてから書き始めないと自分はバグらせるのでちゃんと紙にまとめる。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a <= x && x < b)
#define MP make_pair
#define PB push_back
const int INF = (1LL << 30);
const ll LLINF = (1LL << 60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class RememberWordsEasy {
public:
  string isPossible(int d1, int d2, int w1, int w2) {
    REP(i, w1 + 1) {
      // d1日目をi単語
      // semester1で[low, high]単語覚えられる
      ll low, high = (ll)d1*(d1-1)/2 + i*d1;
      if (i <= d1) low = i*(i+1)/2;
      else low = i*(i+1)/2 - (i-d1)*(i-d1+1)/2;
      if (low <= w1 && w1 <= high) {
        // semester2で[low, high]単語覚えられる
        ll low, high = (i+d2)*(i+d2+1)/2 - i*(i+1)/2;
        if(i == 0) low = 0;
        else if(i <= d2+1) low = (i-1)*i/2;
        else low = (i-1)*i/2 - (i-d2-1)*(i-d2)/2;
        if(low <= w2 && w2 <= high) {
          return "Possible";
        }
      }
    }
    return "Impossible";
  }
};