ABC160 D - Line++

問題原文

atcoder.jp

問題要旨

頂点の直線状のグラフがあり、 辺 は頂点 と 頂点 をつないでいる。
またバイパスが張られていて、 頂点 と頂点 をつないでいる。
について 最短距離が となるような の通り数を求めよ。

• 

解法

各 の組み合わせを全探索することを考える。
各最短距離は min（真っ直ぐ進む場合, バイパスを経由する場合）になる。

実装

N, X, Y = map(int, input().split())
ans = [0] * N

for fr in range(1, N + 1):
    for to in range(fr + 1, N + 1):
        cost = min(to - fr, abs(X - fr) + abs(to - Y) + 1)
        ans[cost] += 1

print(*ans[1:], sep="\n")

感想

特殊な条件を使う or 使わない とすると見通しがよくなるパターンと名付けることにします。
下手に小さな部分に着目するとハマりそう。