ABC180

I didn’t realize I made a mistake on D, concentrated on E, realized it with about 30 minutes left, and rushed to fix it. Continuing to step in front of the light blue…

C - Cream puff

• 
• In a nutshell, it’s “List the Approximate Numbers.”
• I put the approximate enumeration in a homebrew library, so here’s what it looks like python

def main():
    N = int(input())
    for x in get_divisors(N):
        print(x)

D - Takahashi Unevolved

• 
• Since A is greater than or equal to 2, $(x+B)\times A>x\times A+B$, we can say “it is more profitable to do xA first”. python

def solve(X, Y, A, B):
    AX = X
    a_count = 0
    ret = 0
    while AX < Y:
        rest = Y - 1 - AX
        b_count = rest // B
        ret = max(ret, a_count + b_count)
        a_count += 1
        AX *= A

    return ret

• First, a_count += 1 AX *= A was at the top of the loop, so it was a type of input that does A 0 times and it was WA.
  • I could have fixed it as soon as I noticed the WA, but I was so focused on E that I didn’t notice it and let it sit for an hour.

ABC180E AC after contest

F - Unbranched []](https://atcoder.jp/contests/abc180/tasks/abc180_f)

• 
• Thoughts.
  • The fact that the number of degrees is less than or equal to 2 means that each connected component is either a cycle or a path
  • If the largest connected component is exactly L, there is at least one cycle or path of L
    • Take that away and it becomes a matter of placing it under L.
  • Since there are no constraints that the labels of the vertices affect, I wonder if it would be a matter of first determining the shape of the graph and then distributing the labels to it.
    • If it is a cycle, it is a bead permutation.
  • There are multiple edges, so there is an L=2 cycle.
• Official Explanation
  • count(X=Y)=count(X⇐Y)-count(X⇐Y-1)

---

This page is auto-translated from /nishio/ABC180 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.