−目次

SoundHound 2018 Qual
- A - F
- B - Acrostic
- 問題
- 例
- 解法
- C - Ordinary Beauty
  - 問題
  - 解法
- D - Saving Snuuk
  - 問題
  - 解法
- E - + Graph
  - 問題
  - 例
  - 解法
  - 探索実装
  - 探索終了

SoundHound 2018 Qual

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

A - F

略

B - Acrostic

問題

文字列 $S$ を $w$ 文字毎に改行した時、各行の先頭を縦読みしてできる文字列を求めよ

例

S = soundhound
w = 2
↓
so
un
dh
ou
nd

sudon

解法

Pythonが得意とする類いの文字列処理。s[::w] で、文字列s を w文字飛ばしで読める。

        
              s = input()
w = int(input())
print(s[::w])

C - Ordinary Beauty

問題

数列 $A=\{a_1,a_2,...,a_n\}$
隣り合う2項の差の絶対値が $d$ である箇所の個数を、数列 $A$ の“美しさ”とする
各要素が 1以上 $n$ 以下の、長さ $m$ の数列は、 $n^m$ 通り。この全ての数列の“美しさ”の平均値を求めよ

解法

和の期待値は期待値の和、という呪文のような言葉を使う。

ある1つの数列の美しさとは、隣り合う2項を1つずつ見ていって、その美しさの和となる。

d=1
A=  5    4    8    7    8
    |----|----|----|----|
       1    0    1    1   ←隣り合う2項の"美しさ"
                            数列全体の美しさはその和 1+0+1+1 = 3

求めるのはその全ての平均値=期待値なのだから『「隣り合う2項の美しさの和」の期待値』となる。

ここで和の期待値＝期待値の和を当てはめると、『「隣り合う2項の美しさの期待値」の和』が等しくなる。

なので、まず隣り合う2項の美しさの期待値を求める。

2項にだけ着目する。この1箇所だけでの美しさの期待値は?

項        k-1    k    
    ...    1     1    ...
    ...    2     2    ...
    ...    3     3    ...
    ...    4     4    ...

2項の組み合わせの数は、 $n^2$ 通り。

$d=0$ の場合は、 $n$ 通りの組み合わせが美しさ1になり、他は0。よって $\frac{n}{n^2}$

$d>0$ の場合は、 $2(n-d)$ 通りの組み合わせが美しさ1になり、他は0。よって $\frac{2(n-d)}{n^2}$

隣り合う2項は、 $m-1$ 箇所ある。各箇所で期待値は変わらないので、純粋に $m-1$ 倍すればよい。

これが『「隣り合う2項の美しさの期待値」の和』＝『「隣り合う2項の美しさの和」の期待値』＝答えとなる。

        
              n, m, d = map(int, input().split())
c = 1 if d == 0 else 2
print(c * (n - d) * (m - 1) / (n ** 2))

D - Saving Snuuk

問題

円とスヌークという2種類の通貨がある
$n$ 頂点 $m$ 辺のグラフに見立てた都市と鉄道網がある
- $i$ 番目の鉄道の運賃は、円なら $a_i$ 、スヌークなら $b_i$
$10^{15}$ 円持って、都市 $s$ から $t$ まで移動する
任意の都市で1円を1スヌークに両替できる（一方通行）
- その際、所持している全ての円をスヌークに両替し、残すことはできない
都市 $t$ に着いた時、出来るだけ多くのスヌークを残したい

$i$ 年後には、都市 $1,2,...,i$ の両替所が使えなくなる
各 $i=0,...,n-1$ について、 $i$ 年後に出発した時に残せるスヌークの最大値を求めよ

ちょっとややこしい

解法

問題文が長いためふとすると読み落とすかも知れないが、両替できるのは1回のみである。

都市 $c$ で両替すると決めれば、以下のようにしか払いようが無いので、残せるスヌークは一意に決定する。

都市 $s \rightarrow c$ まで円
都市 $c \rightarrow t$ までスヌーク

なので、以下を事前計算すればよい。Dijkstra法などを用いる。

$s$ から全都市までの円建てコスト
$t$ から全都市までのスヌーク建てコスト

これで、各都市で両替した時にかかる総運賃が求まった。

全ての両替所が使える（0年後の出発）なら、全ての都市の中から総運賃が最小で済む都市で両替すればよい。

両替する都市  1   2   3   4
総運賃       10  50  40  90

都市1で両替すれば総運賃10で済む

$i$ 年後に出発した時には、都市 $i+1,...,n$ の両替所しか使えないため、その中の最小値となる。

1年後の出発
両替する都市 ×   2   3   4
総運賃       10  50  40  90
                 ~~~~~~~~~~
都市3で両替すれば総運賃40

これを効率的に計算するには、 $i$ が大きい方から順に総運賃のminを取っていけばよい。 $10^{15}$ から引いた値が答えとなる。

3年後の出発
両替する都市 ×  ×  ×   4
総運賃       10  50  40  90
                         ~~  → 90
2年後の出発                     └─┐
両替する都市 ×  ×   3   4         ↓
総運賃       10  50  40  90
                     ~~~~~~  → min(90, 40) = 40
1年後の出発                                   │
両替する都市 ×   2   3   4         ┌────┘
総運賃       10  50  40  90         ↓
                 ~~~~~~~~~~  → min(40, 50) = 40
0年後の出発                                   │
両替する都市  1   2   3   4         ┌────┘
総運賃       10  50  40  90         ↓
             ~~~~~~~~~~~~~~  → min(40, 10) = 10

        
          
          
              
              import sys
from heapq import heappop, heappush
 
 
def dijkstra(s, i):
    costs = [-1] * n
    q = [(0, s)]
    while q:
        c, v = heappop(q)
        if costs[v] >= 0:
            continue
        costs[v] = c
        for u, *fee in links[v]:
            if costs[u] == -1:
                heappush(q, (c + fee[i], u))
    return costs
 
 
n, m, s, t = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    u, v, a, b = map(int, line.split())
    links[u - 1].add((v - 1, a, b))
    links[v - 1].add((u - 1, a, b))
yen_costs = dijkstra(s - 1, 0)
snk_costs = dijkstra(t - 1, 1)
total_costs = list(map(sum, zip(yen_costs, snk_costs)))
tmp = float('inf')
ans = []
ini = int(1e15)
for c in reversed(total_costs):
    tmp = min(tmp, c)
    ans.append(ini - tmp)
ans.reverse()
print('\n'.join(map(str, ans)))

            

        
      

E - + Graph

問題

$n$ 頂点 $m$ 辺の単純連結グラフ
- ※単純連結グラフ＝自己辺や多重辺を持たない、かつどの頂点からどの頂点へも繋がっている
各辺には整数値 $s_i$ が決められている
それぞれの頂点に正の整数を書き込む
- 書き込む値は、頂点 $u_i$ と $v_i$ を結ぶ辺に $s_i$ が決められている場合、 $u_i+v_i=s_i$ となるようにする
条件を満たすような正の整数の書き方は何通りか

例

si     6      7      5
   ① --- ② --- ③ --- ④
    1      5      2      3  ←頂点に書き込める数字の各パターン
    2      4      3      2  ←
    3      3      4      1  ←

3通り

解法

任意の1頂点を決めれば、連鎖的に全ての頂点の値が決まる。（もしくは矛盾する）

最初の頂点はどれでも良いので、①の値を決めるとする。

①から「偶数本の辺を通ってたどり着ける頂点」と「奇数本の辺を通ってたどり着ける頂点」に分けることを試みる。

もし完全に綺麗に分けられた場合（グラフが2部グラフだった場合）

成り立っている状態から、①及び①と同じグループの値を1増やし、異なるグループの値は1減らしたパターンもまた、成り立つことがわかる。

もし同じグループを結ぶ辺が1つでもある場合（2部グラフで無かった場合）

もし今、成り立っていたとしても（④+⑤= $s_E$ ）、①の値を1増やすと④も⑤も1減り、④+⑤の値は必ず変わってしまう。

よって、グラフが2部グラフで無い場合、成り立つのは1通りか0通りである。

