PythonでABC175 Dを解く #Python

はじめに

タイトルにPythonとありますが、PyPyを使わないと間に合わないです。
どうみてもタイトル詐欺です。本当にありがとうございました。
~~うるせぇ、PyPy使わせろ~~

D - Moving Piece

考えたこと
似た問題が最近のABCに出ていました。過去問と今回の問題の大きな違いは、グラフの形が6みたいな形なのか、円なのかです。過去問は6みたいな形だったのでサイクルに入るタイミングも記録する必要がありました。しかし、今回の問題はグラフの形が円になります。

与えられるグラフがサイクル(閉路)を持つ理由:
与えられるグラフがサイクルを持たないとすると、グラフは木になり、子ノードを持たないノード(行き先がないノード)が存在することになる。しかし、条件より$P$は$N$の順列なので、子ノードを持たない($P_i$が空)は存在しない。よって与えられるグラフはサイクルを持つ

与えられるグラフの形が円になる理由：
与えられるグラフの形が円ではないと仮定する。上記より与えられるグラフはサイクルを持つ。円でないサイクルの始点は二つのノードと結ばれている(行き先が一緒⇔$P_i = P_j (i \neq j)$が存在する)。
しかし、条件より$P$の要素は$N$の順列なので、$P$の要素が複合することはない。よって、二つ以上の点と結ばれている点は存在しないので、与えられるグラフは円になる。

サイクルを調べるときは、DFSなどで使うような探索済リストを作って更新していくのが楽だと思います。

あとはスコアの処理をするだけです。
最初は、(周れるだけ周る+余りの回数で最大となるマス動くとき、一周しかしないとき)で更新すれば良いと思っていました。この嘘に気付かずに2時間くらい溶かしました。これだと次のようなテストケースで落ちます。

3 6
2 3 1
5 5 -9

グラフは、1→2→3→1でループします。最初の考えだと、3→2→1で答えは10になります。これは間違いで、正しい答えは11になります。
このケースの正解は、3→1→2→3→1→2となって11です。
最初の考えだと、2周+1マス or 2マスの二択になります。2周+1マスの場合は7、2マスの場合は上の通り10になります。正解は1周+2マスです。

よって、正しい更新は、(周れるだけ周る+余りの回数で最大となるマス動くとき、一周しかしないとき、周れるだけ周る-1+余りの回数で最大となるマス動くとき)になります。
あとは実装するだけです。

ansの初期値が-infなのは、0にすると答えが負になるときに0回移動が答えになるからです。

n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))

ans = -float('inf')
for i in range(n):
    score = []
    check = [0] * n
    now = i
    cycle = 0
    for _ in range(k):
        go = p[now] - 1
        if check[go] == 1:
            break
        now = go
        if len(score) == 0:
            score.append(c[now])
        else:
            score.append(score[-1] + c[now])
        check[now] = 1
        cycle += 1

    t = k // cycle
    m = k % cycle

    sum_cycle = score[-1]
    if m == 0:
        ans = max(sum_cycle * t, sum_cycle * (t - 1) + max(score), max(score), ans)
    else:
        ans = max(sum_cycle * t + max(score[:m]), sum_cycle * (t - 1) + max(score), max(score), ans)

print(ans)

さいごに

テストケースを教えてくれた、Ryukiさんありがとうございました。
楽しい問題でした。ではまた、おやすみなさい。

3 7
2 3 1
5 5 -9
— Ryuki (@e145755) August 16, 2020