競技プログラミングの大会が毎週開催されるより幸福なことがあるだろうか？ 2日連続で開催されることだ！

昨日の CODE FESTIVAL 予選に続き、日曜日は通常の ABC-only 回です。結果は惨敗 (Bのみ正答) でしたが、まるで完全に理解したかのように解説を書いていきます。

AtCoder Beginner Contest 110

問題リスト：

A - Maximize the Formula

問題概要：1~9 の数字がかかれた3つのパネルと、'+' がかかれた1枚のパネルを好きな順番に並べて足し算の式にした。式の値の最大値を求めよ。

解説：例えば 1, 2, 3 から 12+3, 1+23, 21+3, ... 32+1 などの式が作れます。ただし +123 はダメ。

式は AB+C の形になりますが、10の位 A が大きいほど結果が大きくなるので、最大値をそこに置くのがベストです。式の値は 10A + B + C なので B と C はどっちでもいいです。

結局、A, B, C のどれが最大かで場合分けすればOK。

A, B, C を降順にソートして A ≥ B ≥ C にすることで、必ず A が最大になるようにすると楽に書けます。(あるいは max 関数を使う。)

提出 (コンテスト終了後)：

B - 1 Dimensional World's Tale

問題概要：数直線上にA帝国の首都 (位置 X) とN個の都市 (位置 x[i]) があり、B帝国の首都 (位置 Y) とM個の都市 (位置 y[j]) がある。次の条件を満たす整数Zが存在するか判定せよ。

X < Z ≤ Y
すべての i について x[i] < Z
すべての j について y[j] ≥ Z

解説：図を書くと分かりますが、首都と都市を区別する必要がないので、首都を都市リストに追加します。つまり、

 x[N + 1] = X
y[M + 1] = Y 

です。このとき最初の条件 X < Z ≤ Y は残りの2つの条件の一部になります。

都市の番号に意味がないので x[i], y[j] は昇順とします。条件は次のように変形できます。

x[1] ≤ x[2] ≤ ... ≤ x[N+1] < Z ≤ y[1] ≤ ... ≤ y[M+1]

結局、x[N+1] < y[1] ならOKです。

提出：

C - String Transformation

問題概要：英小文字からなる文字列 S, T が与えられる。S の中の英小文字 X をすべて別の英小文字 Y に置き換え、同時に Y を X に置き換える、という交換操作を好きなだけ行う。S を T に一致させられるか判定せよ。

解説：例えば S=azzel, T=apple なら

azzel
→ appel (z と p を交換した)
→ apple (e と l を交換した)

として一致させられます。

一方、 S=chokudai, T=redcoder なら一致させられません。最初と最後の文字だけ取り出して S'=ci, T'=rr に注目すると分かります。文字の交換をどれだけ繰り返しても、異なる文字が一致することはないので、これは無理です。

別の例として S=test, T=fail を考えます。

i: 1 2 3 4
S: t e s t
T: f a i l

先頭と末尾に注目すると S'=tt, T'=fl ですが、S=T にするには t の一部を別々の文字にしなければいけないので無理です。

逆に交換操作で作れないのはこの2つのケースだけです。つまり、

1. 英小文字 X について S[i]=X になっているすべての位置 i で T[i] が等しい。
2. S, T を入れ替えても同じことがいえる。

このときは何らかの置換があります。(互換の積で任意の置換を生成できるから)

提出 (コンテスト終了後)：

模範解答：公式の解説によれば、交換手順を具体的に構成することもできるようです。

最終的に S を T に一致させられたと仮定します。文字 X が Y に書き換わったとして、これを F(X) = Y および G(Y) = X と書きます。F, G を連想配列として持っておいて、具体的な X, Y を割り当てていき、矛盾がなければOKです。

