コードは二乗和を最大化するためには、モジュロ

Question

入力をm個：

3 1000 
2 5 4 
3 7 8 9 
5 5 7 8 9 10 

出力ウィウル各リストで最高の要素を選択するために、206をd、私が提供した場合、それは(5^2+9^2+10^2)%1000=206

になり、その要素を二乗和を取ると、m

ので使ってモジュラス操作を行う入力、などの

3 998 
6 67828645 425092764 242723908 669696211 501122842 438815206 
4 625649397 295060482 262686951 815352670 
3 100876777 196900030 523615865 

予想される出力は974ですが、私は、私はあなたがこの問題にアプローチする方法をかexistin修正する方法を知りたい624

を取得していますgコード。

Answer 1

あなたの質問はあまり明確ではありません。しかし、正しく理解すれば、f（X1）、...、f（Xn）（おそらくX1、...、Xnのすべての可能な値にfを適用して得られる）の可能な値のリストがあります。 f(X1)^2 + ... + f(Xn)^2を最大にしたいですか？

もしそうなら、あなたのコードは良いようだ、私は同じ結果を得る：ちょうどあなたのコードのように、この印刷624

lists = [[6, 67828645, 425092764, 242723908, 669696211, 501122842, 438815206], 
[4, 625649397, 295060482, 262686951, 815352670], 
[3, 100876777, 196900030, 523615865]] 
sum = 0 
for l in lists: 
    sum += max(l)**2 
print(sum%998) 

を。あなたはどこから974を手に入れていますか？

Answer 2

重要なのは論理的な問題ここでは、forループのmax要素を見つけながら各リストの項目数をスキップする必要があります。それは代わりに

例、

6 67828645 425092764 242723908 669696211 501122842 438815206 

で、であり、あなたのデータはあなたが使用する必要があり、

input().split() 

ある

67828645 425092764 242723908 669696211 501122842 438815206 

、

input().split()[1:] 

です

Paul Hankinさんが指摘しているように、基本的に最大（％mの合計）を見つける必要があります 合計％mが最大の3つのリストから組み合わせを見つける必要があります。

だから、これは基本的に、

あなたは各行の値の数である第一の要素を残して、スペースを入力し、分割をスキャンされ、あなたは整数にマップします。そして、四角形を見つけてリストsに追加します。製品（[1,2]、[3,4,5]）は、[（1,1）、（1,2）、（1,3）、 （2,1）、（2,2）、（2,3）]となる。今度は、そのような結果の合計％mを見つけて、最大値を見つけることができます！

ある

、

k,m=map(int,input().split()) 
from itertools import product 
s=[] 
for _ in range(k): 
	s.append(map(lambda x:x**2,map(int,input().split()[1:]))) 
print(max([sum(i)%m for i in product(*s)])) 

Try it online!

これはあなたに必要な出力が得られます！

希望すると助かります！

Answer 3

max（（正方形の合計）m）を見つける必要があります。これは、モジュロmのmax（二乗和）と同じではありません。

それはあなたが可能な限り大きく絶対的にではないのですが、あなたはモジュロMそれを取るときに最大である二乗和を見つけることかもしれません。例えば

：

m=100 
[10, 9], 
[10, 5] 

ここでは、正方形の最大合計が（+ 100 81）= 0モジュロ100の最大値（二乗和モジュロ100）である100 + 100 = 200であります182はモジュロ100の82です。

mを小さくすると、O（m * N）時間で実行される高速ダイナミックプログラミングソリューションがあります。ここで、Nはすべてのリストのアイテムの総数です。

def solve(m, xxs): 
    r = [1] + [0] * (m - 1) 
    for xs in xxs: 
     s = [0] * m 
     for i in xrange(m): 
      for x in xs: 
       xx = (x * x) % m 
       s[i] += r[(i - xx) % m] 
     r = s 
    return max(i for i in xrange(m) if r[i]) 

m = 998 
xxs = [ 
    [67828645, 425092764, 242723908, 669696211, 501122842, 438815206], 
    [625649397, 295060482, 262686951, 815352670], 
    [100876777, 196900030, 523615865]] 

print solve(m, xxs) 

これは、必要に応じて974を出力します。