Codeforces Round #415 (Div. 1) C. Find a car

dpの遷移が複雑すぎるだろ。

問題概要

縦10⁹, 横10⁹の合計10¹⁸個のマス目があり、上からi番目, 左からj番目のマス目を(i, j)と表す。マス目に以下のルールで数を書き込んでいく:

• マス(i, j)には、マス{(x, j) | 1 ≦ x < i}とマス{(i, y) | 1 ≦ y < j}に書かれている数全てを除いた上で、最小の自然数(0は含まれない)を書き込む。
• つまり、マス(i, j)には、そのマスの左と上を見て、書かれていない数の内、最小のものを書く。
• 当然(1, 1)は1とする

具体的には、以下のような形になる(問題文から引用)

以下の質問に対して Q回答えよ:

• x1, y1, x2, y2, kが与えられるので、長方形区間{(x, y) | x1 ≦ x ≦ x2 ∧ y1 ≦ y ≦ y2}について、k以下の数が書かれているマスについて、それらのマスに書かれている数の総和を答える。
• ただし総和はあまりにも大きな数になるので、10⁹+7で割った余りを答えれば良い。

制約

• 1 ≦ Q ≦ 10⁴
• 1 ≦ x1 ≦ x2 ≦ 10⁹
• 1 ≦ y1 ≦ y2 ≦ 10⁹
• 1 ≦ k ≦ 10⁹

解法

まず求めたい値をcalc(x1, y1, x2, y2)とおくと、calc(x1, y1, x2, y2) = calc(1, 1, x2, y2) - calc(1, 1, x1-1, y2) - calc(1, 1, x2, y1-1) + calc(1, 1, x1-1, y1-1)に分解できるので、全て(1, 1)から考えて良いことがわかる。 ここから少し考察すると、(1, 1)を含む任意の長方形状のマス目は簡単な操作で2倍に拡大できる事に気づく。

つまり、

こういうことで、 例えば

この性質を用いれば、まあ倍倍にしていけば、ぐらいで計算できそうだな、というのは分かる。ここからが問題。 基本的にdpをするんだけど、dpの遷移が大変なので本当に辛かった。 やはり遷移を直で200行ぐらい書くよりは、悩んでもいいからループでちゃんと遷移をまとめる方が良いなという気持ちになった。 具体的な方針としては、1x1の1個のマス目から初めて、目的の長方形へ伸ばしていって、その際に必要な値をdpとして伝搬させて行く。この際、最終的な最大値kから逆算して、各過程に置いて許される最大値というものを前計算しておく。 つまり例えばk = 7だったとすれば、1つ前の長方形ではk' = 4である必要がある、これは長方形を2倍した時、マス目の値も2倍か2倍-1されるから。 まずdpとして持つ状態は、

• どの部分のマス目を考えているか - 右端、下端、右下のマス、それ以外の4通りが必要になる
• 最大値かどうか - 桁dp的な考え方をする必要がある。つまり、上記のように、マス目のに書かれている数が各過程において可能な最大値である場合、場合によっては2倍すると不適となる場合がある。
• 例えば上記の例でマスの数が4であった場合、2倍すると8になるが、許される最大値が7である時、これは不適となる。

また、遷移の式は、dp[i+1][nj][nk] += dp[i][j][k]*2 - num[i][j][k]のようになるわけなので、実はマス目の総和だけでなくて、条件に適するマス目の個数というのも持っておく必要がある。ちなみに僕は誤読していて個数を求める問題だと思っていて200行直書き遷移を書き直す必要が出てきて詰んだ。

書いたコード

まあ本当に遷移は頑張るという感じで、こういう問題は嫌いですが、本番中に1発で通せるべきだよなあと思い反省の意を込めてこの記事を書いておきます

Codeforces Round #415 (Div. 1) C. Find a car