まず先頭の文字 S[1], T[1] に関して F(S[1]) = T[1] かつ G(T[1]) = S[1] になります。残りの文字に関して、F(S[i]) = Y の Y が判明済みなら Y=T[i] でなければならず、また G(T[i]) = X の X が判明済みなら X=S[i] でなければいけません。そうでなければ F(S[i]) = T[i], G(T[i]) = S[i] とします。 

提出：

D - Factorization

問題概要：正の整数 N, M が与えられる。正の整数からなる長さ N の数列 a で積が M に等しいものの個数を求めよ。(10^9+7で割ったあまりで答える。)

忙しい人のための解説：私は次の図をみてようやく分かりました。

数列 a の一例 (N = 3, M = 180)

a[1] = 2^1・3^1・5^0
a[2] = 2^0・3^1・5^1
a[3] = 2^1・3^0・5^0
M    = 2^2・3^2・5^1

数列 a は、M の各素因数 p につき、その重複度 m をa の要素に配分することと対応します。つまり素因数分解してから重複組み合わせを N 回やって掛ければOK。

解説：

技術スタックならぬ数学スタックが深いので簡単にみていきます。

1. 素因数分解
2. 素因数分解のアルゴリズム
3. 重複組み合わせ
4. 有限体上の二項係数

1. 素因数分解

正の整数は素数の積で一意に表せます。例えば 12 = 2・2・3 = 2^2・3 です。

ここであえて素数をすべて使って、

12 = 2^2・3^1・5^0・7^0・11^0・……

という無限の積とみなすこともできます。すると正の整数は、これらの素数にかかる指数の列と 1:1 に対応します。

12 = 2^2・3^1・5^0・7^0・… ↔ (2, 1, 0, 0, 0, ...)
15 = 2^0・3^1・5^1・7^0・… ↔ (0, 1, 1, 0, 0, ...)

ここで上記の考えを使えば、「素因数分解して重複組み合わせ」という解法に到達します。そこからの実装も長いんですけどね……

2. 素因数分解のアルゴリズム

正の整数 M を素因数分解する単純な方法は、小さい数から割っていくことです。p = 2 で M を割れるだけ割って、p = 3 で割れるだけ割って、p = 4 では割れなくて、というのを繰り返す。

M が持つ √M より大きい素因数 P はあっても1つなので、p ≤ √M の範囲でのループが終わった時点で、M は 1 か P (その巨大素因数) のどちらかです。

3. 重複組み合わせ

重複組合せについては、昨日の 競プロ参戦記 第14回「上限」 で軽く説明したので、参考のリンクだけ張っときます。

4. 有限体上の二項係数

有限体 (「整数を素数 p で割ったあまり」の加減乗除) について説明する気力はないです。

組み合わせを数えるには二項係数 C(n, r) = n! / ((n - r)!・r!) を使います。今回は 10^9+7 (素数) で割ったあまりを計算しなければいけません。

いろいろやりかたはありますが、フェルマーの小定理を使うのが簡単です。例によって「高校数学の美しい物語」を参考：

つまり p が素数なら a・a^(p-2) = 1 (mod p) になるようです。だから「a で割る」の代わりに「a^(p-2) をかける」をやればいい。

p = 10^9+7 は巨大なので、冪 a^(p-2) の計算にも工夫が必要です。繰り返し2乗法を使います。y = 1 として x^n = y・x^n とみなし、次の式を繰り返し適用して y, x, n を変化させていき、最終的に y=x^n, x=?, n=0 にします。

y・x^0 = y
y・x^(2n) = y・(x^2)^n
y・x^(2n + 1) = (y・x)・x^(2n)

計算量は、ループが2周するごとに n が半分になるので O(log n) 時間です。

こうして逆元が求まりました。

あとは階乗をDPで求めてから、階乗の逆元 (n!)^(p-2) を記録しておき、二項係数の計算に使います。

提出 (コンテスト終了後)：

重複組み合わせに帰着した後の流れはよくある問題だったので、慣れている人はCより気楽だったらしい。

おわりに

考察力不足が露呈し続けている昨今