kyasbal 2021/08/10

$N$ と $K$ が互いに素であるなら、

S + nK \equiv 0 (mod N)

となる $n$ を求めればよいので、

n \equiv (N-S)K^{-1} (mod N)

kyasbal 2021/08/10

多分これ、互いに素じゃないときのほうが問題なんだろうな。

kyasbal 2021/08/10

$N$ と $K$ が互いに素でないとする。
つまり、 $N$ と $K$ が公約数 $q$ を持つとしたとき、

S + nqK^\prime \equiv 0 (mod qN^\prime)

となり、 $S$ が $q$ で割れるならば、これは $N^\prime$ の輪を $K^\prime$ を一回あたりに動く距離として回っていることと等しい。

例えば、 $q$ が2ならば、 $N$ の二席分を一つの単位として見ているような感じ。 $N$ , $K$ が互いに素ならば、いつか玉座にたどり着く。逆に $q$ があるという事は、その一緒に見た単位の中に一つだけ常に通る椅子があり、それ以外は常に通らない。 $S$ が $q$ で割れないというのは、 $q$ 通りできる巡回するパスの中で、0を通らないパスにいることと同じ。

kyasbal 2021/08/10

PyPy 7.3.0では pow(K,-1,N) は失敗する。

Python 3.8,2ではOK

地味な地雷だな

kyasbal 2021/08/10

LCSのような話?共通ではなく、逆に異なるものを選んでいくのか?

kyasbal 2021/08/10

実際にLCS風に DPを行うなら、空間計算量は $O(MN)$ 必要なはず。これは十分間に合いそう。
計算量も $O(MN)$ 程度になるはず。これも問題なさげ。

d_{i,j}:= Aのi番目、Bのj番目までで達成可能なx+yの値

として計算できない?

kyasbal 2021/08/10

ある $i$ , $j$ 番目を比較しているときに $A_i = B_j$ であるとする。このときは $x+y$ に寄与しない。

kyasbal 2021/08/10に更新

d_{i,j} := Aのi番目、Bのj番目までで達成可能なyの値

とすれば、

d_{k,k} + N-k + M - k

で最小値を探せばよいのではないか。

kyasbal 2021/08/10

長いほうから、長い分だけ消せばよいのでは?

短いほうからも消す意味はないのでは。

kyasbal 2021/08/10に更新

便宜上、 Aのほうが長いとする。

d_{i,k}:= Aのi番目まで見て、k個消したときにA_s=B_{s+k}

を満たせる最大の数

kyasbal 2021/08/10

Aのi番目を見ているときは、Bのi-k番目を見ているはず。
この時、これが等しいなら、消す必要はない、等しくないとき、消したとして状況を更新していく動的計画法ができるのでは?

d_{i+1,k}=d_{i,k}+1 (A_i = B_{i-k}のとき)

d_{i+1,k}=max(d_{i,k-1},d_{i,k}) (A_i != B_{i-k} のとき)

kyasbal 2021/08/10

いや、これはだめかも

1 3 4
2 1 3

の時、消さなければ 3、1つめと3つめを消せば、 2 + 0 = 2

となる。つまり、長いほうだけ操作すればよいという仮説が誤り。

kyasbal 2021/08/11に更新

結局のところ、LCSに近い方法になるのではないか。

今、i,j文字目を見ているときにスコアが変わるのは、

i文字目かj文字目を削除するケース
i-1,j文字目を見ているスコア + 1
i,j-1文字目を見ているスコア + 1

i文字目、j文字目を採択するケース
i-1,j-1文字目を見ているスコア + c

ただし、A[i]=B[j] なら c = 0, それいがいは1とする。

とすればよさそう。

kyasbal 2021/08/11に更新

斜めに配列をなめる必要があるかと思ったが、通常の2重forで行うことができる。

def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    D = [[10**10] * (len(B)+1) for i in range(len(A)+1)]
    D[0][0] = 0
    for i in range(N+1):
        for j in range(M+1):
            if i > 0:
                D[i][j] = min(D[i][j],D[i-1][j] + 1)
            if j > 0:
                D[i][j] = min(D[i][j],D[i][j-1] + 1)
            if i > 0 and j > 0:
                D[i][j] = min(D[i][j],D[i-1][j-1] + (0 if A[i-1] == B[j-1] else 1))
    print(D[-1][-1])
main()