技術室奥プロコン#4day1_G問題_バラバラ掛け算〜すいかの精進旅日記〜
まったりトークコーナー
本番中はとっても苦戦しました！！
ただとっても勉強になって面白かったですし、解説ACもなんとかできたので記事に残しとこうかなーって気分で今書いてます(*'▽'*)
解説
editorial.pdf - Google ドライブ
和が一定，積の最大値はいくつ?|思考力を鍛える数学
わからない！解説が欲しい！って人は正直この辺り見れば十分です☆*:.｡. o(≧▽≦)o .｡.:*☆
解説のページと数学のサイトとってもわかりやすかったです！
（ありがとうございます！）
それでは、ほぼ余談みたいなレベルの解説になると思いますが、それでも良いよって方はお付き合い下さい！
1, 2, 3, 4, 5, 6, ...と和の形に分解してその積の値がどんな時に大きいかを確かめていくと、
1 = 1
2 = 1 + 1 = 2
3 = 1 + 1 + 1 = 1 + 2 = 3
4 = 1 + 1 + 1 + 1 = 1 + 3 = 2 + 2 = 4
5 = 1 + 4 = 2 + 3
6 = 2 + 3 + 1 = 2 + 2 + 2 = 3 + 3
7 = 1 + 6 = 1 + 3 + 3 = 2 + 2 + 3
赤色をつけた分解の仕方が最も積が大きくなっています。ここでなんとなーくわかるのが、２や３の形で分解した方がポイントは大きくなりそうってことですね。もう少し考察を進めて、２や３でどう分解した時が最も大きいかを考えると、６を分解した時に2 + 2 + 2 = 3 + 3の時、2^3 < 3^2となっているので、2の足し算が3つ続いているときは3+3に置き換えた方が良さそうです。ただし、7の時にそれを行うと、1 + 3 + 3と2 + 2 + 3では後者の方が大きくなってしまいます。これは3 + 1と 4を比べた時に後者の方が積が大きくなるからです。
あとは、6を3+3で分解した時が最も大きい数がわかったので、与えられた入力Nを6で割った余りごとに場合分けして求めていけば良いです。この辺については、詳しくてわかりやすくて素晴らしい解説が上記に記した解説PDFにあるのでそれを見てもらえれば良いかなと思います。
それをPythonで実装したものを記します。（ほぼ一緒ですが書き方表記は等若干違うところもあります。）
Q = int(input()) N_list = list(map(int, input().split())) mod = 10 ** 9 + 7 nums = [] for N in N_list: a = N % 6 if N <= 4: num = N elif a == 0: p = N // 3 num = pow(3, p, mod) elif a == 1: p = ((N - 1) // 3) - 1 num = pow(3, p, mod) * 4 elif a == 2: p = (N - 2) // 3 num = pow(3, p, mod) * 2 elif a == 3: p = N // 3 num = pow(3, p, mod) elif a == 4: p = ((N - 1) // 3) - 1 num = pow(3, p, mod) * 4 elif a == 5: p = (N - 2) // 3 num = pow(3, p, mod) * 2 nums.append(num % mod) print(*nums)
余りが3, 4, 5の時は、（ここでは3について）
elif a == 3: p = (N - 3) // 3 num = pow(3, p, mod) * 3
のように、a = 0, 1, 2の流れのまま書くこともできますが、上記のように書くと、余りが0の時と余りが3の時、余りが1の時と余りが4の時が同じ式になっていることがわかります。よって、実はその計算式は周期が3で考えることができるので、Nを3で割った余りで考えることもできます。そうするともう少しスッキリ書くことができて、次のようになります。
Q = int(input()) N_list = list(map(int, input().split())) mod = 10 ** 9 + 7 nums = [] for N in N_list: a = N % 3 if N <= 4: num = N elif a == 0: p = N // 3 num = pow(3, p, mod) elif a == 1: p = ((N - 1) // 3) - 1 num = pow(3, p, mod) * 4 elif a == 2: p = (N - 2) // 3 num = pow(3, p, mod) * 2 nums.append(num % mod) print(*nums)
