** 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)

ABC182 Summary

Total number of submissions: 7497

performance

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

Correct answer rate by color

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

Brief commentary

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)

screenshot.351.png

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

A problem "twiblr"

** Problem page **: A --twiblr ** Gray Coder Correct Answer Rate **: 99.1% ** Brown Coder Correct Answer Rate **: 99.5% ** Green 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 ** Gray Coder Correct Answer Rate **: 69.9% ** Brown Coder Correct Answer Rate **: 97.7% ** Green 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 ** Gray Coder Correct Answer Rate **: 42.3% ** Brown Coder Correct Answer Rate **: 87.7% ** Green 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)

[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!

table of contents

ABC182 Summary

performance

Correct answer rate by color

Brief commentary

Results of me (Unidayo) (reference)

A problem "twiblr"

Consideration

code

Problem B "Almost GCD"

Consideration

code

C problem "To 3"

Consideration

Implementation

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

How to judge multiples of 3

You can't erase everything

code