RustとAtCoderを勉強する(typical90_at)

はじめに

AtCoder の問題を Rust で解いていきます。AtCoder も Rust も初心者ですが、温かい目で成長を見守っていただけるとありがたいです。

今回は、競プロ典型90問の046 - I Love 46（★3）を解きました。

問題

$3$ つの長さ $N$ の数列 $A=(A_1,A_2,\cdots,A_N),B=(B_1,B_2,\cdots,B_N),C=(C_1,C_2,\cdots,C_N)$ から、$A_i+B_j+C_k\equiv0(mod\,46)$ を満たす $(i,j,k)(1 \le i,j,k \le N)$ が何通りあるかを求める問題です。

制約

• $1 \le N \le 10^5$
• $0 \le A_i,B_j,C_k \le 10^9$
• 入力は全て整数

提出コード

解説

$(A_i+B_j+C_k)(mod\,46)=((A_i \, mod \, 46)+(B_j \, mod \, 46)+(C_k \, mod \, 46))(mod\,46)$ となる性質を利用するそうです。まず、数列 $A,B,C$ の全要素に対して $46$ で割った余りを求めます。次に、それら余りが何個あるかを数えます。余りとその個数を求め、HashMap にする関数を vec2hashmap_mod46_counter() としました。この関数を動作確認用に少し改変したものが下のコードです。

このように HashMap<余り, 個数> とすれば、あとは

のようにして答えを求めることが出来ます。

まとめ

• 余り・合同式難しい
• itertools::iproduct! が便利