Hatena::Grouptopcoder

どせいふんとうき。 RSSフィード

2013/02/25

Round #169

| 16:28 | はてなブックマーク - Round #169 - どせいふんとうき。

Codeforces は初参加でした.提出のフォーマットは AtCoder に近い感じなんですね.いつもどおり C++ で挑戦しました.結果は oo--- でレーティングは 1451 になりました.うーん…….


A.Lunch Rush: 342

計算して最大値を求めるだけのお仕事でした.

B.Little Girl and Game: 854

文字数の偶機に着目する問題でした.コードは通ったんですが数学的に納得していないのでモヤモヤです.

C.Little Girl and Maximum Sum: ---

配列の位置ごとに和に使われた回数をカウント→配列と使用回数をソート→内積をとる.という流れだったのですが,配列のサイズが最大で 2e5 ということで 2 重ループが使えません.どうやって使用回数をカウントするか考えていたら終わってしまいました.

D.Little Girl and Maximum XOR: ---

骨組みを書いただけで終わりました.

E.Little Girl and Problem on Trees: ---

読んでもいません.



Little Girl and Maximum Sum の復習

テストをパスしていた方のコードを読んで勉強しました.核となる部分は dp を使って計算する方法でした.

例えば以下のような入力が与えられた時,

5 3
5 2 4 1 3
1 5
2 3
2 3

和に含まれるかどうかを示すフラグは以下のようなテーブルで表現できます.問題を解くためにほしい情報は列ごとの o の数です.

ooooo
-oo--
-oo--

しかし,表のサイズは最大で 2e5×2e5 になるので単純にループを回してしまうと間に合いません.

ここで重要なのは隣り合う列の o の数は独立でないということです.入力では配列で使用する位置の左端(l)と右端(r)の情報が渡されます.それぞれを和の対象に入った(+1),和の対象から抜けた(-1)という情報にして以下のような配列を作成します.

vector<int64_t> num(n+1,0);
for (int64_t i=0; i<q; ++i) {
  cin >> l >> r;
  num[l-1]++; num[r]--;
}

上のコードで生成される配列は以下のようになります.与えられる配列のサイズは n ですがこの配列は 1 つサイズが大きくなっていることに注意します.

120-200-1

あとはこれを cumulative に足していけば

133111(0)

という欲しかった配列が手に入ります.この方法ならループは 1 重で済むので時間オーバーになりません.

解いてみてすごく「積分」っぽいやり方だなと感じました.最初に生成した配列は変化量だけに注目しているので微分係数(差分)に対応します.最後の累積和はまさに積分のようです.解けなくて悔しかったので同種の問題が出たときには間違いなく倒せるようにしたいところです.