■競技プログラミング AtCoder Beginner Contest 133 C 問題

さらに続けてみましょう。

競技プログラミング AtCoder Beginner Contest 133 C - Remainder Minimization 2019 を解いてみます。

 

問題文

非負整数  L,R  が与えられます。 つの整数  i,j  を  L≤i<j≤R  を満たすように選びます。  (i×j) mod 2019  の最小値を求めてください。

 

これは難しくないですよ。 L から R までのすべての組み合わせを計算して余りを出せば良いです。すべての組み合わせを計算するというのは、前にやった B 問題で学んだことですね。

でも単純に総当たりするのは芸がありません。ある数を 2019 で割った余り m は 0 ≦ m ≦ 2018 ですから、0 が出たらそこで終了、答えは 0 です。0 が出なかったら答えは 2018 以下の最も小さな数になりますね。最も小さな数を抽出するのは A 問題でもやりました。

 

では、以下の流れでプログラムを書いてみましょう。

 

  1. 数値 L R を入力
  2. 範囲外なら Error! を表示してエラー終了
  3. 二つの整数の積を 2019 で割った余りを計算
  4. 余りの最小値を更新
  5. 余りが 0 ならば計算を終了し 7. へ
  6. すべての組み合わせで繰り返し
  7. 余りの最小値を表示

 

プログラム自体は簡単です。チャチャっと書いて入力例を試してみると、うまくいきました。

えらい簡単だったなぁ。でもまぁとりあえずいろんな数値入れて試してみよう。と、大きめの数も入れて確認していくと、500000 あたりからおかしな答えが出てきて、1000000 超えると負数になっちゃった (^_^;)

あれ〜、オーバーフローしちゃったのか〜

 

与える数の最大値が 2×109 だったので int 型でいけるよねぇ〜と考えていたのですが、余りの計算式を

 

remain = i * j % 2019

 

としたために、ここでオーバーフローしてしまったようです。計算の最大値は 4×1018 になりますから long long int 型にしなければいけません。

うーん、int 型でオーバーフローしないような計算方法はないのかなぁ〜 と、アルゴリズムを考え直してみるのは B 問題で学んだことです。

 

考えること小一時間 (^_^;) あった!合同式です。

 

合同式 a ≡ b ( mod n )         a を n で割った余りは b 

 

合同式の掛け算は

 

a ≡ c ( mod n ) 、b ≡ d ( mod n ) のとき、a × b ≡ c × d ( mod n )

 

となります。つまり、「2つの数の積 a × b を n で割った余りは、a、bをそれぞれ n で割った余りの積 c × d と同じ」ということ。このことから前出の計算式は次のようにできます。

 

remain = ( i % 2019 ) * ( j % 2019 ) % 2019

 

これで最大値は 2×109 に抑えられますから int 型で計算できるようになりました。

なお、合同式については「合同式の証明や問題の解き方を解説!大学受験で使いこなそう!」を参考にさせていただきました。

 

ということで、できあがったプログラムです。

 

/*  AtCoder Beginner Contest 133 C - Remainder Minimization 2019
    2019.07.25 by meyon */

 

#include <stdio.h>

 

int main()
{
  // input date
  int L, R;
  scanf("%d %d", &L, &R);
  if (0>L || L>=R || 2000000000<R) {
    printf("Error!¥n");
    return 1;
  }

 

  // modulo
  int ans=2018;
  for (int i=L; i<R; i++) {
    for (int j=i+1; j<=R; j++) {
      int remain=(i%2019)*(j%2019)%2019;
      if(ans>remain) {
        ans=remain;
      }
      if (0==ans) {
        i=R;
        j=R+1;    // end of modulo
      }
    }
  }

 

  // answer
  printf("%d¥n", ans);

  return 0;
}

 

余りが 0 になったときに二重のループを一気に抜けて計算を終了させるのは、条件式が偽になるような値を代入する方法をとっています。break では一つのループしか抜けられません。

 

今回はなかなか良い感じだろうと自画自賛してますが、提出はやっぱりドキドキしますね (^_^;)

 


コメント
コメントする








   
この記事のトラックバックURL
トラックバック

■calendar

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
<< October 2019 >>

■search this site.

■recommend

毎日貯まるポイントサイト ECナビ

■recommend

* 楽天ROOM *

■Twitter

■recommend

■recommend

■selected entries

■categories

■archives

■recent comment

■recent trackback

■links

■profile

■others

■mobile

qrcode

■powered

無料ブログ作成サービス JUGEM