AtCoder Beginner Contest 110

解説放送: AtCoder Beginner Contest 110 解説放送 - YouTube

速解きしようとすると凡ミス連発する

A - Maximize the Formula

問題

1～9の整数 $A,B,C$ と'+'を並べ替えて、 $AB+C$ とか $BC+A$ みたいな形の数式を作る
数式の答えを最大化せよ

解法

$AB+C$ をよく見ると、 $10A+B+C$ と一緒。10倍するのは1つのみで、それはなるべく大きい方がよい。よって $A,B,C$ の中で最大を10倍して、後の2数は普通に足せばよい。

        
              a, b, c = sorted(map(int, input().split()))
print(a + b + 10 * c)

B - 1 Dimensional World's Tale

問題

1次元の世界に、A帝国とB帝国がある
A帝国の首都は座標 $X$ 、B帝国の首都は座標 $Y$
A帝国は新たに座標 $x_1,x_2,...,x_N$ の都市を支配下に置きたい
B帝国は新たに座標 $y_1,y_2,...,y_N$ の都市を支配下に置きたい
首都や、支配下に置きたい都市が交錯していると戦争になる
戦争になるか判定せよ

解法

首都も含めて、A帝国の最も右側（最大）の都市<B帝国の最も左側（最小）の都市となっていればよい。

ところで1次元世界って、生まれ着いた時に自分より右にいた人の右側に行くことは一生できないよね。

        
              n, m, x, y = map(int, input().split())
xxx = list(map(int, input().split()))
yyy = list(map(int, input().split()))
xxx.append(x)
yyy.append(y)
mx = max(xxx)
my = min(yyy)
print('No War' if mx < my else 'War')

C - String Transformation

問題

英小文字の同じ長さの文字列 $S,T$
文字列 $S$ に対して、以下の操作を何度でも行える
- 異なる英小文字 $c_1,c_2$ を選び、 $S$ の全ての $c_1$ を $c_2$ に、 $c_2$ を $c_1$ に置き換える
$S$ を $T$ にできるか判定せよ

例

ikatakos
   ↓    a,i
akitikos
   ↓    s,z
akitikoz

解法

$S$ 中の同じアルファベットが $T$ で違う文字になっていたら無理
$T$ 中の同じアルファベットが $S$ で違う文字になっていたら無理

後者は一見行けそうと思うが、操作は1回ずつ順番に行うので、

S: abcd
T: eefg

abcd
 ↓  a,e
ebcd
 ↓  b,e
becd

aもbもeにしたいが、aをeにし、次にbをeにしようとすると、eに変化させた最初の文字がbになってしまう。

で、これさえ満たせば大丈夫。 $S$ の先頭から順番に $T$ と合わせていけばよい。

……んだけど、本当に大丈夫か、見落としが無いか、というのが感覚的に確信持ちにくい問題と感じた。

        
          
          
              
              def solve(s, t):
    dic1, dic2 = {}, {}
    for c, d in zip(s, t):
        if c in dic1:
            if dic1[c] != d:
                return False
        else:
            dic1[c] = d
        if d in dic2:
            if dic2[d] != c:
                return False
        else:
            dic2[d] = c
    return True
 
 
s = input()
t = input()
print('Yes' if solve(s, t) else 'No')

            

        
      

D - Factorization

問題

$N,M$ が与えられる
以下の条件を満たす長さ $N$ の数列が何通りあるか、 $\mod 10^9+7$ で求めよ
- 数列の項を全て掛け合わせると、積が $M$
数列は順序も考慮する
- たとえば $\{1,6\}$ と $\{6,1\}$ は別に数える
$1 \le N \le 10^5$
$1 \le M \le 10^9$

解法

$M$ を素因数分解する。

たとえば $M=64800=2^5+3^4+5^2$ とする。数列の $N$ 個の項でこれらの素因数を分配することになる。

赤いボールが5個、青いボールが4個、黄色いボールが2個あります。

$N$ 個の箱にこれらのボールを入れる時、入れ方は何通りありますか。

ただし同じ色のボールは区別しません。箱は区別します。

という問題と同じことになる。

個別に見ていく。まず、5個の'2'の振り分け方を決める。このパターン数は重複組み合わせで求められる。 ${}_NH_5$

N=6
{ 1, 1, 1, 1, 1, 1}  初期状態

  6個の項から、重複を許して2をかける項を5個選ぶ
(一例)
{ 1, 2, 2, 2, 2, 2}
{ 2, 1, 8, 1, 1, 2}
{32, 1, 1, 1, 1, 1}

同様に、4個の'3'、2個の'5'の振り分け方も求める。

答えは、これらの振り分け方の掛け合わせとなる。素因数なので、このやり方でダブることは無い。

$ANS={}_NH_5 \times {}_NH_4 \times {}_NH_2$

MODで組み合わせ数を計算するので、あらかじめ $N+(素因数分解の指数の最大値)-1$ までの階乗とその逆数を $\mod{10^9+7}$ で求めておく。

MODの階乗と逆数の計算や、素因数分解など、競プロ用のライブラリを持っているかどうかで実装難度が変わってくる。

なお、AtCoderでは使えないが、SymPyには素因数分解モジュールが存在する。この辺使いたいよねー。（ものぐさ思考）

整数論 — 読書ノート v1.5dev

        
          
          
              
              def prepare(n, MOD):
    f = 1
    factorials = [1] * (n + 1)
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials[m] = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
 
    return factorials, invs
 
 
def prime_factorize(n):
    r2 = len(bin(n & -n)) - 3
    if r2:
        yield r2
    i = 3
    k = n
    while 1 < k and i * i <= k:
        cnt = 0
        while True:
            d, m = divmod(k, i)
            if m == 0:
                cnt += 1
                k = d
            else:
                break
        if cnt:
            yield cnt
        i += 2
    if k > 1:
        yield 1
 
 
MOD = 1000000007
n, m = map(int, input().split())
pf = list(prime_factorize(m))
mx = max(pf)
f, r = prepare(n + mx - 1, MOD)
ans = 1
for e in pf:
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)

            

        
      