| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | |||||
| 結果 | AC |
全体感想
43分でBのみの1完。537位で、個人的に過去最低順位という結果でした。
28日ぶりのratedコンテスト。この28日間、かなり熱心に過去問に取り組んでいたこともあり、悔しい結果です。
速解きには苦手意識があって、特に110分だと多くの問題数を考えるのは難しいことが分かっていたので、一通り読んですぐに道筋が見えそうに感じたBとCを考えていました。問題Cがあと1歩で解ききれず。
過去問やってる感覚からすると、平常通りで大失敗という感じではないです。過去問ではAGC-B,C難易度は全制覇できましたが、2～3時間かけて解いているような問題もそこそこあって。もう少し手早く解ききれるようにしていかないと、短時間競技ではかなり運ゲーっぽい感じになってしまいますねｗ
逆に上振れる回もそろそろ来ると期待して、落ち込みすぎずまた次頑張ります(^^)
考察の中枢部を抜けるまでよりも、そこから先の細部を詰め切るところが甘いことが多いような気がしてきました。問題Bでも少しはまって、もう数段階運が悪ければ0完でもおかしくない立ち回りでしたし。その辺を意識的に改善していけると良さそうですね。
問題B – Sorting a Segment
ある2つの区間に対して、ソート後の並びが等しくなるとしましょう。
・1 2 5 6 3 7 4 8 9 → 1 2 3 4 5 6 7 8 9
・1 2 5 6 3 7 4 8 9 → 1 2 3 4 5 6 7 8 9
このようなことがいつ起きるかを考えると、
・[小 小] [中 中 中 中 中] [大 大]・[小 小] [中 中 中 中 中] [大 大]両端がソートしても位置が変わらない形状になっているときだと分かります。
任意の2区間に対して結果の一致がすぐに判定できたとしても、計算量があまり減りません。そこである区間に対して、自身より左側の区間を1度にまとめて考察したいです。その方向で考えていると、
・[小 小] [中 中 中 中 中] [大 大]・[小 小] [中 中 中 中 中] [大 大]・[小 小] [中 中 中 中 中] [大 大]
ソート結果が一致するような区間が連番に並ぶと分かります。
したがって、ある区間のソート結果は、ひとつ手前の区間のソート結果と異なる場合に限り「これまでの全ての区間のソート結果と異なる」ことが分かります……。
これがちょっとだけ嘘で、ソートしても順序が変わっていないような区間については上図のような交わりがなくても同一のソート結果（ソート前と同一）になります。これは [入力例3] のおかげで気づくことができました。
結局、
(1) ある区間の結果が、ひとつ手前の区間の結果と同一であるかどうかを調べる
(2) ある区間がソートしても順序が変わらないかどうか調べる
という2つの課題が必要です。
(1)は「区間の最小値が左端であるのかどうか」「区間の最大値が右端であるのかどうか」という情報から判定できて、RMQあるいはスライド最小値などの定跡が使えます（上位層は、アリ本相当の内容はほとんど定跡として取り入れていると思うので、追いつきたい人はまずアリ本を履修するのが手っ取り早いと思います）。(2)は累積和の要領で、区間内での増加回数を集計することでクリアしました。
(1)の内容は15分程度で考察・実装できたのですが、(2) の要素を見落としていて、その計算および両方を踏まえた答の計算、また他に見落としている要素がないかの検証等に時間がかかりました。
問題C – LCMs
$\mathrm{lcm}(a,b) = \frac{ab}{\mathrm{gcd}(a,b)}$ であること、$d = \mathrm{gcd}(a,b)$ ごとに問題を分割して計算したいと考えます。ほかに、ひとつずつ素数 $p$ の影響を補正していくようなことを考えましたが、うまくいかず破棄しました。
$d = \mathrm{gcd}(a,b)$ という条件はまだ扱いづらいです。一方で、$d \mid \mathrm{gcd}(a,b)$ という条件は扱いやすいです（$d\mid n$ は、$d$ が $n$ の約数であるという記号）。これは、$d\mid \mathrm{gcd}(a,b)\iff d\mid a\text{かつ}d\mid b$ となって、2つ組としての性質ではなく $a,b$ 各々の性質に分離できるからです。あまり意識したことがなかったですが、
・$d = \mathrm{gcd}(a,b)$ に対する計算 → $d\mid \mathrm{gcd}(a,b)$ に対する計算
という帰着は、型として覚えておくべきかなと思いました。さて、課題を列挙します。
・ $f(d) = \sum_{\mathrm{gcd}(a,b) = d} \mathrm{lcm}(a,b) \sum_{\mathrm{gcd}(a,b) = d} \frac{ab}{d}$ とするとき、$\sum_d f(d)$ を計算したい（最終目標）。
・ $g(d) = \sum_{d\mid a,b} ab$ を計算する（これを経由するしかなさそう）。
・$\sum_d f(d)$ を $g(d)$ たちから計算する。
$g(d)$ の計算は次を利用できます：
\[2\sum_{i<j}x_ix_j = \biggl(\sum_ix_i\biggr)^2 – \biggl(\sum_ix_i^2\biggr).\]$d$ の倍数を計算対象として、和や2乗和をすればよいです。$d$ の倍数はせいぜい $\frac{10^6}{d}$ 程度の種類数しかないため、全ての $d$ の倍数を集計することを全ての $d$ に対して行っても $O(10^6\log 10^6)$ 程度です。
$\sum_d f(d)$ を計算するにあたって、$f(d)$ を $g(d)$ から計算することを考えると、個々の $f(d)$ は $g(d)$ たちの線形結合だと分かります。したがって、
$\sum_d f(d) = \sum_d x(d)g(d)$ の形で書けることが分かります。ここに、$\mathrm{gcd}(a,b) = d$ となる $(a,b)$ の寄与する割合が等しいことを考えると、係数が $\sum_{d\mid n} x(d) = \frac{1}{n}$ となることが分かります。
一般に、数列 $\{x(n)\}$ は、$\mathrm{gcd}(a,b)=1\implies x(ab) = x(a)x(b)$ を満たすとき乗法的であるといいます。$n$の約数の個数、約数の和、Euler関数などが代表的で、このような数列 $\{x(n)\}$ は $n$ の素因数分解を用いて要領よく計算できます。乗法的な数列について、次が知られています：
$y(n) = \sum_{d\mid n} x(d)$ とするとき、$x$ が乗法的であることと $y$ が乗法的であることが同値である。
$\sum_{d\mid n} x(d) = \frac{1}{n}$ を解くにあたって、右辺は自明に乗法的な数列なので、$x(d)$ は乗法的だと分かります。乗法的関数は、素数べきでの値から完全に計算されるので、$x(1), x(p), x(p^2), \ldots$ を考察すれば十分です。$n=p^{k-1}$, $n=p^k$ の場合の式の差分をとることで，$k\geq 1$ に対して $x(p^k) = \frac{1}{p^k} – \frac{1}{p^{k-1}} = \frac{1-p}{n}$ が成り立つことが分かるので，$x$ が乗法的であることと合わせると
\[ x(n) = \frac{1}{n}\prod_{p\mid n}(1-p)\] と求まり、素数 $p$ ごとに $p$ の倍数の部分の数値を書き換えていけば計算が終わります。
コンテスト終了後の提出 → ■
どのステップもある程度悩んでしまいましたが、確かにもっとスムーズにできるべき範囲だったかも。特に $x(d)$ が満たすべき条件式に勘違いをして、コンテスト時間内に解ききれず。あとちょっとでした。
