感想

最近、貪欲法がが多いと感じます。苦手なのでそろそろ慣れていきたいです。
そろそろレートの上昇が見られると嬉しいですね…。

20日目

ABC141-E Who Says a Pun?

かかった時間

50分
$O(N^3)$をごり押せば通ると思いましが、流石に無理で20分追加で溶かしました。

考察

二回以上現れる文字列を考えるにはある文字列が最低二回現れれば良いので、その二つの文字列を$s_1$,$s_2$と以下では置きます。

まず、部分文字列なのでDPを疑います。しかし、文字列が重ならないかつ同じ文字列内で考えるという二つを同時に処理しようとして迷走し、$i$文字目以前と$i+1$文字目以降で分けて…などと考えましたが、これは悪手でした。

考察をする中で連続であることに注目し尺取法に近い愚直な方法で解けるのではないかと思いました。つまり、$s_1$の最初の文字を$i$文字目($N$通り)、$s_2$の最初の文字を$j(i+1 \leqq j \leqq N)$文字目($N-i$通り)とした時に、$s_1$と$s_2$が一致する中で最長の文字列を考え(最長で$N$通り)ます。この場合、$O(N^3)$となるので間に合いません。(ここまでの考察に30分近くかかったのが全然だめですね。)

そこで、この方法を効率よく計算するために無駄に調べているところがないか考えます。すると、連続な部分が一致するかを判定する部分で繰り返し同じ部分を計算していることがわかります。したがって、後ろの部分を先に計算しておけば効率化できるので、以下のような配列を用意してDPを行えば良いです。

$dp[i][j]:=$($s_1$が$i$文字目から始まり$s_2$が$j$文字目から始まる時の最長共通接頭辞,ただし、$i=0$の時及び$j=0$の時も含み、$s_1$と$s_2$は重ならない)

ここで、後ろの部分から計算するとした時のDPの遷移の場合分けは以下のようになり、これを実装してdpの中の最大値が答えとなります。

(1) ($s$の$i$文字目)$=$($s$の$j$文字目)の時
　　$dp[i][j]=dp[i+1][j+1]+1$

(2)($s$の$i$文字目)$\neq$($s$の$j$文字目)の時
　　$dp[i][j]=0$

(✳︎)$dp[i][j]$は高々$j-i$にしかならない
　　また、それを超える場合は$dp[i][j]=0$として良い

(1),(2),(✳︎)はそれぞれ示すことができますが、ここでは省略します。

追記

・最長共通接頭辞とは
文字列s,tの共通する接頭辞のうち最長のもののことです。
s=ABCBC,t=ABDの時の最長共通接頭辞はABで、s=ABC,t=BCDの時の最長共通接頭辞は空文字列となります。

・今回得た知見
$O(N^3)$→$O(N^2)$くらいで$N$を削るパターンの問題は繰り返し無駄に計算しているところがないかに注目すればDPなり前計算なりで計算量を落とせるので、肝に命じようと思いました。
また、様々な文字列のアルゴリズムを使うとこの問題はいろいろな解き方ができるようです。

Pythonのコード

abc141.py

n=int(input())
s=input()
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
            dp[i][j]=dp[i+1][j+1]+1
ans=0
for i in range(n):
    for j in range(n):
        ans=max(ans,dp[i][j])
print(ans)

ABC091-C 2D Plane 2N Points

かかった時間

30分くらい考えて諦めました。

間違えた原因

明らかに証明できない貪欲法で解こうとしていた。
典型的な解法を試せていなかった。
(そこまで難しくもないはずなんですが…)

考察

まず、青の点と赤の点の二つの集合があるので、ここでは青の点を固定した時の最適な赤の点を考えます($\because$赤の点を固定した時の最適な青の点を選ぶのでも本質的には変わりません。)。

ここで、青の点でx座標の小さい点は少ない赤の点しか選べないことを考えると、先にそのような点を選んだ方が良いです($\because$ x座標と同時にy座標を考えると難しいので片方のみまずは考えます。)。したがって、青の点はxの座標が小さいものから順に選んで、それぞれで最適な赤の点を選ぶことにします($\because$貪欲法では選ぶ順番が大事！！)。

上記のもとで最適となるのは選べる赤の点の中で(x座標によらず)y座標が最大の点となります。なぜなら、x座標の小さい青の点から順に選ぶので今選ぶことのできる赤の点のx座標はこれ以降に選ぶ青の点よりも常に小さく、y座標をできるだけ小さくすれば良いからです。

以上の考察より、赤の点はy座標の降順で青の点はx座標の昇順で保存しておくことでforループを二回だけ回せば実装することができ、$O(N^2)$の解法となります($O(N \log{N})$には落とせますが、実装が少し面倒です。)。

(二部グラフの最大マッチングという問題に帰着することができるらしいので、いつかその方法で取り組めたらと思います。)

Pythonのコード

abc91c.py

n=int(input())
red=sorted([list(map(int,input().split())) for i in range(n)],key=lambda x:x[1],reverse=True)
blue=sorted([list(map(int,input().split())) for i in range(n)])
ans=0
for bx,by in blue:
    for rx,ry in red:
        if rx<bx and ry<by:
            ans+=1
            red.remove([rx,ry])
            break
print(ans)

21日目

