Pythonで毎日AtCoder #27

はじめに

前回
昨日のABC161は+65でした。次に1200パフェくらいで茶色になれます。

#27

問題843diff
1TLE。
考えたこと
本番で解けなかった問題でした。グラフだと思っていたら、グラフ的な考えでなくても解けました。
$(i,j)(i,j\in Z,1\leq i < j\leq N)$な点を考えた時に、$i,j$の最短距離の個数を求める問題です。
これだけだと簡単ですが、この問題ではX-Y間に距離1で移動できる辺が用意されています。ですので、最短距離は$min(ショートカットを使わない、ショートカットを使う)$で考えます。ショートカットを使わない場合は、$j-i$になります。使う場合は$|y-j|+|x-i|+1$になります。第一項でj-Y間の距離、第二項でX-i間の距離を求めショートカットの距離1を足しています。

n, x, y = map(int,input().split())

ans = [0]*(n-1)
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(x-i)+1+abs(y-j))-1] += 1
for k in range(n-1):
    print(ans[k])

最初はansにappendして最後にcountしていたのですが、countだとO(N)になって計算量が増えてTLEしてしまいます。そこで、ans[距離]に+1していって最後に出力しています。

まとめ

グラフ感があったのに思ったよりも簡単だった。では、また。おやすみなさい