AtCoder Beginner Contest 160 D を Python で
AtCoder Beginner Contest 160 D を Python で解説していこうと思います。自分が初めてコンテスト開催中に解けた D 問題で，なかなか感慨深い問題です。（笑）
それではさっそく，まずは問題文から。
https://atcoder.jp/contests/abc160/tasks/abc160_d
D – Line++
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
1 から N までの番号がつけられた N 個の頂点を持つ無向グラフ G があります。 G には、以下のように合計 N 本の辺があります。
- i=1,2,…,N−1 について、頂点 i と頂点 i+1 の間に辺があります
- 頂点 X と頂点 Y の間に辺があります
k=1,2,…,N−1 について、以下の問題を解いてください。
- 整数の組 (i,j)(1≤i<j≤N) であって、 G において頂点 i と頂点 j の最短距離が k であるようなものの数を求めてください
制約
- 3≤N≤2×10^3
- 1≤X,Y≤N
- X+1<Y
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X Y
出力
k=1,2,…,N−1 に対する問題の答えを、順番に一行に出力せよ。
解説
無向グラフ G において，２頂点間の最短距離が k (1≦k≦N-1) であるようなものの個数を出せといった問題です。G は頂点 i と i+1 の間に辺があり，これが合計 N-1 本，そして入力される値 X，Y に応じてその X と Y との間に１つの辺が作られるので，全部で合計 N 本の辺ができます。
さて，最短経路の考え方についてです。これは X と Y の間に作られる辺を通るかどうかの２パターンが考えられますよね。X と Y の間の辺を通った方が距離が短くなる場合と，逆に距離が長くなる場合が考えられるので，その２パターンの距離を出し，そのうちの距離が短い方を最短経路と考えればいいです。
以下，頂点 i と 頂点 j （ i < j ) の２点間の距離について考えることとします。
まずは X と Y の間の辺を通らない場合です。これは単純に j – i で求めることができます。
次に X と Y の間の辺を通る場合です。これは，次の３つの経路を通ると考えればいいです。
- 頂点 i から頂点 X へ向かう（距離は | X – i | ）
- 頂点 X から頂点 Y へ向かう （距離は１）
- 頂点 Y から頂点 j へ向かう （距離は | j – Y |）
これより，合計距離が（| X – i | + 1 + | j – Y |) になります。これと j – i との距離の小さいほうが最短距離になります。
Python では絶対値を出力しようとするときは abs 関数を用いればいいです。
ex.) abs(-2) -> 2
続いて，実装方法です。まずは距離 k の数を要素とするリスト dis を生成します。
dis[1] が距離 1 の個数，dis[2] が距離２の個数・・・といった具合です。
初期段階ではすべての距離の数を 0 としておきます。
その後，for ループで i < j なるような i と j の全てにおいて，上記の方法で最短距離を求め，その距離に対応する dis のリストの要素の数を +1 します。
最終的に dis の１～Nの要素を出力すればよいです。
これで計算量はO(n^2)で解くことができました。
では，以下に解答例を載せます。
解答例
n,x,y = map(int, input().split())
dis = [0]*n
for i in range(n):
for j in range(i+1, n):
kyori = min(j-i, abs(x - (i+1)) + 1 + abs(y - (j+1)))
dis[kyori] += 1
for k in range(1, n):
print(dis[k])
いかがだったでしょうか。
もし分かりにくいところなどがあれば，気軽にコメントしてくださいね！
それでは！
