Blocks を解くときに使った、新規性のある話題なのでメモ。 長さ \(N\) の文字列 \(S\) があります。 「単位文字列が何度繰り返されているか」を (文字列の長さ) / (文字列の長さの約数である、文字列の周期) の 最大値で定義します。 例えば、 "hellohelloh…

これは Cow and Fields の解説で見たテクニックなのですが、他でも見たことがある気がするのでまとめておきます。 今回解きたいのは以下の問題。 長さ \(N\) の \(2\) 整数の組 \((A_i,B_i)\) があります。 このとき、相異なる \(2\) つを選んだ時の \(min(A…

この記事では、 D - Distinct Boxes の解説の内容をざっくり日本語に翻訳します。 (簡単のために空の箱を1つ作ることを認めておき、最後に解を-1するという前提で議論を行います。) この問題では、「解 \(K\) を先に仮定して、\(K\) が実現可能かどうかは二…