過去問を解いたので解説します。

F. Multicolored Markers

問題概要：整数 a, b (≤10^14) が与えられる。無限大の方眼紙の a マスを赤く、b マスを青く塗った。塗られた領域 R は長方形である。赤い領域か青い領域の少なくとも一方は長方形になっている。長方形 R の周長 (4辺の長さの和) の最小値を求めよ。

不要な対称性をなくすため、必ず赤い領域が長方形になることにします。(後で a と b を入れ替えて同じ計算をして最小値をとればいい。一般性を失わない。)

赤い領域は長方形 R のどの部分にあってもいいので、長方形の幅と高さだけ考えていけばよさそうです。長方形 R の縦横の辺長をそれぞれ y, x とおき、赤長方形の縦横の辺長をそれぞれ t, u とおきます。

満たすべき条件は次のような感じです。

y・x = a + b ……(Rの面積)
t・u = a ……(赤の面積)
y ≥ t & x ≥ u ……(赤がはみ出ない)
y, x, t, u は正の整数 (重要)

x, u はそれぞれ y, t から決まって、 x = (a + b) / y、u = a / t です。これを使えば、

x ≥ u
⇔ (a+b) / y ≥ a / t
⇔ t・(a+b)/a ≥ y

と変形できて、 y の範囲が t ≤ y ≤ t・(a+b)/a に絞られます。

しゃくとりのにおい。

t を昇順で列挙するループにおいて、そのときの y の範囲内における部分解 (周長の最小値) をしゃくとり法で列挙、というアルゴリズムが考えられます。いくぶん天下り的ですけれども。可能でしょうか？

y, t はそれぞれ a+b, a の約数です。整数 n の約数は O(√n) 個あります。√a はいま 10^7 のオーダーなので、約数 t の全列挙は可能です。

当て推量のような考察でしたが、解けたのでよし。

提出：

おまけ: Rust のしゃくとり法

一般的なしゃくとり法自体の解説は避けますが、Rust で書く場合について簡単に触れておきます。

標準ライブラリにある BinaryHeap (二項ヒープ) を使って次のようにします。

1. y の範囲が広がるたびに周長の値 2・(y + x) をヒープに挿入する。
2. y の範囲が縮むたびに、対応する周長をヒープから除去する。
3. (t の値に対する) y の範囲が確定したとき、ヒープから最小値をポップする。

ここで、コツが2つあります。

(一) BinaryHeap は最大値を取得するものであって、最小値は取れません。最小値をとるには、要素の大小関係を逆転する必要があります。符号を反転させるというのが定石ですが、符号の取り違えというのはやりがちなミスなので怖い。

Reverse を使うのがベターです。要素を Reverse(x) でラップして挿入するのです。これは x と逆の大小関係を持つ値として扱われますから、ヒープから出てきた「最大」の Reverse(x) は最小の x 、ということになります。

(現在の AtCoder の Rust 1.15.0 にはまだ Reverse がないので、自作しておくのがおすすめ。今回の提出でも使っています。Codeforces だから Reverse を使えばいいのに……)

(二) BinaryHeap は特定の要素を除去する機能を持ちません。今回は代わりに、要素として周長だけでなく y の値も記録しておき、範囲外の y に対応する要素がポップされたときは無視する、という手順にしています。