JAG夏合宿Day1 - ferinの競プロ帳

ABCDEJ → コンテスト中に解いた F: 凸関数 G: DP H: 2数の積の桁長 I: 誤差がやばい K: 畳み込み

K

解説で素直なDPとなっているDPの一例を書く．A[i][j], B[i][j], D[i][j] を解説の通り定める．

初期値 A[0][0]=0, B[0][0]=1, D[0][0]=s[0][0]の数字

遷移 modを取るのは省略して書く

A[i][j]
- A[i][j] = (A[i-1][j]+D[i-1][j]) + (A[i][j-1]+D[i][j-1]) (s[i][j]='+')
- A{i][j] = A[i-1][j] + A[i][j-1] (s[i][j]='*' か数字)
B[i][j]
- B[i][j] = combi(i+j, i) (s[i][j]='+')
- B[i][j] = D[i-1][j] + D[i][j-1] (s[i][j]='*')
- B[i][j] = B[i-1][j] + B[i][j-1] (s[i][j]は数字)
D[i][j]
- D[i][j] = 0 (s[i][j]='+' か '*')
- D[i][j] = 10D[i-1][j]+dB[i-1][j] + 10D[i][j-1]+dB[i][j-1] (s[i][j]=d 数字)

答え
A[h-1][w-1] + D[h-1][w-1]

クエリを「i行目のj文字目は何か？」に帰着するパート
浮動小数点のような持ち方を考えると，2数の積の長さはそれぞれの桁数の和+1+(仮数部の積が10以上か？) となる．仮数部でソートしておくと，仮数部の積が10以上になる最小のb[i]を二分探索で求められるので，i行目が何文字か？を求められる．
行ごとにj文字目は何かを求めていくパート
行yのj文字目が属するマス(y,x)が何か？を高速に求められればいい．xは二分探索で求まる．
複数行について考える場合，仮数部が小さい行から順番に見ると数列に+1する更新しか飛んでこないのでBITで管理できる．

仮数部でソートするのは文字列にして辞書順ソートすると楽
サボってlog2個にしたけど普通に通った