Q&A
AtCoder ABC281の問題は、AからExまで8問ありますので、D - Max Multipleであることを明記してください。
また、問題へのリンクのご提示もお願いします。
実現したいこと
ここに実現したいことを箇条書きで書いてください。
- AtCoder ABC281 D - Max Multiple のWAを解消したい(02_rnd_04.txtのみ通りません。)
問題: https://atcoder.jp/contests/abc281/tasks/abc281_d
提出: https://atcoder.jp/contests/abc281/submissions/38906904
該当のソースコード
コード内にコードの説明を追加しました。
Python
1import sys 2import copy 3 4 5stdin = sys.stdin 6 7ni = lambda: int(ns()) 8na = lambda: list(map(int, stdin.readline().split())) 9ns = lambda: stdin.readline().rstrip() 10 11N, K, D = na() 12A = na() 13 14old = [(-1, []) for _ in range(D)] # Dで割った余りnそれぞれに対し、old[n] = ((Dで割った余りがnになるもののうち最大のもの), (最大となるときに用いたAの要素のインデックス)) 15old[0] = (0, []) # 0個のAの要素を用いたときで初期化 16 17for i in range(K): # DPを用いて、1〜K個のAの要素を用いたときでoldを更新していく。 18 new = [(-1, []) for _ in range(D)] 19 for d, m in old: 20 if d == -1: 21 continue 22 for j, a in enumerate(A): 23 if j in m: 24 continue 25 dn = d + a 26 if new[dn % D][0] < dn: 27 mn = copy.copy(m) 28 mn.append(j) 29 new[dn % D] = (dn, mn) 30 old = new 31 32 33print(old[0][0])
補足情報（FW/ツールのバージョンなど）
下記にテストケースが公開されています。02_rnd_04.txtのみ通りません。エッジケースでもなくただのランダムケースなので詰んでいます。
02_rnd_04.txtの内容を記載します。
input
198 70 22 217096559 766405565 804429679 84257473 574087672 682206981 926560922 600021616 682445370 652604027 201314351 927105156 679340342 660728814 383622075 285589314 182284197 687206515 31124020 27662047 326058514 156545435 590310385 192593521 321700744 777412132 990038735 806894778 96122313 176239779 547637388 323210461 35653200 511887643 976452260 242864826 279740888 181955557 920559861 372723449 447181609 826720343 622156745 203298686 710918650 838194246 580762090 707052188 907287756 341123612 41476794 707952930 598154395 342610123 417976248 337559654 769913440 196375870 173337362 176944354 592907291 604654771 385486788 326640935 642680254 437170554 638572318 881717794 951978982 908566479 797638095 237171256 931168386 791228334 221969252 857964611 52734986 410850715 327359101 129251286 924817124 365840393 327644854 975752491 695542942 455368048 736391473 399932810 647635285 503985731 867195563 505817949 801848394 115840385 846351364 32299388 887257649 56307152
out
145732572468
追記させていただきました。ご回答の方よろしくお願いいたします。
読んでいませんが、おそらく動的計画法で解いているんですよね？
ならば AC になるコードを取ってきて、今のコードとそのコードで二つの配列を作り、逐次比較してみれば何かわかるんじゃないでしょうか。
if new[dn % D][0] < dn:
この部分なのですが、new[dn % D][0] == dn が成り立つ場合は、その組み合わせもチェックする必要があるのではないでしょうか。
Zuishinさん、試みてみます。ありがとうございます。
melianさん、コメントありがとうございます。
23行目
```python
if j in m:
continue
```
において暫定的にS内に含まれているAの要素との重複をチェックしていること、及びご指摘の、new[...][0]に格納される整数(言い換えると、dnが代入される部分です)が同じ場合にはnew[...][1]はどちらでも良いことから、ここはチェックをしないことにしています。こちら、私の認識間違いがございましたら教えていただけますと幸いです。
dn の最大値が複数ある場合、それらのインデックスを j1, j2 とすると以下の new[dn%D][1] を作成して、それぞれで DP を実行する必要があるのではないでしょうか。
new[dn%D][1].append(j1) # j1 を追加したもの(j2 は含まれていない)
new[dn%D][1].append(j2) # j2 を追加したもの(j1 は含まれていない)
AC になる方法を尋ねているのではなく、どうしてこれでうまくいかないかを知りたいということですが、既存の回答の通り切り捨ててはいけないものを切り捨てています。
問題が長いとわかりにくいと思うので、簡単なものを作ってみました。
6 4 4
7 4 5 5 5 2
以上は、4 + 5 + 5 + 2 = 16 が答えになりますが、質問のコードでは -1 を出力します。
各周の new を出力させてみると、次のようになります。
[(4, [1]), (5, [2]), (2, [5]), (7, [0])]
[(12, [2, 0]), (9, [1, 2]), (10, [2, 3]), (11, [1, 0])]
[(16, [2, 0, 1]), (17, [2, 0, 3]), (14, [2, 0, 5]), (15, [2, 3, 4])]
[(-1, []), (21, [2, 0, 1, 3]), (22, [2, 0, 3, 4]), (19, [2, 0, 3, 5])]
3 周目に (14, [2, 0, 5]) とありますが、ここで要素 5 の 2 を使っているために、14 に 2 を足すことができなくなり、16 という正解が出なくなっています。
質問のコードで不正解になるデータは多くあり、AtCoder で WA が 1 つしか出なかったのはたまたまということになります。
うまくいかない理由の主なものは、ループの順番を間違えていることです。
K を最も外側で回していますが、ここでは A を回すべきでしょう。
この質問者、前の質問でも教えてもらったのに自己解決してるな。
教えてもらうのが悔しいなら聞かなきゃいいのに。
Zuishinさん、前回の質問に関してですが、18:26に追加のコメントがあり18:29に自己解決としています。これはそれ以前のコメントがわかりにくく参考にならなかったため自分で試行錯誤をしたのちに自己解決でき、それを投稿する直前に追加のコメントがあった次第となります。最初から追加のコメントの内容が記載されており参考になったのであればもちろんベストアンサーにしましたが、最初のコメントが投げやりで参考になっていなかったため自己解決にした次第です。ご理解よろしくお願いいたします。
そのコメントは追加質問の 5 分後。それから 3 分後の自己解決。
質問者にとってわかりにくいかどうかなんて質問者以外にわかるわけないし、8 分で自己解決するのも不自然です。
投げやりとは言うけど、WA になるケースを具体的に示した回答なので、不親切とは思いません。
2 と 10 のどちらが大きくなるかというケースを示せば、よほどの初心者ではない限り理解できるじゃありませんか。
むしろなぜこれでわからないのか疑問です。
追加質問を投げている間にも自分で試行錯誤しているなんてことは余程の初心者でもわかるとおもいますが、、、
余程の初心者はstrのままで数値評価ができないということに気づかないんですよ。当時の自分はそれぐらい余程の初心者でした。その上で試行錯誤をして自分で突き止めた次第です。これだけ説明したらさすがのあなたでもわかりますでしょうか？
また、他のコメントにも全て返信させていただいている通り、私は他人に教わることでプライドが傷つくとかそういったことを考えたことすらございませんでした。Zuishinさんはプライドが傷ついて当然だという価値観で生きていらっしゃるのですね。楽しそうで羨ましいです。
自己解決できるのにあの回答で理解できない理由がわからないという意味で、初心者は関係ないですね。
このあなたの反応から、とにかく意味不明なプライドがあることがわかります。
まあ羨ましいなら、回答がついて数分経つ前に自己解決できるようになればいいと思いますよ。
回答3件
0
ベストアンサー
ご提示のコードと解説のコードを比較してみましょう。
まず解説のコードですが、「a_1,…,a_i から j 個が選ばれていて、総和を D で割った余りが k であるようなときの総和の最大値(不可能なら −1 )」を1つだけ求めています。
この場合、「a_1,…,a_i から j 個が選ばれていて、総和を D で割った余りが k であるような」組み合わせに対して、今後追加される可能性がある数字は、a_(i+1),…,a_Nの中にあるもののみとなります。
それに対し、ご提示のコードだと、「a_1,…,a_Nから j 個が選ばれていて、総和を D で割った余りが k であるようなときの総和の最大値(不可能なら −1 )」を1つだけ求めています。
そして、「a_1,…,a_Nから j 個が選ばれていて、総和を D で割った余りが k であるような」組み合わせに対して、今後追加される可能性がある数字は、a_1,…,a_N 内の数字のうち、まだ使われていないものになります。
しかし、「まだ使われていないもの」というのは、「すでに使われているもの」に依存してしまいます。
つまり、ある組み合わせでは使える数字が、他の組み合わせではすでに使われていて使えないという事態が発生します。
このように、条件が一様ではないもの(追加できる数字が異なるもの)を一緒くたに扱って、総和が一番大きいもので上書きしてしまってるので、以下で説明するような組み合わせの漏れが発生します。
ご提示のコードですと、正解となる組み合わせがold上から消えてしまう場合があります。
例えば、以下の入力例で考えてみましょう。
正しい出力は「44」(先頭から4つの数値の合計)ですが、ご提示のコードですと「-1」が返ります。
6 4 22 3 9 14 18 30 42
まず、2回目のループの後にoldがどうなるか見てみましょう。
| 余り | 合計 | 組み合わせ |
|---|---|---|
| 0 | 44 | [4,2] |
| 1 | 45 | [0,5] |
| 2 | ||
| 3 | ||
| 4 | 48 | [4,3] |
| 5 | 27 | [1,3] |
| 6 | 72 | [4,5] |
| 7 | 51 | [1,5] |
| 8 | ||
| 9 | ||
| 10 | 32 | [2,3] |
| 11 | 33 | [0,4] |
| 12 | 56 | [2,5] |
| 13 | ||
| 14 | ||
| 15 | ||
| 16 | 60 | [3,5] |
| 17 | 39 | [4,1] |
| 18 | ||
| 19 | ||
| 20 | ||
| 21 | 21 | [0,3] |
この時点で、[0,1](合計12), [0,2](合計17), [1,2](合計23)の組み合わせは、より合計が大きくなる組み合わせがあるため、old内から排除されています。
このため、次のループで[0,1,2](合計26)という組み合わせがold上に現れることはありません。
次に、3回目のループの後にoldがどうなるか見てみましょう。
| 余り | 合計 | 組み合わせ |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | 90 | [4,3,5] |
| 3 | 69 | [1,3,5] |
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | 51 | [4,3,0] |
| 8 | 74 | [2,3,5] |
| 9 | 75 | [0,5,4] |
| 10 | 54 | [0,5,1] |
| 11 | ||
| 12 | ||
| 13 | 57 | [4,3,1] |
| 14 | ||
| 15 | 81 | [4,5,1] |
| 16 | ||
| 17 | ||
| 18 | 62 | [4,2,3] |
| 19 | 63 | [0,5,3] |
| 20 | 86 | [4,2,5] |
| 21 | 65 | [1,5,2] |
先ほど述べたとおり、[0,1,2](合計26)は、本来であれば余り4のところに現れるはずですが、存在していません。
また、[0,1,3](合計30), [0,2,3](合計35), [1,2,3](合計41)の組み合わせは、より合計が大きくなる組み合わせがあるため、old内から排除されています。
このため、次のループで、正しい答えである[0,1,2,3](合計44)という組み合わせがold上に現れることはありません。
以前の解説
ozwkさんの記法を使わせてもらうと、old(k)からold(k+1)が求められるという前提が間違っています。
old(k)は、k個の項目の和dをDで割った余りが同じ組み合わせの中から、dが最大のものだけを保存します。
しかし、その最大の組み合わせに要素を1つ追加したものが、必ずしも(k+1)個の和を最大にするとは限りません。
k個の和が最大でない組み合わせに要素を1つ追加したもののほうが、(k+1)個の和が大きくなる場合がありえます。
例えば、WAとなる入力例に対して、old(69)[2]は以下の組み合わせで、そこに36番目の要素(279740888)を追加した結果がold(70)[0]となり、その和は45706581800となります。
(45426840912, [11, 34, 68, 26, 72, 83, 80, 69, 6, 48, 75, 96, 67, 90, 38, 92, 94, 27, 41, 2, 70, 25, 45, 44, 73, 56, 1, 84, 86, 51, 12, 5, 17, 8, 47, 9, 66, 88, 61, 13, 52, 64, 22, 7, 4, 30, 60, 46, 42, 89, 85, 33, 91, 77, 62, 40, 54, 65, 81, 39, 14, 87, 20, 55, 49, 53, 82, 78, 31])
しかし、実際には、それより和が小さい以下の組み合わせ(和を22で割った余りは上と同じで2)に82番目の要素(327644854)を追加した場合の方が、和が45732572468となり、先ほどの値より大きくなります。(old(69)[2]には、すでに82番目の要素が含まれるので、82番目は追加できない)
(45404927614, [1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 17, 20, 22, 24, 25, 26, 27, 30, 31, 33, 34, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 51, 52, 54, 55, 56, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 75, 77, 78, 80, 81, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 94, 96])
もっとシンプルな例が出せればよかったのですが、WAの入力例しか見つかりませんでした。
ちなみに、以下のコードを仕込んだうえで、WAの入力例を処理しても、「1」が表示されることはありません。
つまり、和が最大値となる組み合わせが複数見つかったとしても、それらは並び順を除けばすべて同じということです。
私も最初は、和が最大値となる組み合わせを1つしか保持していないのが原因だと考えていましたが、少なくともこの入力例については違う原因でした。
python
1 for j, a in enumerate(A): 2 if j in m: 3 continue 4 dn = d + a 5 ## 6 if new[dn % D][0] == dn: 7 mn = copy.copy(m) 8 mn.append(j) 9 if set(new[dn % D][1]) != set(mn): 10 print(1) 11 ## 12 if new[dn % D][0] < dn: 13 mn = copy.copy(m) 14 mn.append(j) 15 new[dn % D] = (dn, mn)
投稿2023/02/21 15:25
編集2023/02/24 13:36
総合スコア2555
0
以下の様な print 式を入れてみました。dn % D == 0 の場合のみを表示していて、new[0][1][-1] は dn の最大値のインデックスになります。
python
1 for j, a in enumerate(A): 2 if j in m: 3 continue 4 dn = d + a 5 ## 6 if dn % D == 0 and new[0][0] == dn: 7 print(new[0][1][-1], j, dn, i) 8 ## 9 if new[dn % D][0] < dn:
02_rnd_04.txt を入力とした実行結果は以下の通りです。ozwk さんから報告がありました、正答に含まれている 24 と 63 が j の値として出現していますが、if new[dn % D][0] < dn: としているので A[24] や A[63] は除外されます。(この後、A[24] と A[63] は候補に挙がってきません) また、正答に含まれない 36 が含まれてしまっていることも確認できます。
python
126 69 1898605214 1 268 11 2855536398 2 383 72 3873411872 3 4 : 5 649 24 44444268726 65 # j = 24 782 31 44762504578 66 882 63 44762504578 66 # j = 63 982 20 45089147774 67 1082 63 45089147774 67 # j = 63 11 : 12 1336 20 45706581800 69 # new[0][1][-1] = 36 1436 78 45706581800 69 # new[0][1][-1] = 36 15 : 16
投稿2023/02/20 21:13
総合スコア21611
0
Python3で実行すると出力が45732572468ですが、
PyPyで実行したところ45706581800になりました。
おそらく精度(桁数)絡みでしょう
質問文の方法は
「Aからk個の要素を選んだとき、その総和の余りがnであるもののうち、最大である組」を
old(k)[n](もとのコードにkは添字として現れませんが説明のためつけました)としたとき、
old(k)からold(k+1)を求めようとしています。
あまり論理的なことも、具体的な条件も言えなくて申し訳ないのですが
この方法だとなにかの拍子に不正解の要素(今回だとA[53])を選ぶ組を大半のold[n]が採用してしまうと、
不正解の要素を選ばない組は採用されにくくなります。
以後の選択によってはすべてのold[n]で不正解の要素を選んでしまって、正解にたどり着くことが不可能になります。
投稿2023/02/20 05:27
編集2023/02/21 00:04
総合スコア13553
ありがとうございます。
私の方でAtCoder上のPyPy2, PyPy3, Python3.8, ローカルのPython3.9で試したところ、いずれも誤答の`45706581800`と出力されました。ozwkさんがお使いになった環境を詳細に教えていただけますでしょうか？
Python3については勘違いでした。
正答が出る(と思っていた)というのは本題ではなくて、
おそらく桁数絡みで誤答になっているのでは?というのが本題です
pythonにおける整数除算系(// 及び %)は誤差が出ないと認識しているのですが、この認識が誤っている、ということになりますでしょうか、、、？
確認ですが、質問は「どうやったら正しく計算できるか」ではなく「なぜこれで計算できないか」ですよね?
前者であれば解説を読めばいいだけなので。
とりあえず正答では24,63番目の要素を使っていますが、誤答では代わりに36,53番目を使っています。
左様です、「なぜこれで計算できないか」が質問になります。
取り急ぎ、情報ありがとうございます。
あなたの回答
tips
プレビュー
