Manthan, Codefest 16(CF)
出ました。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です。
C
適当にdpして、復元すればいいですね。
Trie木でやったのでO(N max(|wi|))とかそこらです。途中でロリハに変更しようかとも思ったんですけど、今更後戻りできないし、Hashが衝突するくらいなら別にTrie木でもいいや、という感じでやりました。結果としてTrie木の実装がめっちゃ軽かったので、助かりました。
開始36分でAC出来たので、3完の中ではそこそこの順位に入れました。レート落ちなくてよかった...
D
フィボナッチは爆発するので、適当にO(N^2)で開幕を全探索して実際にシミュレーションすれば大丈夫っぽいかなあ..という感じになります。ただ、最初の2項が0,0の場合に計算量が破綻することに気が着けなくて、Hackされたのにresubmit出来ませんでした。つらい。
ちなみに、コンテスト終了後に0,0のケースを対策して提出したのですが、結局TLEしました。その後、mapやsetの使用を可能な限り減らしたら通りました。制約きついです。
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完でレート爆上げ、という感じでしたけど、現実は甘くなかったですね
