競プロ日記

ACコード
ACコード(区間をsetで管理)　2019/12/17追記

通常

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  lint n, x, d;
  cin >> n >> x >> d;
  if (d == 0) {
    if (x == 0) {
      cout << 1 << endl;
    } else {
      cout << n + 1 << endl;
    }
    return 0;
  }
  // ?
  if (d < 0) {
    x = -x;
    d = -d;
  }
  unordered_map<int, vector<pair<lint, lint>>> now;
  for (lint A = 0; A <= n; ++A) {
    // S = Ax + Bd
    lint Bmin = (A - 1) * A / 2, Bmax = (2 * n - A - 1) * A / 2;
    lint Adiv = A * x / d, Smod = A * x % d;
    if (Smod < 0) {
      Smod += abs(d);
      // ?
      ++Adiv;
    }
    now[Smod].push_back({Adiv + Bmin, Adiv + Bmax});
  }
  lint cnt = 0;
  allrep (m, now) {
    sort(all(m.second));
    lint now = LLONG_MIN;
    allrep (p, m.second) {
      lint l = max(now, p.first), r = max(now, p.second + 1);
      cnt += r - l;
      now  = r;
    }
  }
  cout << cnt << endl;
  return 0;
}

区間をsetで管理

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

template <bool merge_adjacent>
class SectionUnion {
  struct comp { bool operator()(const pair<long long, long long> &a, const pair<long long, long long> &b) const { return a.second < b.second; } };

  public:
  set<pair<long long, long long>, comp> section_set;
  SectionUnion(void) {}
  bool insert(long long l, long long r) {
    auto litr = section_set.lower_bound({0, l - merge_adjacent}), ritr = section_set.lower_bound({0, r});
    if (ritr != section_set.end() && r + merge_adjacent >= ritr->first) ++ritr;
    const bool exist = litr != ritr;
    if (exist) {
      l = min(l, litr->first), r = max(r, prev(ritr)->second);
      section_set.erase(litr, ritr);
    }
    section_set.insert({l, r});
    return exist;
  }
  bool remove(long long l, long long r, bool involve = false) {
    auto litr = section_set.lower_bound({0, l}), ritr = section_set.lower_bound({0, r});
    if (ritr != section_set.end() && r >= ritr->first) ++ritr;
    const bool exist = litr != ritr;
    if (exist) {
      long long ledge = litr->first, redge = prev(ritr)->second;
      section_set.erase(litr, ritr);
      if (!involve) {
        if (ledge < l) section_set.insert({ledge, l - 1});
        if (r < redge) section_set.insert({r + 1, redge});
      }
    }
    return exist;
  }
  bool same(long long a, long long b) const {
    if (b < a) swap(a, b);
    auto itr = section_set.lower_bound({0, b});
    return itr != section_set.end() && itr->first <= a;
  }
  pair<bool, pair<long long, long long>> get(long long x) const {
    auto itr = section_set.lower_bound({0, x});
    return {!(itr == section_set.end() && x < itr->first), *itr};
  }
  void clear(void) { section_set.clear(); }
  bool empty(void) const { return section_set.empty(); }
  int  size(void) const { return section_set.size(); }
};

int main(void) {
  lint n, x, d;
  cin >> n >> x >> d;
  if (d == 0) {
    if (x == 0) {
      cout << 1 << endl;
    } else {
      cout << n + 1 << endl;
    }
    return 0;
  }
  if (d < 0) {
    x = -x;
    d = -d;
  }
  unordered_map<int, SectionUnion<true>> now;
  for (lint A = 0; A <= n; ++A) {
    // S = Ax + Bd
    lint Bmin = (A - 1) * A / 2, Bmax = (2 * n - A - 1) * A / 2;
    lint Adiv = A * x / d, Smod = A * x % d;
    if (Smod < 0) {
      Smod += abs(d);
      ++Adiv;
    }
    now[Smod].insert(Adiv + Bmin, Adiv + Bmax);
  }
  lint cnt = 0;
  allrep (m, now) {
    allrep (p, m.second.section_set) cnt += p.second - p.first + 1;
  }
  cout << cnt << endl;
  return 0;
}

練習で解く問題が4問の旧ABCばかりなので最近記事を書くほど詰まる問題がなかった。
久々に骨がある問題を解いた。
AtCoder Problemsでも黄上位くらいになっているし、青はかなり手の届く問題になってきたかな。

本番では取り組む時間がなかったので、まっさらな状態からスタート。
こういうシンプルな問題は解き慣れていないので何から手をつけて良いのか全く分からなかった。
解説を読んで方針だけなんとか把握できた。
基礎をしっかりしてないと解けない感じで、こういう問題をしっかり練習するのは大事っぽい。
イメージとしては、簡単なE問題レベルが4つか5つくらい重なった感じ。
自分の簡単なE問題の正解率を70~80%とすると、5つ重なったら正解率20%もないんだが！？となる。

考察

まず重要なのが、Tを考えずにSだけを考えれば良いという置き換え。
Sを決めればTも決まるのでなるほど当然だが、しっかり意識しないと両方考えちゃいそう。
両方考えても解けるのだろうが、やっぱり簡単な方が良いね。
実際Sだけ考えれば良いと分かった段階でかなり先が開けた気がする。

Sについて考えると決めれば、次に行き着くのは選ぶ個数Aを0~Nで固定してループする。
何度も見た解き方なのでこれは問題なく辿り着けるだろうと思う。
次の悩みどころが、個数を固定した上で何通りの選び方があって、他の個数との被りがないか。
これをチェックする必要がある。

まず、何通りの選び方があるかを考える。
ここで生きるのが、各iにおける値を数式で表現する書き方。
ただ単に等差数列という認識ではなく、「X, X+D, X+2D, ..., X+(N-1)D」と捉えることで、A個を選んだ際の合計がAX+BDという形で表現できる。
Bの最低値Bminは、0から1ずつ増やしたA個の合計なので、(0+A-1)*A/2。
Bの最大値Bmaxは、(N-1)から1ずつ減らしたA個の合計なので、{(N-1)+(N-1-A+1)}*A/2 = (2N-A-1)*A/2。
Dの係数は1刻みなので、Bmin~Bmaxまでの間を1刻みで(Bmax-Bmin+1)個の値を作れる(+1は開区間なので)。

AXについては、ループ内ではAを固定しているためAXの値も同じく固定となる。
このことから、Aを固定すると(Bmax-Bmin+1)個の値を作れることになる。

このままでは、他のAを選択した場合の値との被りを考慮していない。
これからがおそらくこの問題の本質なのかな。
解説PDFの、modD毎に考えれば良いという記述、雑ぅ・・・。
理解すれば確かにmodD毎に考えれば良いのだが。
modD毎に考えると、複数の区間を結合して、区間の合計を求めるような問題になる。
集合として考えると、まさしく和集合という感じ。
かなり典型チックな雰囲気を醸し出しているが、懇切丁寧に解説しているような記事はなかった。

modDを理解する部分で大事なのが、AX+BminD~AX+Bmaxを、Bが1刻みになっていると見るのではなく、式全体としてみるとD刻みになっていると捉えること。
つまり、AX+BminD~AX+Bmaxの間でmodDの値は変化せず、その値はAXのみで決まる。
これを式に表すと、AX+BD = (AX/D+B)D+AX%Dとなる(AX/Dは切り捨て)。
この式を見ると、AX%D毎に独立して(AX/D+B)を考えれば被りを防げることが分かるので、(AX/D+B)をBmin~Bmaxの区間を被らないように数える和集合の問題になった。

フレンズのアライグマさんの画像がすっごく分かりやすくて理解をかなり助けてくれた。
アライグマさんの解説

これでほぼ終わりなのだが、ここまで来てこの区間の和集合が難しい。
setで管理すれば簡単だけど計算量的にどうなのって話になる。
問題の設定から、必ず区間は正の方向に被るとか、区間を覆ってしまうような区間は存在しないとか、色々考えたが、そういう細かい部分まで考える必要はなかった。
区間を順に考えるのではなく、一度全ての区間を列挙した後で、区間の最小値(最大値でも良い)でソートする。
そうすれば、問題の設定に関係なく、区間の最小値は必ず逆行することがないという保証が得られる。
後は、現在どこまで区間を選んでいるかを保存しながら走査していけば被りなく区間を数えられる。
やったー解けた！
d=0の場合と、d=0かつx=0の場合は、全然話が変わってくるから注意しよね。

実装

まずmodDに騙された話。
modって巨大な数を扱えないからmod取ったよー＾＾とする場合が多いので、疑いなく二次元配列の要素数としてDの絶対値を取ったのだが、Dの制約が10^8。
僕は学んでいる、二次元配列でその要素数はダメだと。
全体でN+1回しかpush_backされないので、vectorを連想配列に入れれば解決。

