AtCoder SoundHound Inc. Programming Contest 2018 -Masters Tournament-

At Coder のコンテストのログです.

C

問題文

数列 (a_1,...,a_n) の 美しさを、隣り合う 2 項の組であって、 差の絶対値が d であるものの個数として定義します。 例えば、d=1 であるとき、数列 (3,2,3,10,9) の美しさは 3 です。各要素が 1 以上 n 以下の整数である長さ m の数列は全部で nm 通り存在します。 この nm 通りの数列すべてに対して美しさを求めて、 それらの平均を出力してください。

制約
  • 0 ≤ d <n≤109
  • 2≤m≤109
  • 入力はすべて整数
解答

美しさが1上がる時は数列内に a_i,a{i+1} の差が d となる時です.それは前後の列には関係ありません。そのため、期待値の線形性から 長さ m の数列の美しさの期待値は(a_0,a_1)の美しさの期待値 + ... + (a{m-1},a_m)の期待値になります.

(a_0,a_1) について考えます. もし a_0 < d, a_0> n -d なら美しさが1となる組はただ1つ定まります. d \le a_0 \le n-d ならば,美しさが1あがるのは a_1 = a_0 + d,a_0 -d があります。これは d = 0 の時一通り,それ以外は2通りあることになります。

これから答えは以下のようになります.

n,m,d = list(map(int,input().split()))

if n > 2 * d and d > 0:
    l = n -2 * d
else:
    l = 0
# 問題文を読み違えて美しさが0 or 1になるものだと勘違いした名残
sums = [(m -1 ) * ( n +  l)]
print( sum(sums) / (n ** 2 ))

D

問題文

kenkoooo さんはすぬけ国での旅行の計画を立てています。 すぬけ国には n 個の都市があり、m 本の電車が走っています。 都市には 1 から n の番号がつけられていて、 i 番目の電車は都市 ui と vi の間を両方向に走っています。 どの都市からどの都市へも電車を乗り継ぐことで到達できます。 すぬけ国で使える通貨には、円とスヌークの 2 種類があります。 どの電車の運賃も円とスヌークのどちらの通貨でも支払え、 i 番目の電車の運賃は、 円で支払う場合 ai 円、 スヌークで払う場合 bi スヌークです。 両替所のある都市に行くと、1 円を 1 スヌークに両替することができます。 ただし、 両替をするときには持っている円すべてをスヌークに両替しなければなりません。 つまり、kenkoooo さんの所持金が X 円であるときに両替をすると、 kenkoooo さんの所持金は X スヌークになります。 現在、両替所は n 個の都市すべてに存在しますが、 i 番目の都市の両替所は今年から i 年後に閉鎖されてしまい、 i 年後とそれ以降は使うことができません。 kenkoooo さんは 10^{15} 円を持って都市 s から旅に出て、 都市 t へ向かおうと思っています。 移動中、kenkoooo さんは両替所のある都市のいずれかで円をスヌークに両替しようと考えています。 ただし、都市 s または都市 t の両替所で両替をしてもよいものとします。 kenkoooo さんは移動の経路と両替をする都市を適切に選ぶことで、できるだけ多くのスヌークを持っている状態で 都市 t に辿り着きたいと考えています。 i=0,...,n−1 のそれぞれについて、i 年後に都市 s から都市 t へ移動した際に kenkoooo さんが所持しているスヌークの最大額を求めてください。 ただし、旅行中に年をまたぐことは無いとします。

制約
  • 2≤n≤105
  • 1≤m≤105
  • 1≤s,t≤n
  • s≠t
  • 1≤ui<vi≤n1≤ai,bi≤109
  • i≠j のとき ui≠uj または vi≠vj
  • どの都市からどの都市へも電車を乗り継ぐことで到達できる入力はすべて整数
解答

問題文が長いので条件を整理すると

  • 円とスヌークの価値は同じ
  • スヌークから円への交換はできないので、交換はただ一度のみ可能
  • スヌークへの交換は必ず一度はしないといけない?(スヌークの最大値求める問題であるため、一度は必ず交換するが)
  • i 年後は{i + 1}以降でしか交換できない.
  • どの道も自由に通れる.

このことから,円について s から i まで移動するのにかかるお金の最小値と スヌークについて i から t まで移動するのにかかるお金の最小値を求め、その和が最小になる i で答えを求めれば良い. i から t までの移動にかかるお金の最小値は t から i へのお金の最小値と同じなので、これらについて動的計画法というか、この場合はダイクストラ法を使えば求まる.

ちなみに私は問題文を読み違えて、スヌークから円にも交換できるから、計算時間あふれるやんどうするんだ？？ってなりました。 実際そうなったら計算時間のかからない方法は存在しない気がします.

from collections import defaultdict
import heapq
n,m,s,t =list(map(int,input().split()))

uvab =  [list(map(int,input().split())) for _ in range(m)]
en = [[] for _ in range(n) ]
snuke = [[] for _ in range(n)]

 
for u,v,a,b in uvab:
    u=u-1
    v=v-1
    en[u].append((a,v))
    en[v].append((a,u))
    snuke[u].append((b,v))
    snuke[v].append((b,u))
 
 
def dijkstra(edges, s):
    INF = 10 ** 15
    d = [INF for x in range(n)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0,s))
 
    while len(que) > 0:
        u_d,u = heapq.heappop(que)
        if d[u] < u_d:
            continue
        for  v_d,v in edges[u]:
            if d[v] > d[u] + v_d:
                d[v] = d[u] + v_d
                heapq.heappush(que,(d[v],v))
    return d

en_ds =  dijkstra(en,s-1)
snuke_ds = dijkstra(snuke,t-1)
scores = [0] * n
for i in range(n):
  scores[i] = 10**15 - (en_ds[i] + snuke_ds[i])

ans = [ 10 ** 15 for _ in range(n)]
ans[n-1] = scores[n-1]
for i in range(n-2,-1,-1):
    ans[i] = max(ans[i+1],scores[i])
for a in ans:
    print(a)
ダイクストラ法とは

反省の意味も込めてダイクストラ法を解説します. ダイクストラ法はグラフ G=(V,E) に対し,その辺に重み k が与えられた時に、 s から t に対する最短経路を求める方法です.

基本的には 1. s から1辺で繋がる点に対する長さの最小値となる点を求める. 2. その点に対して,長さの最小値が確定する(できる) 3. 二辺で繋がる辺の最短経路の確定できる点を増やす

実装上は 1.　予め全点に距離を∞にした配列dを作成(この配列は計算段階での最小の重さの配列を表す) 2.　始点sに距離を0にする(d[s]= 0) 3.　始点sとその時点での距離0をキューにいれる 4.　キューからpopし、点uとその時の距離u_dを取得する。それと現時点でわかる最短距離d[u]を比較し、d[u]が小さければ飛ばす.(これによってすでに計算済みのものは扱わないという操作) 5.　popした点uと辺で繋がる点vに対し,その時点での最短距離d[v]と u までの最短距離＋dまでの長さd[u]+v_dを比較しそれが小さければd[v]を更新し、(v,d[v])をキューに加える 6. 4.5.をキューがなくなるまで実施する。

こうなることで最短の経路を求められ、かつ無駄な操作はあまりないというものになります。

// コードブロック