ABC180
Dを間違えてるのに気づかずにEに集中して、残り30分くらいで気づいて慌てて直した
https://gyazo.com/7a99a330842d06c816d8b2e7463ceefd
水色手前での足踏みを継続中…
https://gyazo.com/be704e75e3126bb5928898936b33951e
https://gyazo.com/0ca2c8bea32656c1f05ffa66447bdffc
一言で言えば「約数を列挙せよ」だね
約数列挙は自作ライブラリに入れたのでこんな感じ
code:python
def main():
N = int(input())
for x in get_divisors(N):
print(x)
https://gyazo.com/8f06a617ab10a812d76a3db89b088612
Aが2以上であることから$ (x + B) \times A > x \times A + Bが成り立つので「先に×Aにした方が得」が言える
code: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
最初、a_count += 1 AX *= Aがループの先頭にあったのでAを0回やるタイプの入力でWAになってた
WAに気づいたらすぐ直せたのだけどEに集中してたせいで気づかずに1時間も放置してしまった
https://gyazo.com/35303867fe0d84984d1e647509bfda0a
考えたこと
位数が2以下ということは、各連結成分はサイクルかパスである
最大連結成分がちょうどLなら、Lのサイクルかパスが最低1個ある
それを取り除いたらL以下で配置する問題になる
頂点のラベルが影響する制約がないので、まずグラフの形が決まってからそこにラベルを分配する問題になるかな
サイクルだと数珠順列
多重辺がありなのでL=2のサイクルがある
公式解説