AtCoder Regular Contest 098参加記

部内での共有用に久々に書いてみようと思います。
まあ参加記であって解説では無いんですが...

AtCoder Regular Contest 098 - AtCoder

C - Attention

リーダーを決めると、後は他の人がどちらを向いているか数えるだけになって嬉しいです。
が、よく見るとN<=10^5なので解けません。難しい。
「範囲和を取るときは累積和」の一般的なテクが使えるのでこれを使いましょう。
-1参照しそうになったり+-1で結構悩んでしまった。
Submission #2562951 - AtCoder Regular Contest 098

※ところでpythonのstr.count関数とかCのstrlen関数とかはO(|S|)かかるので気を付けましょう。

D - Xor Sum 2

D - Xor Sumという配点の割に正解者がかなり少なかったことで有名な問題(僕にとっては難しい問題、強い人にとっては割と典型らしい)があるのでちょっと身構えました。
が、名前が似た問題は往々にして全然違う問題なので、先入観を捨てて取り掛かりましょう。

まずは問題整理
xorとsumはかなり似た演算ですが、少しだけ違いがあります。

xor sum
0,0 0 0
0,1 1 1
1,0 1 1
1,1 0 10

これを見るとAl...Arでの演算に(bit単位で)1,1を含むとき(bit&を使うとAl&...&Ar!=0)だけが、不等号が成り立つ可能性がある事が分かります。
そこで、これが不等号が成り立つ必要十分条件であるとエスパーします。(これは僕が証明をしていないという意味)

そうすると、(l,r)のとき等号が成り立つならば(l+1,r)のとき等号が成り立つ事がわかります
つまり、とりあえず出来るだけ長めのものを数え上げれば数え上げの総数が減って嬉しい感じになりそうです。
こういう時に重複を省きながら数え上げる一般的なテクとして、「末尾(or先頭)がiのとき」を数え上げるというものがあります。(たぶんこのテクに名前は無い)

また、(l,r)のとき等号が成り立たないならば(l-1,r)のとき等号は成り立たない事もわかります
言い換えると、短いもので成り立たないならば、より長いものでは成り立たないということです。

これは
区間の先頭を1ずつ右にずらす
区間長が変わる
のでこういうときの一般的なテクの「尺取り法」を試してみたくなります。

実際に考えてみると
・左側は縮む一方で、伸びることは無い
・伸びる方は今までの累積和/xorに加算/xorすることで構築可能
・縮む方は今までの累積和/xorに減算/xorすることで構築可能
であるので尺取り法が使えることが分かります。

この方針でO(N)なので解くことが出来ます。
Submission #2564186 - AtCoder Regular Contest 098

E - Range Minimum Queries

X−Yをできるだけ小さくしたい問題ときたら決め打ち+二分探索みたいな先入観で突っ込んでいって大当たりしました。


まあそれだけでは解けないんですが。
ここまででO(NlogN)使ってるけどN<=2000なのでまだO(N)使える

範囲内の値を
・Y以下の値を避けながら
・Q 回取り除かないといけない
ので少し考えます。
Y以下の値が無ければ貪欲に端から取り除いて良いのは明らか(本番ではこれ証明してなかった)
Y単調増加させればY以下の値が範囲内に存在するかはBIT使って求められるなぁ(使わない考察)
値を取り除く操作をしたい=>区間のN番目の最小値を求めたい=>尺取りmultisetで行けそう

書く。
Submission #2565822 - AtCoder Regular Contest 098
TLEしたなんで

良く考えるとO(N^2 * (logN)^2)
logNは1では無くて10(重要)
10^8だね悲しい。

しょうがないので対策を考える。
取り除くやついちいち識別しているからlogかかるので、差異を無視したい。
出来るね。
書く。コードが闇。特にdeleted_useable (Qに含められるものの内、既に操作をして取り除いたやつの個数)
Submission #2567510 - AtCoder Regular Contest 098
通った

TLEに気が付いてればもうちょいタイムロス少なく出来そう

余談
言れて気が付いた

F - Donation

まだACしてないですが、結構惜しいとこまで行った気がする(気のせいかもしれない)
始めよりも終わりの方が制約が大きいのでとりあえず遡りを考えてみる。
行けるところ適当に行って損しないので、適当に全部行くことが出来る。これは良い。
始点O(N) * 全部行けるかどうか試すO(NlogN)
600点分くらい解いた気がするけどまだ間に合わない。
始めに持っておく余剰資金分を決めてやると走査を同時に走らせることが出来るので始点O(N)が消滅してO(NlogN)で間に合う
出会ったらマージ出来るので計算量をO(NlogN)で頭打ちに出来る。
まあ識別番号としてUFtree使ったりとかする必要はありますが。

実装は間に合わない
2018-05-26 22:39:59の提出:
Submission #2570788 - AtCoder Regular Contest 098
テストも何もしてなかったので、まず出力部が正しくなくて、本当は

out << std::accumulate(all_range(B),(int64_t)0)+ok_range << endl;

って書きたかった。
ところでこれ直してもまだ通らないんですが何処が間違ってるんでしょうね。