Xmas Contest 2018
A - Art Time
問題
- 与えられた画像で4色塗り分け問題を実践せよ
解法
ペイントで適当に。隣り合うセルに別々の3色が塗られていればそのセルは残りの1色とわかるが、途中でどうしても決められないところが出るので、仮定して進み、仮定した箇所をメモっておく。破綻した時にそこまで戻る、というのを繰り返すと手動全探索が出来る。Ctrl+Zは偉大。
B - Bit Smaller
問題
- $3^4425=34425$ のように、指数を下に下ろしても数が等しくなるような数字を、20181224以下で全列挙せよ
解法
全探索。せいぜい8桁なので、指数の項は多くとも $1^23^45^{67}8$ のよう3つまで。
入力はないので、多少時間かかっても答えをTextで提出すればよい。
さすがに指数部が3桁以上になることは無いだろうと考えて、その条件で証明の無い枝刈り。
後は、切る位置によって'0'が先頭に来る場合は成立しないことに注意。
# もうちょいスッキリ書きたい
from itertools import product
def test(n, s, c, spl):
for sa, sb, tb in spl:
str_a = s[sa:sb]
str_b = s[sb:tb]
if str_a[0] == '0' or str_b[0] == '0':
return False
c *= pow(int(str_a), int(str_b), 1000000009)
if c > n:
return False
return n == c
def make_can(s, t):
ms = max(s + 1, t - 2)
return [[(s, i, t)] for i in range(ms, t)]
def make_cans():
cans = {}
for dab in range(2, 8):
if dab == 2:
can = make_can(0, 2)
elif dab == 3:
can = make_can(0, 3)
elif dab == 4:
can = make_can(0, 4)
can.extend(a + b for a, b in product(make_can(0, 2), make_can(2, 4)))
elif dab == 5:
can = make_can(0, 5)
can.extend(a + b for a, b in product(make_can(0, 2), make_can(2, 5)))
can.extend(a + b for a, b in product(make_can(0, 3), make_can(3, 5)))
elif dab == 6:
can = make_can(0, 6)
can.extend(a + b for a, b in product(make_can(0, 2), make_can(2, 6)))
can.extend(a + b for a, b in product(make_can(0, 3), make_can(3, 6)))
can.extend(a + b for a, b in product(make_can(0, 4), make_can(4, 6)))
can.extend(a + b + c for a, b, c in product(make_can(0, 2), make_can(2, 4), make_can(4, 6)))
elif dab == 7:
can = make_can(0, 7)
can.extend(a + b for a, b in product(make_can(0, 2), make_can(2, 7)))
can.extend(a + b for a, b in product(make_can(0, 3), make_can(3, 7)))
can.extend(a + b for a, b in product(make_can(0, 4), make_can(4, 7)))
can.extend(a + b for a, b in product(make_can(0, 5), make_can(5, 7)))
can.extend(a + b + c for a, b, c in product(make_can(0, 2), make_can(2, 4), make_can(4, 7)))
can.extend(a + b + c for a, b, c in product(make_can(0, 2), make_can(2, 5), make_can(5, 7)))
can.extend(a + b + c for a, b, c in product(make_can(0, 3), make_can(3, 5), make_can(5, 7)))
else:
raise NotImplementedError
cans[dab] = can
return cans
buf = []
cans = make_cans()
print(cans)
for n in range(1000000, 20181225):
s = str(n)
for digit_c in range(1, len(s) - 1):
str_c = s[-digit_c:]
if str_c[0] == '0':
continue
c = int(str_c)
if n % c != 0:
continue
dab = len(s) - digit_c
for ccc in cans[dab]:
if test(n, s, c, ccc):
buf.append(s)
print(s, ccc)
break
else:
continue
break
- $3^4 \times 425=34425$
- $31^2 \times 325=312325$
- $3^4 \times 4250=344250$
- $49^2 \times 205=492205$
- $31^2 \times 3250=3213250$
- $3^4 \times 42500=3442500$
- $3^4 \times 7^2 \times 875=3472875$
- $49^2 \times 2050=4922050$
- $1^3 \times 7^4 \times 5725=13745725$
- $1^3 \times 9^4 \times 2125=13942125$
- $1^4 \times 569^2 \times 45=14569245$
- $1^6 \times 7^4 \times 6975=16746975$
- $1^9 \times 7^4 \times 8225=19748225$
綺麗。
ほとんどは指数部が $3^4=81$ や $7^4=2401$ のように「2を素因数に多く持つ数+1」になり、整数部が5を素因数に多く持つことで、「$10^{3～4}$の倍数+元の整数」となり成立している。
H - Hello, Xmas Contest 2018
問題
- 任意の大きさの盤面のいくつかのマスに文字を書き込む
- 書き込める文字は、'A'～'Z' と '*'
- 各行の、最も左にある文字から、'*' を抜いて読むと、$S$ になる
- 各列の、最も上にある文字から、'*' を抜いて読むと、$T$ になる
- 書き込む必要のある最小マス数を求めよ
例
S = ABCF, T = EBDCA
＊ＥＢＤＣＡ
↓↓↓↓↓↓
＊→＊Ｅ Ｄ
Ａ→ Ａ
Ｂ→ Ｂ
Ｃ→ Ｃ 7マス書き込めば成立
Ｆ→ Ｆ
解法
$S$ と $T$ に共通する文字は、必ず共有する位置に置くことができる。（複数回登場する文字は、同じ個数まで）
$(H,W)=(Sの文字数, Tの文字数)$ な盤面を用意して、'A'が $S$ で1文字目、$T$ で5文字目に出てくるなら、$(1,5)$ に'A'を書き込めばよい。
また、共通しない文字や、双方に登場する文字でも片方が多くて溢れるものは、「1文字目以外は」隠せる（もう一方から読まれない位置に置ける）。1文字目の後ろに置けばよい。
どちらかの1文字目がもう一方に出現しなかった場合は'*'で隠す必要があるが、これも1つさえあれば、盤面を1マス広げて $(1,1)$ に置くことで縦横両方に隠すスペースを確保できる。
よって、$\displaystyle \sum_{c=A ... Z}{文字cの登場回数のSとTで多い方}$ をベースとし、$S_0$が$T$に含まれなかったり、$T_0$が$S$に含まれなかった場合のみ、$+1$すればよい。
from string import ascii_uppercase
from collections import Counter
s = input()
t = input()
cs = Counter(s)
ct = Counter(t)
ans = 0
for c in ascii_uppercase:
tmp = 0
if c in cs:
tmp = cs[c]
if c in ct:
tmp = max(tmp, ct[c])
ans += tmp
if s[0] not in t or t[0] not in s:
ans += 1
print(ans)
