MEMORANDUM CEDRETABRI

ARS LONGA VITA BREVIS

AtCoder Beginner Contest 133 C

C - Remainder Minimization 2019

最初に言うと、僕はこの問題に大変な時間を取られ、大きくレートを下げてしまった。 なので、自戒としてこの問題の解説を書くことにする。

概要

 {L..R} の間で  {i} {j} とを定めて、  {(i\times j)\mod2019} を最小化せよ、という問題である。ただし  {0\leq L\lt R\leq2 \times10^9} なので全探索みたいなことはできない。

解法

 {\mod 2019} ということなので、  {i} {j} との差が  {2019} 以上の場合を考える必要はない(何故ならその場合、間には必ず  {n\mod 2019=0} なる  {n} が存在し、それを選ぶことで  {(i\times j)\mod 2019} {0} になるから)。 それさえわかれば、話は単純である。 解法の本質は以下のようなものとなる。

for i in L .. min(L+2019, R)
  for j in i+1 .. min(L+2019, R)
    result <- min(result, (i * j) mod 2019)
  end for
end for

見る範囲は  {L..R} {L..(L+2019)} かの狭い方になる。

実際のコードはこのような形。

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto lr = readln.split.to!(long[]);
    auto L = lr[0];
    auto R = min(L+2020, lr[1]+1);

    long x = long.max;
    foreach (i; L..R) {
        foreach (j; i+1..R) {
            x = min(x, i*j%2019);
        }
    }
    writeln(x);
}

感想

掛け算の性質と剰余の性質とをちゃんと理解しておきたい(できていなかったのが敗因)。

簡単とか難しいとかは、解く人の経験とかに依存するから一概に言うことはできないと思うけど、少なくとも僕の経験を考えれば、「簡単に」解けて然るべき問題だったと思う。 強く強く反省したい。