naoya_t@hatenablog

いわゆるチラシノウラであります

Codeforces Round #422 (Div. 2) [Virtual participation]

昨夜参戦できなかったCodeforces Round #422に朝からvirtual参戦(8:05am〜)
いつも通りC→B→A、と行きたかったんだけど
Cの制約を突破する糸口が掴めずパスしてB→Aの後Cに戻って解いて、まだ時間がたっぷりあったのでDへ。

Virtual participationって、実際のコンテストと同じ経過時間で他の参加者が問題を解いていくように見えるのが面白い。(=その時間までにどの問題がよく解かれていたか、のようなメタ情報も参考にできるということ)
f:id:n4_t:20170703112846p:plain

C. Hacker, pack your bags! (x903)

http://codeforces.com/contest/822/problem/C
区間を適当に1つ取ったとして、「その終点より後で始まって、ある長さ以下でいちばん低コストなやつ」をO(\log N)で探せればいいんだよね
ってなんか3次元空間の探索になってる
なんか凄い賢いツリーとか作って解くやつ?
パス

B. Crossword solving (x2925)

http://codeforces.com/contest/822/problem/B
編集距離を求めるのに似てる。insert/delete無しで。
ていうか
開始位置全探索でもO(N^2)程度で解けない?sもtも長さ1000以内だし。
最悪ケースってtが1000で、sがいくつ?s(t-s)が最大になるsってs=500で500^2
1000\cdot500\cdot500=2.5\cdot 10^8だし間に合うでしょ

・とりあえず、どこ始点で最小になるかだけ覚えておいて(どこを?にするか記録してもいいんだけど時間とメモリ食うからしてない)
・その最小始点でもう一度比較して、?になる箇所を列挙しておしまい

→WA
http://codeforces.com/contest/822/submission/28239081
もう一度比較、の時のforループで i, jのjを++していなかった(なんでそれで通るケースがあるんだ)のを修正して

→AC
http://codeforces.com/contest/822/submission/28239107
所要時間:15分ぐらい

A. I'm bored with life (x3895)

http://codeforces.com/contest/822/problem/A
min(A,B)! を求めるだけ。min(A,B)\le 12までとあるし、これは31bitに収まる。

→AC
http://codeforces.com/contest/822/submission/28239161
所要時間:6分弱

C. 再訪

あ。2つの区間の合計がx日以内とかじゃなくて "sum of their durations is exactly x" という制約を見逃してた。exactlyて太文字で書いてくれてるのに。

・長さ(日数)ごとに分ける
・(長さごとの中で)始点ごとに分ける(始点順にソートして、というか同じ長さ・同じ開始日なら最小コストのやつ以外は捨てていいのでmap<int,int>でいい。)
・ある始点より後の最小コストを何らかの方法で計算しておく。というか、始点順にソートして、右から(開始日が遅い順)見てそこまでの最小コストを更新していくだけ。mapの右からのイテレーションはrbegin(), rend()で行けるし。
・こうして [(開始日,そこ以降での最小コスト), ...] という配列 mincost[] が長さごとに作れる。
・↑最悪全部の区間が同じ長さだとしてもO(N\log N)で作れるはず
・全てのi (0\le i\lt N) について、区間iの長さw_i=r_i-l_i+1, コストをc_iとしたとき、終点r_iより後に始まる、長さがちょうどx-w_i区間(があればその)最小コスト mincost(x-w_i, r_i) は、mincost[x-w_i] からlower_bound()で(あれば)拾えるからO(\log N)


→AC
http://codeforces.com/contest/822/submission/28239520
所要時間:56分ぐらい(最初の15分ぐらい+41分)

時間かかったけど一発で通って嬉しい。

D. My pretty girl Noora (x731)

http://codeforces.com/contest/822/problem/D
f(n) の定義域が5e6までで、そこさえ求めてしまえば \displaystyle\sum_{i=0}^{r-l}t^i\cdot f(l+i) はO(N)で計算できる。

さて。f(n)なのですが。
グループに分けない(あるいはnが素数なため分けることができない)場合\displaystyle\frac{n(n-1)}{2}回の比較が必要。
n人をa人ずつのグループに分ける(aはnの約数であるべし;n%a==0)と、グループ数gは当然n/aで
\displaystyle g\cdot\frac{a(a-1)}{2}+f(g)
a人のグループの比較も、それを更に小さく分けていいから
\displaystyle g\cdot f(a)+f(g)
ということで、nの約数{a,...} それぞれについてこれを計算し、minを求めていくDPで良さそう。

もしかして、と思ってnの最小の約数だけでやっても同じ結果になったので最小の約数で。
最小の約数は、エラトステネスの篩を作るときにできるsmallest prime factorテーブルでO(1)で取れる。

→WA
http://codeforces.com/contest/822/submission/28239884

…long longでもdpがオーバーフローするのに気づいた。
5\cdot10^6\cdot5\cdot10^6(5\cdot10^6-1)/2\simeq6.25\cdot10^{19}\simeq2^{66}

int128_t にしたら行ける?と思って書き直したら結果がlong longの時とは違った。やっぱりそうか。
→Compile Error
http://codeforces.com/contest/822/submission/28240043
includeヘッダ何呼べばいいんだ?
いや時間ないし
long longで計算できるように比較部分を書き直して
これで通せる、あれ?submitボタン押せないぞ、と思ったら試合終了ダイアログが出てた
で、再submitしたDはACだった(10:05:06)
http://codeforces.com/contest/822/submission/28240050

あと1〜2秒あれば通せた、というか、AC解が手元にあるのにsubmitできないで試合終了する悔しさ。
この悔しさを何度も味わってみんな強くなっていくんですね(わかりません)

所要時間:43分(あと2秒速ければ)
f:id:n4_t:20170703112827p:plain

E. Liar (x22)

http://codeforces.com/contest/822/problem/E
開いてない

F. Madness (x31)

http://codeforces.com/contest/822/problem/F
開いてない