# Chokudai Contest 004

Updated:

Chokudai Contest 004

# Solutions

## A - マス目に数を書き込む問題

### The digest

The main function is as follows.

int main()
{
auto start{chrono::system_clock::now()};
auto goal{chrono::system_clock::now()};
double dif{0};
input();
must_do(); // if L[i][j] == R[i][j], we have to fix ans[i][j] as this value.
make_V();
make_min_ans();
while (true)
{
goal = chrono::system_clock::now();
dif = chrono::duration_cast<chrono::milliseconds>(goal - start).count();
if (dif >= 2994)
{
break;
}
shuffle(V.begin(), V.end(), engine);
make_min_ans();
}
flush();
}


In make_min_ans(), we do brute-force searches for each points $(i, j)$. We try all $L[i][j] \leq v \leq R[i][j]$ as the value of $(i, j)$ and find the value that attains the minimum score of that. At that time we only consider the segments that contains $(i, j)$. We can compute the sums fast by the two-pointers method and the time-complexity is $O(N)$.

We try to reduce the answer as much as possible till the time limit. We continue to shuffle the order of $V$ and call make_min_ans().

Tags:

Categories: