yukicoderのコンテストに出た。2問出題の2問正解でなんとか全完できたので満足。

No.159 刺さらないUSB

はじめ、USBメモリが確率pで表、1-pで裏であるとする。USBを刺すとき表向きなら確率pで刺さって終わり、確率1-pで指すのに失敗する。裏ならもちろん刺さらない。失敗したらUSBメモリをひっくり返して同様のことを繰り返す。p,qを与えるので、2回ひっくり返して刺して終わる確率が1回ひっくり返して刺して終わる確率より大きくなるかどうかを答えよ。

解法

素直に問題を実装すればいい。2つの変数を抱えて2回の試行を繰り返せば確率を求められる。配列にすればN回のときにも対応可能。

p,q = map(float,raw_input().split())
a = [[0.]*2 for i in xrange(3)]
a[0][0] = p
a[0][1] = 1-p
for i in xrange(1,3):
    a[i][0] = a[i-1][1]
    a[i][1] = (1-q)*a[i-1][0]
print "YES" if a[1][0] < a[2][0] else "NO"

No.160 最短経路のうち辞書順最小

0から順番に番号を振られたN個の頂点を持つ重みつき無向グラフが与えられる。始点と終点をしていするので、始点から終点まで最短となる経路のうち、辞書順最小のものを答えよ。N ≦ 200。

解法

Nが小さいのでワーシャルフロイドで全点間距離を求めてしまう。そのとき、もとのコスト表を残しておくと、2点間が直接移動可能かどうかを判定できる。そのあとDFSで最短距離となる経路のうちで辞書順最小のものを探索していく。(今までのコスト)＋(次の点へのコスト)＋(次の点から終点までのコスト) <= (始点から終点までのコスト) となるように次に進む点を小さい順に探していけば答えが得られる。PyPyで提出しないと間に合わない。

import copy
inf = 10**9
def dfs(path,t):
    if path[-1] == G: return path
    spath = set(path)
    res = []
    for i in xrange(N):
        if i not in spath and t+cost[path[-1]][i]+mincost[i][G] <= time:
            res = dfs(path+[i],t+cost[path[-1]][i])
            if res: return res
    return []

N,M,S,G = map(int,raw_input().split())
cost = [[inf]*N for i in xrange(N)]
for i in xrange(N): cost[i][i] = 0
for loop in xrange(M):
    a,b,c = map(int,raw_input().split())
    cost[a][b] = cost[b][a] = c

mincost = copy.deepcopy(cost)
for k in xrange(N):
    for i in xrange(N):
        for j in xrange(N):
            mincost[i][j] = min(mincost[i][j], mincost[i][k]+mincost[k][j])

time = mincost[S][G]
print " ".join(map(str,dfs([S],0)))