Codeforces Round #332 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Patrick and Shopping

ざっくりと大意

・家から店1と店2の両方へ行って帰ってくる最短距離はいくつか。
・家から店1が\(d_1\)、家から店2が\(d_2\)、店1と店2が\(d_3\)

方針のようなもの

・全部調べよう。

l=map(int,raw_input().split())
print min(sum(l),(l[0]+l[1])*2,(l[1]+l[2])*2,(l[0]+l[2])*2)

全部が考えたらずに無駄にWAした。サンプル1,2の移動経路以外に家から店1、店1から店2、店2から店1、店1から家。家から店2、店2から店1、店1から店2、店2から家。という既に到達した店をもう一度通って家にかえるパターンがある。考えれば分かったはずなのに・・

B. Spongebob and Joke

ざっくりと大意

・長さnの数列fと長さmのbをヒントにして数列aを再現する。
・\(b_i\) = f[\(a_i\)] に対応するらしい。
・サンプル1は\(b_1\)が1でfの中で1は3番目の数なので\(a_1\)は3、\(b_2\)が2でfの中で2は2番目なので\(a_2\)は2、\(b_3\)が3でfの中では3は1番目の数なので\(a_3\)は１。
・サンプル2は\(b_1\)が1でfの中で1,2,3番目、、、以降も同様に、、ヒントではaが定まらないので'Ambiguity'
・サンプル3は\(b_1\)が3でfの中で情報を持っていないので'Impossible' らしい？？？

方針のようなもの

・数列作成をシミュするしか無い気がする。

python

#WA
n,m=map(int,raw_input().split())
f=map(int,raw_input().split())
fd={}
for x,i in enumerate(f):
    if fd.has_key(i):
        fd[i].append(x+1)
    else:
        fd[i]=[x+1]
b=map(int,raw_input().split())

a=[0]*m
p=0
for x,i in enumerate(b):
    if p==0 and fd.has_key(i) and len(fd[i])==1:
        a[x]=fd[i][0]
        del fd[i]
    elif p==0 and fd.has_key(i) and len(fd[i])>1:
        p=1
        fd[i].pop()
    elif p==1 and fd.has_key(i):
        fd[i].pop()
        if len(fd[i])==0:
            del fd[i]
    else:
        print 'Impossible'
        exit()
if p==1 or a.count(0)>0:
    print 'Ambiguity'
else:
    print 'Possible'
    print ' '.join(map(str,a))

WA解決出来ずシミュして1つに定まればそれを出力する。fの中に複数候補があったら曖昧フラグを立てつつ候補を1減らして、'Ambiguity'予定でシミュを続ける。完走したら'Ambiguity'、途中で見つからないものがあったら'Impossible'な方針で試したが上手くいかず。。。あとで