AtCoder Regular Contest #011 ○○×-

• Welcome to AtCoder Regular Contest #011 - AtCoder Regular Contest #011 | AtCoder

AとBだけ解けてCはTLE。

A問題

最初の数からm引いてn足すのを繰り返して、足したnの数の合計+初期値を求める。
やるだけ。

# -*- coding: utf-8 -*-
import sys
import collections
m, n, N = map(int, raw_input().split())

consumed = N

sold = N
while consumed >= m:
    consumed -= m
    consumed += n
    sold += n

print sold

B問題

単語中のある特定の文字を数字に置換して、それ以外を無視した場合の数字列を出力。
やるだけ。

# -*- coding: utf-8 -*-
import math
import sys
import datetime

N = int(raw_input())
word = raw_input().split()

ret = []
check = [['z', 'r'], ['b', 'c'], ['d', 'w'], ['t', 'j'], ['f', 'q'], ['l', 'v'], ['s', 'x'], ['p', 'm'], ['h', 'k'], ['n', 'g']]
new_check = []
for q in check:
    temp = []
    for e in q:
        temp.append(e)
        temp.append(e.upper())
    new_check.append(temp)
check = new_check
for w in word:
    result = []
    for c in w:
        for i, q in enumerate(check):
            for e in q:
                if c == e:
#                    print c, e, i
                    result.append(str(i))
    if len(result) > 0:
        ret.append(''.join(result))

print ' '.join(ret)

C問題

単語リストと最初と最後の単語が与えられる。
1文字違う単語をつないでいって、最初から最後まで最短でいくつの単語でいけるかを求める。

終わってから思いついたC問題の解法。
単語をノードとみなして1文字違う単語との間に辺を張れば後はダイクストラ法とかA*とかを使うだけっぽい。

……と思ってPythonでコードを書いたら何故か終わらなかった(´・ω・｀)

# -*- coding: utf-8 -*-
import math
import sys
import collections
 
first, last = raw_input().strip().split()
N = int(raw_input())
word = []
for i in xrange(N):
    word.append(raw_input().strip())
 
if first == last:
    print 0
    print first
    print last
    
    sys.exit(0)
 
L = len(first)
 
diff = collections.defaultdict(set)
 
P = {}
for i in word + [first, last]:
    P[i] = sum([i[c] != last[c] for c in xrange(L)])
 
for i in word + [first, last]:
    for j in word + [first, last]:
        if sum([i[c] != j[c] for c in xrange(L)]) == 1:
            diff[i].add(j)
            diff[j].add(i)
 
 
distance = collections.defaultdict(lambda: 10000)
 
cur = [first]
distance[first] = -1
 
while len(cur) > 0:
    new_cur = []
    c = cur.pop()
    for next in diff[c]:
        if distance[next] > distance[c] + 1:
            distance[next] = distance[c] + 1
            new_cur.append(next)
    cur += new_cur
    cur.sort(key = lambda x: - P[x] - distance[x], reverse=True)
 
if distance[last] != 10000:
    print distance[last]
    
    cur = last
    route =[cur]
    while True:
        if cur == first:
            break
        for next in diff[cur]:
            if distance[next] == distance[cur] - 1:
                cur = next
                route.append(cur)
                break
    route.reverse()
    print '\n'.join(route)
else:
    print -1