探索実装

探索はBFSでもDFSでもよいが、2部グラフの判定と同じくどちらのグループに属するか（＝①から偶数本の辺を辿ったか、奇数本か）の情報を与えながら辺を辿っていく。

①に値1を仮定し、全ての頂点の値を決定していく。1は正整数の最低値である。

探索の過程で、既に値が決まっている頂点に別のルートでたどり着けてしまった場合、やや細かいが、以下の条件分岐に従う。

①から辿る辺数の偶奇が同じ場合

入るべき値が同じ場合

問題なく続行可能

入るべき値が異なる場合

この矛盾を解消することは出来ないので、答えは0

①から辿る辺数の偶奇が異なる場合

入るべき値が同じ場合

問題なく続行可能、ただし2部グラフで無いことが判明したフラグを立てる

入るべき値が異なる場合

①の初期値を変化させて調整することが可能か試みる。

「偶数本たどるルートで入るべき値」を $p_i$ 、「奇数本辿るルートで入るべき値」を $q_i$ とする。

既に他に、①から辿る辺数の偶奇が異なる2ルートを持つ頂点があり、その頂点の値に矛盾が無い場合
- ⇒ 先方の無矛盾を保ったまま当方の調整をすることはできないので、答えは0
$p_i>q_i$ の場合
- ⇒ ①の値を減らすことで両者を近づけられるが、①にはそもそも1（もしくは現時点でとりえる最低値）を仮定しているため、これ以上減らせない。答えは0
$q_i-p_i$ が奇数の場合
- ①の値を1変化させると、 $q_i-p_i$ は2変化するため、奇数の場合は差を0に出来ない。答えは0
$q_i-p_i=2d$ の場合
- ①の初期値を $d$ だけ増加させて再探索すると、この頂点に関しては矛盾が解消される

探索終了

最後まで矛盾無く値が決定できたとする。

2部グラフだった場合

③のように0以下の値が①グループの方にあると、①の初期値をその分増やさないといけない。（この場合は+3）その分反対のグループは減る。

ここから①の初期値を1ずつ増やしていったパターンは全て成立するのだが、どこまで増やせるかというと、反対側のグループの最小値が1になるまでである。

よってこの場合、④や⑥が3で最小のため、3,2,1の3パターン作れるということになる。

2部グラフで無かった場合

もう①の初期値はここから動かせない。

もしどこかの頂点に0以下の値がある場合、答えは0となる。

そうでなく、全頂点が正値で成立したパターンが構築できた場合、答えはその1個となる。

        
          
          
              
              # ※上記の説明とは少し異なり、探索中に頂点に0以下の値が入らないかのチェックも行う実装となっている
#   再探索回数が増えるため、速度としては上記のアルゴリズムの方が良いと思う
import sys
 
 
def check(k, flag=False):
    fixed = [-1] * n
    q = [(0, k, False, None)]
    has_non_bipartite_loop = False
    while q:
        v, m, is_odd, a = q.pop()
        # print(v, m, is_odd, q, fixed)
        if fixed[v] != -1:
            p, was_odd = fixed[v]
            if is_odd == was_odd:
                if m != p:
                    return 0
                continue
            else:
                if m == p:
                    has_non_bipartite_loop = True
                    continue
                if flag:
                    return 0
                d = m - p if is_odd else p - m
                if d < 0:
                    return 0
                if d % 2:
                    return 0
                return check(k + d // 2, True)
        else:
            fixed[v] = (m, is_odd)
 
        for u, s in links[v]:
            if s - m < 1:
                if not is_odd:
                    return 0
                return check(k + m - s + 1, False)
            if u == a:
                continue
            q.append((u, s - m, not is_odd, v))
 
    if has_non_bipartite_loop:
        return 1
 
    min_is_odd = float('inf')
    for m, is_odd in fixed:
        if is_odd:
            min_is_odd = min(min_is_odd, m)
    return min_is_odd
 
 
n, m = map(int, input().split())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    u, v, s = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, s))
    links[v].add((u, s))
print(check(1))

            

        
      