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

    *EBDCA
    ↓↓↓↓↓↓
*→*E  D
A→          A
B→    B
C→        C   7マス書き込めば成立
F→          F

解法

$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)

programming_algorithm/contest_history/atcoder/2018/1224_xmascon18.txt · 最終更新: 2018/12/26 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0