Mar 29, 2020

ABC160

2020-03-29 22:02 +0900 [Last modified : 2024-04-07 14:59 +0900]

C問題

問題概要

\(1\) 周 \(K\) メートルの円形の湖の周りに \(N\) 軒の家がある．

\(i\) 番目の家は，湖の北端から時計回りに \(A_i\) メートルの位置にある．

いずれかの地点からすべての家を訪ねるための最短距離を出力する．

制約

\(2 \leq K \leq 10^6\)
\(2 \leq N \leq 2 \times 10^5\)
\(0 \leq A_1 \lt ... \lt A_N \lt K\)

解答

隣同士の各家について間隔の最大値 \( d_{\max}\) をとれば答えは \( K-d_{\max}\) である．制約より \( A_i\) はソートされた状態で入力されるので，入力毎に各家間の距離を計算し，\( d_{\max}\) を更新すればよい．最後に \( A_1\), \( A_K\) 間の距離を例外的に計算する．

https://atcoder.jp/contests/abc160/tasks/abc160_c

https://atcoder.jp/contests/abc160/submissions/11282977

D問題

問題概要

頂点 \(N\) 個の無向グラフ \(G\) がある．\(G\) は，

\( i=1,2,...,N-1\) について頂点 \(i\) と頂点 \(i+1\) 間
頂点 \(X\) と頂点 \(Y\) 間

に辺をもつ．

頂点 \(i\), \(j\) (\( 1 \leq i \lt j \leq N\)) 間の距離を \(k\) としたとき，各 \(k(=1,2,...,N-1)\) を満たす整数組 (\(i, j\)) の個数を出力する．

制約

\( 3 \leq N \leq 2 \times 10^3\)
\( 1 \leq X,Y \leq N\)
\( X+1 \lt Y\)

解答

すべての頂点についてBFSするだけでも \(O(N^2)\) で間に合うが，気づかず場合分けゴリ押し解で通してしまった．

\( D = Y-X\) とすると，

\( i \leq X\) かつ \(Y \leq j\)
\( X \leq i \leq X + \dfrac{D+1}{2} - 1\) かつ \(Y \leq j\)
\( i \leq X\) かつ \(Y - \dfrac{D+1}{2} + 1 \leq j \leq Y\)
\( X \leq i \leq X + \dfrac{D+1}{2} - 1\) かつ \(Y - \dfrac{D+1}{2} + 1 \leq j \leq Y\)

で場合分けした．ただし，\(i=X,j=Y\) の場合の重複に気を付ける必要がある．

https://atcoder.jp/contests/abc160/tasks/abc160_d

https://atcoder.jp/contests/abc160/submissions/11313172