AtCoder Beginner Contest 160 D

2020年4月12日

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 において,2頂点間の最短距離が k (1≦k≦N-1) であるようなものの個数を出せといった問題です。G は頂点 i と i+1 の間に辺があり,これが合計 N-1 本,そして入力される値 X,Y に応じてその X と Y との間に1つの辺が作られるので,全部で合計 N 本の辺ができます。

さて,最短経路の考え方についてです。これは X と Y の間に作られる辺を通るかどうかの2パターンが考えられますよね。X と Y の間の辺を通った方が距離が短くなる場合と,逆に距離が長くなる場合が考えられるので,その2パターンの距離を出し,そのうちの距離が短い方を最短経路と考えればいいです。
以下,頂点 i と 頂点 j ( i < j ) の2点間の距離について考えることとします。

まずは X と Y の間の辺を通らない場合です。これは単純に j – i で求めることができます。

次に X と Y の間の辺を通る場合です。これは,次の3つの経路を通ると考えればいいです。

  • 頂点 i から頂点 X へ向かう(距離は | X – i | )
  • 頂点 X から頂点 Y へ向かう (距離は1)
  • 頂点 Y から頂点 j へ向かう (距離は | j – Y |)

これより,合計距離が(| X – i | + 1 + | j – Y |) になります。これと j – i との距離の小さいほうが最短距離になります。
Python では絶対値を出力しようとするときは abs 関数を用いればいいです。
ex.) abs(-2) -> 2

続いて,実装方法です。まずは距離 k の数を要素とするリスト dis を生成します。
dis[1] が距離 1 の個数,dis[2] が距離2の個数・・・といった具合です。
初期段階ではすべての距離の数を 0 としておきます。

その後,for ループで i < j なるような i と j の全てにおいて,上記の方法で最短距離を求め,その距離に対応する dis のリストの要素の数を +1 します。
最終的に dis の1~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])

いかがだったでしょうか。
もし分かりにくいところなどがあれば,気軽にコメントしてくださいね!
それでは!

他の問題も解説しているので,ぜひご覧ください。
ABC 160 A
ABC 160 B
ABC 160 C
ABC 160 D
ABC 160 E