エイシングプログラミングコンテスト2020-E Camel Trainを解きました。
こちらの記事にて解説しています・

22日目

ABC144-E Gluttony

かかった時間

27分

考察

まず、積の最大値が最小となるような組み合わせは、消化コストを昇順で並べて食べにくさを降順で並べたものを対応するように組み合わせたものになります。これは、最適な組み合わせを組み替えた時に得をすることがない(または、最適でない組み合わせを組み替えた時に得をする)ことを示せれば良いです(詳しくはARMERIAさんの記事を参照してください)。簡単な解説を示すと以下のようになります。

(以下では、この組み合わせで前から$i$番目の消化コストを$a[i]$、前から$i$番目の食べにくさを$f[i]$で表します。)

初めの状態でこの組み合わせを作り、そこからpriority_queueを使って$K$回のシミュレーションを行おうとしまいましたが、$K$が最大で$10^{18}$と大きいので間に合いません。

ここで、$K$を一つずつではなくまとめて減らしたいとして考察していった時に、とりあえずそれぞれの積がある値$x$以下にできると仮定してみました。すると、$(f[i],a[i])$の組み合わせは$a[i] \rightarrow [\frac{x}{f[i]}]$とすれば最小の修行の回数でその積を$x$以下にすることができます($a[i] \leqq [\frac{x}{f[i]}]$の時はすでにその積は$x$以下なので修行回数は0回)。したがって、全員の最低の修行回数の和を$O(N)$で求めた時に$K$回以下であれば良いとわかります。

ここで、その$x$のうちの最小値($x^{'}$)を求めればよく、$x^{'}$より小さい$x$では題意を満たさず$x^{'}$以上の$x$の時は満たさないという単調性も容易に示せるので、二分探索でこの$x^{'}$を調べることができます。(制約から$x$は最大で$a_{max} \times f_{max}$と大きくなることからも発想できると思います。)

以上より、全体の計算量は$O(N \log(a_{max} \times f_{max}))$となります。また、普通に実装したらPythonでは通らなかったのでPyPyで通しました。

Pythonのコード

abc144e.py

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
#こっちは変えられない
f=sorted(list(map(int,input().split())),reverse=True)
l,r=0,10**12
def cal(x):
    global n,f,a,k
    ret=0
    for i in range(n):
        ret+=max(0,a[i]-(x//f[i]))
    return ret
while l+1<r:
    x=l+(r-l)//2
    if cal(x)<=k:
        r=x
    else:
        l=x
if cal(l)<=k:
    print(l)
else:
    print(r)

ABC150-D Semi Common Multiple

かかった時間

30分

考察

問題の通りに言い換えていけば難しくない問題ですが、数学が苦手だと難しく感じるでしょうか。
ちなみに、僕は自分の考察と実装が一部異なったという下らない理由で2WAを出しました。反省しています。

まず、$X=a_k \times (p+0.5)$の$0.5$が扱いにくいので、数列$A$の任意の要素を2で割った数列$B$を考えて$X=b_k \times (2p+1)$と言い換えます。また、この式は、「$X$は任意の$k$で$b_k$の倍数(1)」かつ「任意の$k$で$X$を$b_k$で割った商が奇数(2)」と言い換えることができます。(これらの言い換えは全て同値です。)

ここで、(1)より$X$は数列$B$の任意の要素の公倍数なので、最小公倍数を$C$としてその倍数です。また、$C$はmathライブラリのgcdを利用して$O(N \log{a_max})$で簡単に求められます。このもとで、$C$の倍数の中で(2)を満たすものを探します。まず、$C$が奇数の場合は$C$に奇数をかけたものがその答えとなるのは容易にわかります。しかし、$C$が偶数の場合は数列$B$の任意の要素で2で割りきれる回数が同じ(✳︎)にならねばなりません。なぜなら、2で割りきれる回数が異なる数列$B$の要素が存在する時は、2で割れる回数が少ない$b_k$で$X$を割ったものは偶数になるからです。また、(✳︎)は$C$が奇数の場合も常に成り立ちます。

したがって、実装しやすいように上記を言い換えれば、「$C$が割り切れる中で最大の$2^i$($i$は非負の整数)を$D$とした時、$D$で割り切れない数列$B$の要素が存在する場合は題意を満たす$X$が存在せず0通り、それ以外の場合は$C$に奇数をかけたもののうち1以上$M$以下の数が$X$の候補でありこれは$ceil(\frac{X}{2})$」となります。

Pythonのコード

abc150d.py

from math import gcd
def lcm(a,b):
    return a//gcd(a,b)*b
def lcm(ab):
    l=len(ab)
    ret=ab[0]
    for i in range(1,l):
        ret=ret//gcd(ab[i],ret)*ab[i]
    return ret
def count2(a):
    ret=0
    while a%2==0:
        a//=2
        ret+=1
    return 2**ret
n,m=map(int,input().split())
A=list(map(int,input().split()))
#これはいらないです
if any(i%2 for i in A):
    exit(print(0))
A=[i//2 for i in A]
#全体の最小公倍数
p=lcm(A)
c=count2(p)
#2で割り切れる回数が同じでないものがある場合
if any(i%c for i in A):
    exit(print(0))
x=m//p
#print(p//c)
print(-(-x//2))