** A, B, C problems ** of ** AtCoder Beginner Contest 182 ** will be explained as carefully as possible with ** Python3 **.

I am aiming to explain a solution that satisfies the following three points, not just a method that can be solved.

--Simple: You don't have to think about anything extra --Easy to implement: I'm glad that mistakes and bugs are reduced ――It doesn't take long: The performance goes up and you have more time left for later problems.

If you have any questions or suggestions, please contact ** Comments ** or ** Twitter **! Twitter: u2dayo

[ABC182 Summary](# abc182-Summary) [A problem "twiblr"](#a problem twiblr) [B problem "Almost GCD"](#b problem almost-gcd) [C problem "To 3"](#c problem to-3)

Total number of submissions: 7497

Performance | AC | Score | time | Ranking(Within Rated) |
---|---|---|---|---|

200 | AB---- | 300 | 37 minutes | 5814(5649)Rank |

400 | ABC--- | 600 | 96 minutes | 4832(4668)Rank |

600 | ABC--- | 600 | 44 minutes | 3991(3829)Rank |

800 | ABCD-- | 1000 | 100 minutes | 3118(2956)Rank |

1000 | ABCD-- | 1000 | 50 minutes | 2306(2144)Rank |

1200 | ABCDE- | 1500 | 96 minutes | 1631(1475)Rank |

1400 | ABCDE- | 1500 | 67 minutes | 1117(965)Rank |

1600 | ABCDE- | 1500 | 50 minutes | 744(596)Rank |

1800 | ABCDE- | 1500 | 37 minutes | 483(341)Rank |

2000 | ABCDE- | 1500 | 27 minutes | 304(181)Rank |

2200 | ABCDEF | 2100 | 97 minutes | 185(88)Rank |

2400 | ABCDEF | 2100 | 80 minutes | 110(40)Rank |

color | Number of people | A | B | C | D | E | F |
---|---|---|---|---|---|---|---|

Ash | 3040 | 99.1 % | 69.9 % | 42.3 % | 12.5 % | 2.9 % | 0.0 % |

tea | 1461 | 99.5 % | 97.7 % | 87.7 % | 51.8 % | 12.7 % | 0.1 % |

Green | 1122 | 99.5 % | 99.5 % | 97.2 % | 87.5 % | 50.7 % | 0.6 % |

water | 692 | 100.0 % | 100.0 % | 98.8 % | 97.7 % | 86.6 % | 3.6 % |

Blue | 357 | 100.0 % | 100.0 % | 99.2 % | 98.9 % | 97.2 % | 24.4 % |

yellow | 134 | 96.3 % | 96.3 % | 95.5 % | 96.3 % | 91.8 % | 59.7 % |

orange | 27 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 77.8 % |

Red | 7 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % |

- Display rate, ash does not include first-time participants </ font>

- A problem (7436 people AC) "twiblr"
- Arithmetic.
- B problem (6249 AC) "Almost GCD"
- $ A_i $ can be up to $ 1000 $. $ 1000 $ is never divisible by numbers greater than $ 1001 $. You can actually try how many $ 2 $ to $ 1000 $ are divisible by each and output the maximum number.
- C problem (5077 people AC) "To 3"
- $ N $ is less than $ 10 ^ {18} $. That is, there are only up to $ 18 $ digits. There are $ 2 $ ways to erase digits, up to $ 18 $ for each digit, with or without erasing. There are about $ 26 $ 10,000 in $ 2 ^ {18} $ streets, so you can try erasing all the digits and see if it's a multiple of 3. This is the so-called ** bit full search ** algorithm. Note that you are not allowed to erase everything to $ 0 $, in which case you will print $ -1 $.
- D problem (3419 people AC) "Wandering" [not explained in this article]
- Use the cumulative sum. You may understand it by writing it on paper.
- E problem (1988 AC) "Akari" [not explained in this article]
- For all up to $ 50 $ million light bulbs, it's too late to look at the light bulbs. ** "I know that the future is already illuminated" ** If you stop at this point, the amount of calculation will be $ O (HW + N + M) $ and it will be in time.
- F problem (233 people AC) "Valid payments" [not explained in this article]
- It seems to be dynamic programming.
### Results of me (Unidayo) (reference)

I think I should have thought about the D problem a little more calmly.

# A problem "twiblr"

** Problem page **: A --twiblr ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 99.1% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.5% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.5%

## Consideration

It's a simple math, but it's a waste to get a penalty with momentum, so you may want to stop and check it.

## code

`A, B = map(int, input().split()) print(2 * A + 100 - B)`

# Problem B "Almost GCD"

** Problem page **: B --Almost GCD ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 69.9% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 97.7% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.5%

## Consideration

** Suppose you have a positive integer $ K $. $ K $ is never divisible by a number greater than $ K $. ** For example, $ 6 $ is never divisible by numbers greater than $ 7 $.

The maximum value of the sequence in this problem is set to $ 1000 $, so it is certain that numbers greater than $ 1001 $ will not be divisible by $ 1 $ given.

You can try all the divisible sequences, from $ 2 $ to $ 1000 $, which are candidates for the answer.

## code

`N = int(input()) A = list(map(int, input().split())) ans = 0 current_max = 0 for x in range(2, 1001): score = 0 #Divided number (GCD degree) for a in A: if a % x == 0: score += 1 if score > current_max: ans = x current_max = score print(ans)`

# C problem "To 3"

** Problem page **: C --To 3 ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 42.3% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 87.7% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 97.2%

## Consideration

It may seem like a problem that requires mathematical consideration, but in fact, it can be solved without devising ** "Search all possible ways to erase digits and judge" **.

The $ N $ constraint is less than $ 10 ^ {18} $. It has a maximum of $ 18 $ digits. For each digit, there are $ 2 $ ways to erase or not erase. Therefore, there are up to $ 2 ^ {18} $ ways to erase digits. $ 2 ^ {18} = 262,144 $. You can try them all in time.

(The $ 1 $ way to erase all digits is not allowed, so it's actually $ 2 ^ {18} -1 = 262,143 $, but it's included for simplicity)

## Implementation

### The two ways of "use / not use" are "bit full search"

When you want to search all $ 2 $ streets of "use / not use" like this problem, use the so-called ** "bit full search" ** method.

The details of bit full search are omitted. (Actually I want to write in detail, but it is hard to write in detail every time a full bit search comes out, so I may summarize it somewhere)

In python, full bit search is easier with the

`product`

of the`itertools`

module.`from itertools import product product((True, False), repeat=l)`

If you write this, all combinations that can be made with either

`True`

or`False`

for each element will be generated with a length of $ l $.### How to judge multiples of 3

** "Erase the numbers, stick them together back to an integer, and determine if it's divisible by $ 3 $" seems obviously annoying. ** **

Therefore, it can be easily implemented by using ** "a certain integer $ N $ is a multiple of $ 3 $" ⇔ "the sum of the numbers in each digit of $ N $ is a multiple of $ 3 $". ** **

(Example: $ 18 → 1 + 8 = 9 $, $ 762 → 7 + 6 + 2 = 15 $)

Specifically, create a list of $ N $ decomposed by $ 1 $ digits. For example, $ 1234567 $ would be

`[1,2,3,4,5,6,7]`

. If you want to use a certain digit without erasing it, add it to the sum of digits, and if you erase it, do not add it. And finally, you just have to determine if the sum of digits is a multiple of $ 3 $.### You can't erase everything

If you erase all the digits, the sum of digits will be $ 0 $, so it will always be a multiple of $ 3 $. However, this issue is not allowed.

It is troublesome to exclude it, so if the answer is the default value, you can output $ -1 $.

## code

`from itertools import product #For the time being, after receiving it as a character string S, it is easier to handle if it is made into a list A of numbers for each digit. # N = 6227384 -> A = [6,2,2,7,3,8,4] S = input() A = [int(x) for x in S] l = len(S) #The number of digits in S (since S was received as a string, len(S)Can be used) ans = l for bits in product((True, False), repeat=l): digit_sum = 0 #It is the sum of the unerased digits score = 0 #The number with the digits erased, the smaller the number, the better for i, bit in enumerate(bits): if bit: #Use without erasing the i-th digit from the top digit_sum += A[i] else: #Erase the i-th digit from the top score += 1 if digit_sum % 3 == 0: #If the erase method is a multiple of 3, update the minimum value. ans = min(ans, score) if ans == l: #It wasn't a multiple of 3, so-Output 1 print(-1) else: print(ans)`

Recommended Posts