読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

Manthan, Codefest 16(CF)

codeforces.com

出ました。300位くらい ooox---- 2008->2016(+6)でした。残念...

A

よくあるdpをしました。
AC:http://codeforces.com/contest/633/submission/16352023


↓サンプルすら通らない謎の解法を投げて1WAした。反省
(http://codeforces.com/contest/633/submission/16351375)

B

n!を因数分解したときに5がちょうどm回登場すればいいわけです。nを5ずつ増やしていって、登場する5の数がちょうどm個になるタイミングがあれば、答えが5個存在すると分かります。そのようなタイミングが無い場合、答えは0です。

AC:http://codeforces.com/contest/633/submission/16353337

C

適当にdpして、復元すればいいですね。
Trie木でやったのでO(N max(|wi|))とかそこらです。途中でロリハに変更しようかとも思ったんですけど、今更後戻りできないし、Hashが衝突するくらいなら別にTrie木でもいいや、という感じでやりました。結果としてTrie木の実装がめっちゃ軽かったので、助かりました。

開始36分でAC出来たので、3完の中ではそこそこの順位に入れました。レート落ちなくてよかった...

AC:http://codeforces.com/contest/633/submission/16357926

D

フィボナッチは爆発するので、適当にO(N^2)で開幕を全探索して実際にシミュレーションすれば大丈夫っぽいかなあ..という感じになります。ただ、最初の2項が0,0の場合に計算量が破綻することに気が着けなくて、Hackされたのにresubmit出来ませんでした。つらい。

ちなみに、コンテスト終了後に0,0のケースを対策して提出したのですが、結局TLEしました。その後、mapやsetの使用を可能な限り減らしたら通りました。制約きついです。

AC:http://codeforces.com/contest/633/submission/16372736

G

実はDを提出したあとGを開きました(名前に"Tree"が入っていたので、実装が重いだけの問題であることを期待した感じ)

あるsubtree内のノードの値を一様に加算するクエリと、あるsubtree内のノードの値で(a_v≡p mod M)となるようなものが存在するようなMより小さい素数pの個数を求めるクエリ、という2種類のクエリが来る問題。

クエリがsubtreeに対してしか来ないので、オイラーツア―テクニックで木を列にしてsegtreeとかで頑張れば行けそうな感じがします。(加算のほうのクエリは頻出ですし)

segtreeの各要素にM個の0,1からなるbit列を持たせて、加算が来たらbitシフト、もう一方だったら&演算を行えば一応行けることが分かります。めっちゃ計算量が死ぬ(O(NMlogN))のですが、bit列を50個ずつに分けてbit並列化すれば通るような気がしたのでそれを実装しました。ただし、本番では一か所ミスをしていたのでWAが取れませんでした。

後でバグに気付いたので書き換えて提出したんですが、TLEでした。上位陣のコードを見てみると、みんなbit列をbitsetで持ってやっていたので、真似したらACしました。bitsetはめっちゃ高速に動作するのでしょうか・・・?

segtreeのノード数が10^5とかあって、それぞれに1000個の0,1を持ったbitsetをもたせているので、そもそもメモリがしにそうな気がするのですが、MLEもしなかったので、bitsetは{時間、空間}計算量どちらの面でもいい感じなんでしょうか・・・。

AC:http://codeforces.com/contest/633/submission/16374566

まあ理想はABCDGの5完でレート爆上げ、という感じでしたけど、現実は甘くなかったですね