Chokudai Contest 004

Chokudai Contest 004

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

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

I got the minimum point of AC solutions, 161761, successfully. #chokudai_004 pic.twitter.com/NaQaRYO9pv

— Kazune Takahashi (@kazune_lab) August 31, 2019

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().

Others