競プロ日記

ついにこのブログにもシンタックスハイライトがやってきたぞ！

コード
https://atcoder.jp/contests/abc127/submissions/7097782

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(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(V, v) for (auto &&V : v)
#define all(x) (x).begin(), (x).end()
const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
using lint = long long;

using namespace std;

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int q;
  cin >> q;
  vector t(q), a(q), b(q);
  rep(i, q) {
    cin >> t[i];
    if (t[i] == 1) cin >> a[i] >> b[i];
  }
  multiset<int, greater> l;
  multiset r;
  int lmax = -INF, rmin = INF;
  lint lsum = 0, rsum = 0, bsum = 0;
  int mid;
  bool mid_ava = false;
  rep(i, q) {
    if (t[i] == 1) {
      if (mid_ava) {
        if (a[i] < mid) {
          r.insert(mid);
          rmin = mid;
          rsum += mid;
          l.insert(a[i]);
          lmax = max(lmax, a[i]);
          lsum += a[i];
        } else {
          l.insert(mid);
          lmax = mid;
          lsum += mid;
          r.insert(a[i]);
          rmin = min(rmin, a[i]);
          rsum += a[i];
        }
      } else {
        if (a[i] < lmax) {
          l.erase(l.begin());
          mid = lmax;
          l.insert(a[i]);
          lmax = *l.begin();
          lsum += a[i] - mid;
        } else if (a[i] > rmin) {
          r.erase(r.begin());
          mid = rmin;
          r.insert(a[i]);
          rmin = *r.begin();
          rsum += a[i] - mid;
        } else {
          mid = a[i];
        }
      }
      mid_ava = !mid_ava;
      bsum += b[i];
    } else {
      cout << (mid_ava ? mid : lmax) << " " << rsum - lsum + bsum << "\n";
    }
  }
  return 0;
}

シンタックスハイライトはやってきたものの入力が面倒くさい。
毎回このクソ面倒なタグ手打ちすんの・・・？
WordPressならテンプレートとかありそうで便利そうだなぁ。
そもそも解説ブログではないので必要ではないかもしれないが、わざわざリンクから飛ぶのも面倒で難しいところ。


今回は時間の見積もりは大事だよっていうお話。
今回はD問題とF問題でTLEをかましてやった。
TLEにはなったもの、WA1回もなしでA～Fまで答えにたどり着けたのはかなりの成長を感じる。

D問題は明らかに早い実装を思いついたのでそれでACになったが、F問題は思いついた後にこれは遅いだろうという間違った考えを挟んでしまった。
「aの中央値を求めてbは定数項にまとめて～」という問題の解き方自体は、クエリを数回適当に手書きしてみると分かった。

1,2回目の実装

最小のx：
ソートされたaの配列から中央値を求める。

最小のf(x)：
ソートされたaの配列の(右から1番目-左から1番目)+(左から2番目ー右から2番目)+...を繰り返す(奇数の場合は中央を含まない)。
(配列のサイズ/2)回繰り返すことで、奇数の場合も中央を含まないように合計できる。

この実装はaが大きくなってくるときついだろうとは思っていたものの、クエリの更新がないとaは増えないし、クエリの更新は処理が軽いし、いける可能性はあるのではという儚い願いは崩れ去る。
最初はvecterに入れて出力クエリの度にソートをしてTLEだったので、おそらく一番遅いであろうソートをなくすためにmultisetに入れてみるもTLE。
だめなのは(配列のサイズ/2)回繰り返すところなんだろうなぁと気づいて悩む。
クエリが2*10^5あるんだから、更新出力クエリが半々だとしても最大でO(10^10)くらいになっちゃうもんなぁ・・・。

たどり着いたのがaの配列を左半分と右半分に分けること。
左半分と右半分は合計値で保管しても良いというのに気付けるかが全てだった。
両端の差+2番目の差+...と考えずに、(a[n]-a[0])+(a[n-1]-a[1])+...と式としてとらえていれば移行してすぐに気付けたかもしれない。
これが上のコードなのだが、更新クエリの処理が明らかに色々やってて遅そう。
こうなるのが分かっていたから一旦諦めてしまった。
ループの中が単純な方が早そうだが、頑張って色々詰め込んだとしてもループなしの方が早いのである。
そりゃそうではあるんだけど、ループ回数とか考えるとなかなか正確な判断が下せない。
実行速度・オーダーに関する勘みたいなのを養っていかないとなぁ。

それでなんやかんや細かい処理頑張ってなんとかAC。
WA食らったのが、「multisetのeraseすると対象の値全てを削除する」ことを知らなかったため。
1つだけ削除するのかなと思って値を入れてeraseしていたので、イテレータで削除するようにするとACできた。
multiset使って正解にたどり着くの初めてやねん！
いつかの問題でmultiset使ってうまく行かずにやめた記憶があるが、うまく行っていればそこで同じミスをして、今回は間違わなかったかもしれない。
ABC127をAから通して初WAなので、間違わなければWAなしでABC127通せたわけでそっちの方が良かったなぁと少し。
それでもAから通して初WAがF問題は実装精度の向上を感じる。
解説を見ても右半分と左半分に分けていたので、思考面も向上していて嬉しい限り。
細かい部分はちょっと理解できなかったけど分けるまで同じでACできてるなら大筋は同じだろう。
BITでも解けるよと書いててどう実装するのか気になる部分ではある。
問題を読んでセグメントツリーとかBITとか使えそうと思わずにはいられなかったが、データをどう処理すれば良いのか全く分からなかった。
「凸性に基づいた値自体に対する三分探索」についてはマジで何言ってんのか分かんねぇ。

今回実行時間が300ms程度と結構かかっており、他の人のを見ると2桁msが結構あってはえーなーBITつかってんのかなーとか思ったわけです。
今回入出力多かったしここらで入出力の速度の違い見てみるかと、今までそこまでシビアなことしてなかったから良いかとテンプレートに入れていなかったこいつらを試してみた。

今日はABCなさそうだしあるとしたら明日かな？
あったら頑張って参加するぞい！