modの話はもう1つあって、負の数のmodがなかなか曲者。
C++ではa%b=cとすると、a負ならbに関係なくcは負の数か0になる。たぶん。
正の数にしたかったら、cが負ならbを足せば良いだけなのだが、同時にa/b=dも使う場合は、±1しないと(bの正負によって符号が変わる)、b*d+c=aを満たせなくなってしまう。
符号変わるしcが負でも0だと±1しなくて良いしで面倒臭い。
これを考慮して、dを正に固定してdにプラス1するような実装にしてみたのだが(?コメントの部分)、この+1の部分がなくてもACしてしまう。

なぜ通るかいまいち分かっていなかったのだが、記事を書きながら気付いた。
Xが負ならAX%Dも全て負の数か0になるので、modDが0以外の場合は全てにおいて-1されている状態であり、何通りかという問題に対しては影響を与えず正しい答えが出ているっぽい。
本当は違うんだけどこれでも良いよみたいなのはなぜ通るのか理解しないとすごくもやもやするので、自分なりに解き明かせてよかった。

次はそんなに悩んでないが、やっぱり半開区間便利だねの話。
数列Zi(0<=i<N)のうち今Znowまで見ていて、次の区間(Zmin, Zmax)が得られた時に区間の合計を更新しながらZnowを更新してねとなった時、開区間だと結構ややこしい。
Znow=Z0でZ3~Z9が得られた時、区間の合計に+(9-3)+1する。
しかし、Znow=Z5でZ3~Z9が得られた時は、区間の合計に+(9-5)となり、Z5は既に合計に入っているので+1してはいけない。
Znowの更新はZnow=max(Znow, Z9)で良いのだが、区間の合計は単純なmax関数では計算できず、場合分けが増えるのでミスしやすくなってしまう。

ここで半開区間を使う。
Znow=Z0でZ3~Z9が得られた時、区間の合計は+(9+1)-3。
Znow=Z5でZ3~Z9が得られた時、区間の合計は+(9+1)-5。
Znowの値に関わらず同じ計算式なので、+(max(Znow, Zmin)+1)-max(Znow, Zmin)で良い。
Znowの計算式もZnow=max(Znow, Zmax)で簡単。
半開区間すげー。

最後によくやるミスだが、intの範囲外になる部分をrepのint型の変数のまま計算してしまい、値が大きいケースにWAが連なってた。
最後に直したのがこの部分なのだが、ここまでWA出るとなると考察から間違ってるのかと不安になる。
気付けば、あーここかーという感じ。
long longとして扱いたい部分はしっかりlong longにしていたのだが、計算式の途中でオーバーフローする部分をいつも忘れてしまう。
気をつけよう。

2019/12/17追記
区間をsetで管理するテクなるものがあるようで、典型チックと思った区間の管理部分をまさにやってくれてすごい。
一番悩んだ部分がとっても簡単に書けた。
satanicさんの実装を参考にしたつもりが、ほとんど別物になってしまった。

競プロで基底クラスのポインタに入れるなんて頭のおかしいことはしないはずなので、本当はsetをpublic継承したかった。
しかし書いているうちに区間の左端より右端で比較した方が良くないかという流れになり、pair(左端, 右端)を保ったまま格納するなら通常のsetだといけないということで、比較関数を色々弄っていくうちにスマートに書けないと判断してこの形に。
正直mapの方が理にかなっているのだが、map[右端] = 左端の形は扱いづらすぎる。
クラス内部のprivateなデータならともかく、map自体も外で使う可能性が十分ある中これはちょっと・・・となる。
ま、まぁSTLをpublic継承なんて邪道だし？これで良いよね？

まとめ

自分用メモだしなんでも良いかと見出しとかつけずに改行だけで乗り切る姿勢でいたのだが、あまりに見づらい・・・。
考察と実装とまとめくらいなら頑張れる気がするので、しばらくこのスタイルで行こうかな。
最近ブログレイアウトも変えた(元々横に広いのが良かったが見つけられなかった)のだが、コードのシンタックスハイライトの表示が崩れているっぽい。なぜ。
改行も自動で消えるの毎回意味分かんないし忍者ブログが悪い気がしてならない。
コード部分くらいは直したい。