ARC102「Triangular Relationship」

コンテスト中の考察（おじさんは解けませんでした^^;にゃおーん！！）

愚直にやるとa, b, cを全探索する3重ループになるなー。
$O(N^3)$から$O(NlogN)$くらいに落とすのかなーと思いつつ考察を進めた
Snuke Festivalみたいに真ん中(b)のループ回してa, cを二分探索で求められそうとか思う。無理でした。
いろいろこねくり回して謎の数式たくさん生成した結果解けませんでした！！おしまい！！

理想の考察

一部分について考える

$(a+b), (b+c), (c+a)$をいきなり全部考えると頭爆発する
なので、とりあえずその中の一部分である$a+b$について考えてみる。
$a+b$が$K$の倍数になる条件は、以下のいずれかが当てはまるときである。
1. $a % K + b % K = 0$
2. $a%K+b%K=K$
条件1は、$a, b$がそれぞれ$K$の倍数であるときに成り立つ。
条件2は、$a,b$を$K$で割った余りの和が$K$であるときに成り立つ。

全体的なことを考える

部分的なことはわかったので、全体的なことを考える
$a,b,c$という3つの数を考慮した場合、条件を満たすのは以下のいずれかが当てはまる時である
1. $(a%K, b%K, c%K) = (0, 0, 0)$
2. $(a%K, b%K, c%K) = (\frac{K}{2}, \frac{K}{2}, \frac{K}{2})$
条件1は、全ての要素が$K$の倍数であるときに成り立つ。
条件2は、$(a+b), (b+c), (c+a)$それぞれの和が$K$となる場合に成り立つ

具体的なことを考えていく

大体の方針が立ったので、詳細を詰めていく。

偶奇で処理を分ける

$(a%K, b%K, c%K) = (\frac{K}{2}, \frac{K}{2}, \frac{K}{2})$についてよく考えると、$K$が奇数の場合はこの条件が使えないことが分かる。$K$が奇数のときにこの条件を成り立たせるためには各要素が小数点数である必要がある。だが、制約によりそれは認められないので$K$が奇数の時はこの条件は使わないこととする。
つまり、偶数の時は条件1, 2を適用し、奇数の時は条件1のみを適用する。

組み合わせ方について

$(a, b, c)$に条件に当てはまる数字を組み合わせていくだけ。
例えば条件を満たす数字が5種類あったら、$(a, b, c)$それぞれに5種類ずつ入れるから$5^3=125$が答えとなる。こんな感じで考える。
条件1, 2に当てはまる数字を別々に数える。
その後、$(条件1に当てはまる数字の個数)^3 + (条件2に当てはまる数字の個数)$をした数値が答えとなる。

解法

$x(1 \leq x \leq N)$が$K$の倍数である個数を数え上げる。この個数を$a$とする。
$x(1 \leq x \leq N)$を$K$で割った余りが$\frac{K}{2}$である個数を数え上げる。この個数を$b$とする。
$K$が奇数の場合、答えは$a^3$となる。$K$が偶数の場合、答えは$a^3+b^3$となる。

コード

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int N, K;

int main() {
   cin >> N >> K;

   // Kの倍数である数値の個数を数える
   int64 a = 0;
   for (int x = 1; x <=N; x++) {
      if (x % K == 0) {
         a++;
      }
   }

   // 余りがKの半分となる数値の個数を数える
   int64 b = 0;
   for (int x = 1; x <=N; x++) {
      if (x % K == K/2) {
         b++;
      }
   }

   // 全ての要素がKの倍数の場合を足す
   int64 ans = a * a * a;
   // Kが偶数なら余りがK/2の場合も考慮する
   if (K % 2 == 0) {
      // 全ての要素がK/2の場合を足す
      ans += b * b * b;
   }

   cout << ans << endl;

   return 0;
}

要点

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

類題

ABC096 - D
ABC077 - D
この問題と似たような考え方を使うらしい(by takeoさん)
たぶんどっちも解いたこと無い

感想

なんか数学的な問題が解けない。
なんで解けないのかすらよく分からない。
もう解ける気すらしない。
おなかすいた
解説かなり雑になったし、僕も完全に理解しているわけでは無い。
僕的にこの問題クソムズいんですが、上位陣が10分以内に通しててつおいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいって思った。なんでそんなにすぐわかるんだよ。僕なんかクッソ長い考察書いてようやく理解したぞこの野郎。
ちなみに問題タイトルの「Triangular Relationship」は三角関係っていう意味らしいです！！！夏だから恋愛っぽいタイトルにしてみたんでしょうか！！！僕にはまっっったくかんけいないですがね！えーん ><