pyてよn日記

一寸先は闇が人生

ABC108: C - Triangular Relationship

概要

 ABC108のC問題で余り(mod)を扱う問題が出た。コンテスト中ACできなかったので丁寧に考察をした。modを扱う問題についての考察の流れを確認。

私の現在

 興味ない方飛ばしてOK。現在灰色コーダー(200強)。最近他のことで競プロに触れてなくて、思うようにレートが伸びない。何事もやり始め多くの時間をかけたほうがいいよなあと思いつつ...現在は、B問題を解けるようになってきたが、コンテスト中C問題は一度しか解けたことがないという状況。

modを扱う問題

 余り(mod)を考える問題は競プロだと結構出てくる。コンテスト中解けなくて解説で「modを使って解くんだよ」ってことがよくある。今まで「数学的な知識が必要なのか、これじゃ解けないなあ」と敬遠気味だったが、こういう問題をコンスタントにACさせないといけないという思いが強くなってきたので、本記事でmodに関する問題をしっかり考察して苦手意識を無くしていきたいと思う。

類題

ABC108 C問題 Triangular Relationship

 直近でやった「3つの数を足してKの倍数になる組み合わせを求める問題」。全探索するとO(N3)となるのでもちろんTLEになる。(問題名からコンテストページへ飛べる。)

まずは小さく考える

 一気に考えられないので、問題を小さくして考える。
まず、2つの数の和がKの倍数になるとはどういうことか。これを満たすための2つの数a, bの条件は、

2つの数の和がKの倍数になる条件    a\%K + b\%K = 0\ or\ K

である。具体例を見ると直感的に分かりやすい。

e.g.)
 K = 8のとき、

  •  (a, b) = (16, 32)の時は、(a\%K,\ b\%K) = (0, 0)

  •  (a, b) = (7, 9)の時は、(a\%K,\ b\%K) = (7, 1)(mod 8の和が8)

上記の例はどちらも2つの数の和が8の倍数になっている。

まとめると、a+bがKの倍数であるためには、

2つの数の和がKの倍数になる条件

  • aとbがともにKの倍数である
  • aとbの mod K の和がKの倍数である

のどちらかである必要がある。特に、2つ目の条件が問題を考察する上で大切である。

2つ目の条件:2つの数のmod K の和がKの倍数である

 2つ目の条件について考察していく。a+bをKの倍数にするためにはどのように a, bを設定すれば良いだろうか?

aを適当に取り、 a\%K = nとする。このとき、 b\%K = K-n という数になるようにbを設定すれば、 a+bがKの倍数になる。つまり、 a\%K + b\%K = nK(n = 1, 2, ...)である。

e.g.)

  •  K = 8, (a, b) = (7, ?)のとき、(a\%K,\ b\%K) = (7, ?)

 a\%K = n = 7である。 a+bを8の倍数にするためには、 b\%K = K - n = 1 になるようにbを取る必要がある。よって、 b = 1, 9, 17, ...という数をとれば a+bが8の倍数になることが分かる。

3つの数の内、どの2つを足してもKの倍数になる条件

 ここまでの考察を3つの数の場合に拡張する。
a, b, cという3つの数の内、どの2つを足してもKの倍数になる、つまり a+b,\ b+c,\ c+a が全てKの倍数になるための条件は、

3つの数の内、どの2つを足してもKの倍数になる条件

  •  (a\%K,\ b\%K,\ c\%K) = (0, 0, 0)
  •  (a\%K,\ b\%K,\ c\%K) = (K/2, K/2, K/2)

のどちらかしかない。分かりやすく言うと、

3つの数の内、どの2つを足してもKの倍数になる条件

  • 3つの数全てがKの倍数である
  • 3つの数全てのmod K が K/2である

のどちらかである。1つ目は理解しやすい。2つ目が分かりづらい。2つの数の和を考えた時は、 a\ mod\ Kの数から、うまく帳尻を合わせるようにbを定めれば二つの数はKの倍数になった。3つの数のそれぞれの和が同時にKの倍数になるように設定する時は単純にはいかない。どのように設定すれば良いだろうか?

