ねむくてつらかった
A-small、A-largeとB-smallとC-smallを解けて824位、1000位以内なので一応Round2まではいけるっぽい
Problem A. The Repeater
文字列が\(N\)個与えられる
ある文字の次に同じ文字を付け足すか、連続してる同じ文字を1文字削除するかの2つの操作が行える。
全部の文字を同じにするのに最小の操作回数を答える。
ただし同じにできない場合には'Fegla Won'と出力
解法
それぞれの文字列で文字がちゃんと対応しているか確かめる。
対応している部分について文字の長さをソートしてから、それぞれの文字列に合わせるときの操作回数を計算する(現在注目している文字の長さよりも短いものの個数と長いものの個数がわかれば差分が簡単に求められる)
計算量は、テストケース数を\(T\)、文字列の数を\(N\)、文字列の長さを\(L\)としたとき、\(O(TLN\log N)\)
以下ちょっと汚いコード
import sys import collections T = int(raw_input()) for t in xrange(1, T + 1): N = input() text = [raw_input().strip() for i in xrange(N)] cur = [0] * N L = map(len, text) result = 0 fail = False while cur[0] < L[0]: char = text[0][cur[0]] temp = cur[:] for i in xrange(N): while cur[i] < L[i] and text[i][cur[i]] == char: cur[i] += 1 diff = [cur[i] - temp[i] for i in xrange(N)] diff.sort() s = sum(diff) s2 = sum(diff) ii = 0 for i in xrange(N): s2 -= (diff[i] - ii) * (N - 1 - i + 1) s2 += (diff[i] - ii) * (i) s = min(s, s2) ii = diff[i] result += s for i in xrange(N): if cur[i] - temp[i] == 0: print "Case #{0}: {1}".format(t, 'Fegla Won') fail = True break if fail: break if fail: continue for i in xrange(N): if cur[i] < len(text[i]): print "Case #{0}: {1}".format(t, 'Fegla Won') break else: print "Case #{0}: {1}".format(t, result)
Problem B. New Lottery Game
\(A\)未満の数と\(B\)未満の数の論理積(AND)を取った時に\(K\)未満になる組み合わせの数を答える。
smallは単純に実装すれば良い
計算量は\(O(AB)\)
import sys import collections T = int(raw_input()) for t in xrange(1, T + 1): result = 0 A, B, K = map(int, raw_input().split()) for i in xrange(A): for j in xrange(B): if i & j < K: result += 1 print "Case #{0}: {1}".format(t, result)
Problem C. The Bored Traveling Salesman
各ノードに文字列がついたグラフが与えられる。
深さ優先探索(?)で行き掛け順に文字列を足していく時の最小の文字列を答える。
smallは単純に全通り試せばよい
import sys import collections import random import itertools T = int(raw_input()) for t in xrange(1, T + 1): N, M = map(int, raw_input().split()) code = [] for i in xrange(N): code.append(input()) neighbor = collections.defaultdict(list) for i in xrange(M): x, y = map(int, raw_input().split()) neighbor[x - 1].append(y - 1) neighbor[y - 1].append(x - 1) result = '99999999'*10 if N == 1 and M == 0: print "Case #{0}: {1}".format(t, code[0]) continue for p in itertools.permutations(xrange(N)): cur = [p[0]] temp = str(code[cur[-1]]) success = False for n in p[1:]: while cur: if n not in neighbor[cur[-1]]: cur.pop() continue else: cur.append(n) temp += str(code[cur[-1]]) if n == p[-1]: success = True break else: if success: result = min(temp, result) print "Case #{0}: {1}".format(t, result)
largeは一旦戻ったほうが文字列が小さくなる時に、戻ったら到達不能なノードができないかを判定しながら回ればいいっぽい(ここまでは実装できず