Atcoder Beginner Contest 021 A,B,C

Cでバグ取りに時間がかかりDはわからず・・・

問題はこちら。

A: 足し算

Nが与えられるので 1, 2, 4, 8 を任意の個数用いてそれらの和がNになるようにせよ。その時用いた数の個数と値を出力せよ。

解法

1が使えるのでN個の1を出力すればいい。

N = input()
print N
for i in xrange(N):
    print 1

B: 嘘つきの高橋くん

高橋くんは街aから街bまで最短経路で移動したと主張している。あなたは街の間の道路の有無やいくつ町があるかなど全く知らないが、高橋くんは移動の際中M個の町を通ったといっている。これらの情報から高橋くんが本当に最短経路で移動してきた可能性があるかどうかを答えよ。

解法

aとbとM個の町の間で重複があるかどうかを確認すればいい。重複があるなら同じ町を2度通ったことになり、それは決して最短経路にはなり得ない。

N = int(raw_input())
a, b = map(int, raw_input().split())
K = int(raw_input())
P = map(int, raw_input().split())+[a,b]
print "YES" if len(P) == len(set(P)) else "NO"

C:

N個の町とそれらの町間を結ぶM本の道路がある。道路は双方向に移動可能である。町aから町bへの最短経路での移動仕方は何通りあるか。答えが大きくなる可能性があるので10⁹+7で余りを取った値を答えよ。

解法

道路の長さがすべて同じなのでBFSで解ける。 町aからある町への最短経路での移動の仕方は、その町と道路でつながっていてなおかつ町aからの最短距離がこの町へのものより1小さい町への、町aからの最短経路での移動の仕方の和となる。この計算を町aからの最短距離が小さい町から順に計算していく。町aからの距離表を抱えておけば重複計算を防ぐことができる。

inf = 10**9
mod = 10**9+7
N = int(raw_input())
a, b = map(int, raw_input().split())
a, b = a-1, b-1
G = [[0]*N for i in xrange(N)]
M = int(raw_input())
for loop in xrange(M):
    x, y = map(int, raw_input().split())
    x, y = x-1, y-1
    G[x][y] = G[y][x] = 1
    
combs = [0]*N
combs[a] = 1
steps = [inf]*N
steps[a] = 0
que = [a]
while que:
    cur = que.pop(0)
    for nxt in xrange(N):
        if G[cur][nxt] and steps[nxt] > steps[cur]:
            combs[nxt] = (combs[nxt]+combs[cur])%mod
            steps[nxt] = steps[cur]+1
            if nxt not in que: que.append(nxt)
 
print combs[b]%mod