適当にaを取り a\%K = nとし、 b\%K = K-n という数になるようにbを設定する。
問題の条件より、cをa, bどちらに足してもKの倍数にならないといけない。2つの和を考えた時のように、cをうまく設定して帳尻合わせをする。

  • b+cをKの倍数にするためには、 c\%K=nを満たすようなcを設定する
  • c+aをKの倍数にするためには、 c\%K=K-nを満たすようなcを設定する

これを同時に満たすcは存在するのか?

簡単な例を3つ考える。
e.g.)

  •  K = 7(7の倍数, 奇数),\ (a, b, c) = (5, 2, ?)

    • (b+c)を7の倍数にする。
      --> cをbに合わせるためにはc = 5, 12, 19...
    • (c+a)を7の倍数にする。
      --> cをaに合わせるためにはc = 2, 9, 16...
      つまり二つ同時に満たすcは存在しない。
      実は、K/2は整数なのでKが奇数の時は本来考えなくてい良いのだが、例として示すために奇数でもやって見た。以降、Kは偶数で考える。
  •  K = 6\ (6の倍数, 偶数),\ (a, b, c) = (5, 7, ?)

    • (b+c)を6の倍数にする。
      --> cをbに合わせるためにはc = 5, 11, 17...
    • (c+a)を6の倍数にする。
      --> cをaに合わせるためにはc = 1, 7, 13...
      つまり二つ同時に満たすcは存在しない。
  •  K = 6\ (6の倍数, 偶数),\ (a, b, c) = (9, 15, ?)

    • (b+c)を6の倍数にする。
      --> cをbに合わせるためにはc = 3, 9, 15...
    • (c+a)を6の倍数にする。
      --> cをaに合わせるためにはc = 3, 9, 15...
      つまり二つ同時に満たすcが存在する。
      これは、 a\%K = b\%K = c\%K = K/2になっている。条件の二つ目を満たしているのである。

ここまでの例から実は以下のことも分かる。

 n \neq K-n のとき、
 a+b,\ b+c,\ c+aが同時にKの倍数となるような数は存在しない

 n = K-n より、  n = \cfrac{1}{2}K、つまり  a\ mod\ K \cfrac{1}{2}K じゃないと3つの数それぞれの和はKの倍数にならないってこと。

解法

ここまでの考察から問題の解法をまとめると、

Kが奇数の時、

  • 3つの数全てがKの倍数である

Kが偶数の時、

  • 3つの数全てがKの倍数である
  • 3つの数全てのmod K がK/2である

を満たす数を数え上げて、その数を3乗して(重複を許した3つの数の順列)おしまい。

modを考える問題で大事なポイント

  • 和がKの倍数である数の組が存在する時、それぞれの数の mod Kの和はKの倍数

という考え方がよく出てくるみたい。数式で表すと、

  •  (a+b+...)\%K = 0のとき、 a\%K + b\%K + ... = nK\ (n = 1, 2, ...)

倍数を考える問題 --> modを考える

という思考の流れが大事なようなので次出てきた時はなんとかACしてやりたい。

上記の考え方は以下の記事を参考にさせていただいた。TwitterでFFの方の記事。大変参考になりました。

  • いきなり全体的なことを考えるのが大変だったら、まずは一部分について考える(これ「友達の友達」でも使った考え方)
  • 倍数が出てきたら、modを意識する
    • modを使うと状態のグループ分けがしやすい
    • Kで割った余りがK/2になる場合とか、modを使ったおかげで考えることも減ったし処理が楽になった。
    • 「a, b,cをKで割った余りの和がKになるとき、(a+b+c)はKの倍数になる」ってのは覚えといて損はない気がする。

終わりに

 Twitterは解法の宝庫でした。早く自分も解法を生み出す側になりたい。記事中の間違い、こんな類題あるよって方はコメントで教えていただければ幸いです。最後まで読んでくださりありがとうございました。

参考記事

以下の記事を参考させていただきました。