回答編集履歴
3
解説のコードとの違いを説明
test
CHANGED
|
@@ -1,3 +1,17 @@
|
|
|
1
|
+
ご提示のコードと[解説のコード](https://atcoder.jp/contests/abc281/editorial/5366)を比較してみましょう。
|
|
2
|
+
|
|
3
|
+
まず解説のコードですが、「a_1,…,a_i から j 個が選ばれていて、総和を D で割った余りが k であるようなときの総和の最大値(不可能なら −1 )」を1つだけ求めています。
|
|
4
|
+
この場合、「a_1,…,a_i から j 個が選ばれていて、総和を D で割った余りが k であるような」組み合わせに対して、今後追加される可能性がある数字は、a_(i+1),…,a_Nの中にあるもののみとなります。
|
|
5
|
+
|
|
6
|
+
それに対し、ご提示のコードだと、「a_1,…,a_Nから j 個が選ばれていて、総和を D で割った余りが k であるようなときの総和の最大値(不可能なら −1 )」を1つだけ求めています。
|
|
7
|
+
そして、「a_1,…,a_Nから j 個が選ばれていて、総和を D で割った余りが k であるような」組み合わせに対して、今後追加される可能性がある数字は、a_1,…,a_N 内の数字のうち、**まだ使われていないもの**になります。
|
|
8
|
+
しかし、「**まだ使われていないもの**」というのは、「**すでに使われているもの**」に依存してしまいます。
|
|
9
|
+
つまり、ある組み合わせでは使える数字が、他の組み合わせではすでに使われていて使えないという事態が発生します。
|
|
10
|
+
|
|
11
|
+
このように、条件が一様ではないもの(追加できる数字が異なるもの)を一緒くたに扱って、総和が一番大きいもので上書きしてしまってるので、以下で説明するような組み合わせの漏れが発生します。
|
|
12
|
+
|
|
13
|
+
---
|
|
14
|
+
|
|
1
15
|
ご提示のコードですと、正解となる組み合わせが`old`上から消えてしまう場合があります。
|
|
2
16
|
|
|
3
17
|
例えば、以下の入力例で考えてみましょう。
|
2
より簡潔な例が見つかったので、解説を書き直し
test
CHANGED
|
@@ -1,3 +1,74 @@
|
|
|
1
|
+
ご提示のコードですと、正解となる組み合わせが`old`上から消えてしまう場合があります。
|
|
2
|
+
|
|
3
|
+
例えば、以下の入力例で考えてみましょう。
|
|
4
|
+
正しい出力は「44」(先頭から4つの数値の合計)ですが、ご提示のコードですと「-1」が返ります。
|
|
5
|
+
```
|
|
6
|
+
6 4 22
|
|
7
|
+
3 9 14 18 30 42
|
|
8
|
+
```
|
|
9
|
+
|
|
10
|
+
まず、2回目のループの後に`old`がどうなるか見てみましょう。
|
|
11
|
+
|余り|合計|組み合わせ|
|
|
12
|
+
|--:|--:|:--|
|
|
13
|
+
|0|44|[4,2]|
|
|
14
|
+
|1|45|[0,5]|
|
|
15
|
+
|2|||
|
|
16
|
+
|3|||
|
|
17
|
+
|4|48|[4,3]|
|
|
18
|
+
|5|27|[1,3]|
|
|
19
|
+
|6|72|[4,5]|
|
|
20
|
+
|7|51|[1,5]|
|
|
21
|
+
|8|||
|
|
22
|
+
|9|||
|
|
23
|
+
|10|32|[2,3]|
|
|
24
|
+
|11|33|[0,4]|
|
|
25
|
+
|12|56|[2,5]|
|
|
26
|
+
|13|||
|
|
27
|
+
|14|||
|
|
28
|
+
|15|||
|
|
29
|
+
|16|60|[3,5]|
|
|
30
|
+
|17|39|[4,1]|
|
|
31
|
+
|18|||
|
|
32
|
+
|19|||
|
|
33
|
+
|20|||
|
|
34
|
+
|21|21|[0,3]|
|
|
35
|
+
|
|
36
|
+
この時点で、`[0,1]`(合計12), `[0,2]`(合計17), `[1,2]`(合計23)の組み合わせは、より合計が大きくなる組み合わせがあるため、`old`内から排除されています。
|
|
37
|
+
このため、次のループで`[0,1,2]`(合計26)という組み合わせが`old`上に現れることはありません。
|
|
38
|
+
|
|
39
|
+
次に、3回目のループの後に`old`がどうなるか見てみましょう。
|
|
40
|
+
|余り|合計|組み合わせ|
|
|
41
|
+
|--:|--:|:--|
|
|
42
|
+
|0|||
|
|
43
|
+
|1|||
|
|
44
|
+
|2|90|[4,3,5]|
|
|
45
|
+
|3|69|[1,3,5]|
|
|
46
|
+
|4|||
|
|
47
|
+
|5|||
|
|
48
|
+
|6|||
|
|
49
|
+
|7|51|[4,3,0]|
|
|
50
|
+
|8|74|[2,3,5]|
|
|
51
|
+
|9|75|[0,5,4]|
|
|
52
|
+
|10|54|[0,5,1]|
|
|
53
|
+
|11|||
|
|
54
|
+
|12|||
|
|
55
|
+
|13|57|[4,3,1]|
|
|
56
|
+
|14|||
|
|
57
|
+
|15|81|[4,5,1]|
|
|
58
|
+
|16|||
|
|
59
|
+
|17|||
|
|
60
|
+
|18|62|[4,2,3]|
|
|
61
|
+
|19|63|[0,5,3]|
|
|
62
|
+
|20|86|[4,2,5]|
|
|
63
|
+
|21|65|[1,5,2]|
|
|
64
|
+
|
|
65
|
+
先ほど述べたとおり、`[0,1,2]`(合計26)は、本来であれば余り4のところに現れるはずですが、存在していません。
|
|
66
|
+
また、`[0,1,3]`(合計30), `[0,2,3]`(合計35), `[1,2,3]`(合計41)の組み合わせは、より合計が大きくなる組み合わせがあるため、`old`内から排除されています。
|
|
67
|
+
このため、次のループで、正しい答えである`[0,1,2,3]`(合計44)という組み合わせが`old`上に現れることはありません。
|
|
68
|
+
|
|
69
|
+
---
|
|
70
|
+
以前の解説
|
|
71
|
+
|
|
1
72
|
ozwkさんの記法を使わせてもらうと、old(k)からold(k+1)が求められるという前提が間違っています。
|
|
2
73
|
|
|
3
74
|
old(k)は、k個の項目の和dをDで割った余りが同じ組み合わせの中から、dが最大のものだけを保存します。
|
1
和が最大値となる組み合わせを1つしか保持していないのが原因ではないとの調査結果を追記
test
CHANGED
|
@@ -16,3 +16,26 @@
|
|
|
16
16
|
(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])
|
|
17
17
|
```
|
|
18
18
|
もっとシンプルな例が出せればよかったのですが、WAの入力例しか見つかりませんでした。
|
|
19
|
+
|
|
20
|
+
---
|
|
21
|
+
|
|
22
|
+
ちなみに、以下のコードを仕込んだうえで、WAの入力例を処理しても、「1」が表示されることはありません。
|
|
23
|
+
つまり、和が最大値となる組み合わせが複数見つかったとしても、それらは並び順を除けばすべて同じということです。
|
|
24
|
+
私も最初は、和が最大値となる組み合わせを1つしか保持していないのが原因だと考えていましたが、少なくともこの入力例については違う原因でした。
|
|
25
|
+
```python
|
|
26
|
+
for j, a in enumerate(A):
|
|
27
|
+
if j in m:
|
|
28
|
+
continue
|
|
29
|
+
dn = d + a
|
|
30
|
+
##
|
|
31
|
+
if new[dn % D][0] == dn:
|
|
32
|
+
mn = copy.copy(m)
|
|
33
|
+
mn.append(j)
|
|
34
|
+
if set(new[dn % D][1]) != set(mn):
|
|
35
|
+
print(1)
|
|
36
|
+
##
|
|
37
|
+
if new[dn % D][0] < dn:
|
|
38
|
+
mn = copy.copy(m)
|
|
39
|
+
mn.append(j)
|
|
40
|
+
new[dn % D] = (dn, mn)
|
|
41
|
+
```
|