Educational Codeforces Round 104のきろく

問題文和訳はこちら

A. Arena / Арена (実行時間制限: 1 sec)
B. Cat Cycle / Круговорот котов в квартире (実行時間制限: 1 sec)
C. Minimum Ties / Как можно меньше ничьих (実行時間制限: 1 sec)
D. Pythagorean Triples / Пифагоровы тройки
- $a$ の値を全探索
- 原始Πυθαγόρας数であることを利用
  - $a = x = p^2 - q^2$ のとき
  - $a = y = 2pq$ のとき
E. Cheap Dinner / Дешевый обед (実行時間制限: 4 sec): 未提出
F. Ones / Единицы (実行時間制限: 3 sec): 未提出
G. String Counting / Подсчет строк (実行時間制限: 10 sec): 未提出
結果、感想

A. Arena / Арена (実行時間制限: 1 sec)

レベルの一番小さい訳ではないヒーローを1人選び、そのヒーローとレベルの一番小さいヒーローを $100^{500}$ 回戦わせることによってそのヒーローを勝者にさせることができます。レベルの一番小さいヒーローについてはどのような組み合わせであっても勝つことができないため、勝者になることはありません。つまり答えは $n - \mathrm{cnt}(\text{最弱ヒーロー})$ です。

B. Cat Cycle / Круговорот котов в квартире (実行時間制限: 1 sec)

$n$ が偶数のとき、1度も猫Aと猫Bの行き先が重なることはありません。これは奇数時間目には猫Aは偶数箇所目に、猫Bは奇数箇所目に、偶数時間目には猫Aは奇数箇所目に、猫Bは偶数箇所目に行こうとするからです。この時答えは $((k-1) \bmod n) + 1$ となります。

$n$ が奇数のとき、 $\displaystyle\left\lfloor \frac{n}{2} \right\rfloor m + 1$ $(m \in \mathbb{N}^{+})$ 時間目に行き先がかぶります。最初に $\displaystyle\left\lfloor \frac{n}{2} \right\rfloor + 1$ 時間目に行き先がかぶった時、猫Bが行き先を変更しますが、その行き先を変更した後の状況は場所のインデックス全体をスライドさせることによって最初の状況と変わらないことがわかり、 $\displaystyle\left\lfloor \frac{n}{2} \right\rfloor$ 時間の周期で行き先がかぶることが分かります。実際の猫Bのいる場所は最後に行き先がかぶった時にAがどこにいたかを基にそこから何個先に進んだ場所かを計算することで求まります。

C. Minimum Ties / Как можно меньше ничьих (実行時間制限: 1 sec)

$n$ が奇数の場合、各チームは他のチームの内半分に勝ち、もう半分に負けることで全チームの点数を同じにすることができます。そのような結果は今回の出力フォーマットでは $1$ と $-1$ を交互に出力させるような形式でつくることができます。このようにして全体の引き分け数 $0$ の例が作れます。

$n$ が偶数の場合各チームが少なくとも1回は引き分けになる試合をしないと全チームの点数を同じにすることができません。逆にそれぞれにチームについて引き分けにするペアを1つずつ決めてやることで全体の引き分け数 $\displaystyle\frac{n}{2}$ の例を構成することができ、これが最小です。具体的に構成する場合は各ペアを $(2i - 1,\,2i)$ $(1 \leq i \leq \displaystyle\frac{n}{2})$ としてそれらの間の試合を引き分けにし、また、同様の $i,\,j$ について $(2i - 1,\,2j - 1)$ と $(2i,\,2j)$ の試合をそれぞれ左側が、 $(2i - 1,\,2j)$ と $(2i,\,2j - 1)$ の試合をそれぞれ右側が勝利したことにすると楽に実装できます。

D. Pythagorean Triples / Пифагоровы тройки

Πυθαγόρας*1の三平方の定理から $a^2 = c^2 - b^2$ 、Вася*2の式から $a^2 = c + b$ となるため $$\begin{align}
a^2 = c + b = c^2 - b^2
\\ \therefore (c+b)(c-b-1) = 0
\end{align} $$ であり、 $b$ も $c$ も正整数であるため、 $c + b \neq 0$ より $c = b + 1$ であることが分かります。ここから2つの解法を考えました。

$a$ の値を全探索

$c = b + 1$ を三平方の定理かВасяの式*3に代入すると $a^2 = 2b+ 1 = 2c - 1$ となります。 $c \leq n$ であることから、 $a \leq \sqrt{2n - 1}$ の範囲で調べ上げてやればいいことが分かります。各奇数 $a$ について、 $a \leq \displaystyle\frac{a^2-1}{2}$ が成立するものについて数えてれば答えとなります。

原始Πυθαγόρας数であることを利用

$c = b + 1$ より $\mathrm{gcd}(a,\,b,\,c) = 1$ であることから $(a,\,b,\,c)$ は原始Πυθαγόρας数であることが分かります。原始Πυθαγόρας数 $(x,\,y,\,z)$ は正整数 $p,\,q$ $(p \gt q)$ を用いて $x = p^2 - q^2,$ $y = 2pq,$ $z = p^2 + q^2$ と表すことができます(参考)。ここで $a = \min\{x, y\},$ $b = \max\{x, y\},$ $c = z$ *4です。さてここで、 $a = x$ であるか $a = y$ であるかで場合分けします。

$a = x = p^2 - q^2$ のとき

$a = p^2 - q^2,$ $b = 2pq,$ $c = p^2+q^2$ であり、 $c = b + 1$ より $c - b = (p - q)^2 = 1$ より $p = q+1$ となります。
また、逆に $p = q + 1$ のとき $a = 2q + 1,$ $b = 2q(q + 1)$ であり $q +1 \geq 2$ であることから $a \leq b$ がちゃんと成立します。