Xmas Contest 2018

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'が先頭に来る場合は成立しないことに注意。

• $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$すればよい。