| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
49 分 4 ペナ → 41位。
たぶん ABC コンテストで初の First AC なんですよね。はじめ「$A_1$ 個未満」の未満を「以下」にして解いていて、サンプルが合わない原因の調査で 2～3 分単位でロスしたので、可能性があるとすら思っていなくてびっくりしました。（結果的にはこれでも 8 分差あった）
2 位との時間差もわりと余裕があって、全体での AC 人数も少なかったので、難しいと感じた方が不思議と多かった問題だったのかもしれません。
全体では、E の実装でミスして解くのに 15 分もかけてしまったり、問題 C で嘘解法を連投していたりしていて、特に良い結果ではなかったですｗ
問題B – Minor Change
x = sum(s != t for s, t in zip(S, T))$(S[0], T[0]), (S[1], T[1]), \ldots$ などと複数の文字列（より一般に iterables）にアクセスするときに、zip(S, T) でイテレータを作成できます。
問題C – Tsundoku
上から貪欲にとる問題だと勘違いして…。
「ABC-C だし」みたいな思考法で雑をしましたねｗ
「マージソートのマージ部分ですか、初心者向けの良い題材ですねー」とか思っててひどいｗ
選べる選択肢は、「Aの山から x 冊、Bの山から y 冊」の形に限定されます。y を決め打ったときに最適な x が計算できるようにします。つまり、
$$A_1 + \cdots + A_x\leqq K – (B_1+\cdots + B_y) < A_1 + \cdots + A_{x+1}$$
を満たす $x$ を計算できるようにします。累積和を事前計算する（Acum, Bcum などと書くことにします）と、$\mathrm{Acum}_x\leqq K – \mathrm{Bcum}_y < \mathrm{Acum}_{x+1}$ を満たす $x$ を求める問題に変化します。
配列 Acum には単調性があるので、これは二分探索により求めることができます。
Python でこれを求める方法を挙げておきます。配列 A が昇順であるとします。
import bisect
n = bisect.bisect_left(A, x) # A[i] < x となる i の個数
n = bisect.bisect_right(A, x) # A[i] <= x となる i の個数
import numpy as np
n = np.searchsorted(A, x, side='left') # A[i] < x となる i の個数
n = np.searchsorted(A, x, side='right') # A[i] <= x となる i の個数bisect：https://docs.python.org/ja/3/library/bisect.html
numpy.searchsorted：https://numpy.org/doc/stable/reference/generated/numpy.searchsorted.html
返り値は「その数を挿入した場合の挿入先のインデックス」ということもありますが、個人的には、私は上のコメントのように「i の個数」と認識してから迷うことが少なくなりました。numpy.searchsorted は、第 2 引数に array を持たせることが多いと思います。
尺取り法を使う方法もあります。この記事では省略します。
問題 C にしてはレベルが高くてびっくりしました。問題 D ～ E ではめちゃくちゃ出題頻度が高いので、手法を思いつくところも実装するところも迷わずできるようになると役に立つと思います。
問題D – Sum of Divisors
（１）約数の個数の表をつくる
div = np.zeros(N+1, np.int64)
for n in range(1, N+1):
for m in range(n, N+1, n):
div[m] += 1$a$ が $n$ の約数であるような対 $(a,n)$ を探すとき、 $n$ を固定して $a$ を探すよりも、$a$ を固定して $n$ を探す方が効率的です。全体の計算量は $\Theta(N\log N)$ です。
なお、div[m] += m としておくことで、$f(K)$ を $Kf(K)$ に直す必要がなくなります。
（２）約数の個数の表をつくる（高速ゼータ変換）
私のコンテスト提出がこれです。計算量は $\Theta(N\log\log N)$ になります。$\log N$ と $\log \log N$ の差が問われることはほとんどない上に、実装量はすこし増えるので、下手な選択でしたね。
（３）約数の表をつくらない $\Theta(N)$
$$\sum_{n=1}^N nf(n) = \sum_{n=1}^{N}\sum_{a\mid n}n = \sum_{a=1}^N\sum_{a\mid N}
N$$
と変形します。各 $a$ に対して、$a + 2a + 3a + \cdots$ を $N$ 以下の範囲で計算すればよいです。この計算は、等差数列の和なのでループなしに計算できて、全体では$\Theta(N)$ 時間になります。
（４）約数の表をつくらない $\Theta(N^{1/2})$
$$\sum_{n=1}^N nf(n) = \sum_{n=1}^{N}\sum_{a\mid n}n = \sum_{n=1}^N \sum_{ab=n}n = \sum_{ab\leq N}ab$$
と変形します。$ab\leq N$ となる $(a,b)$ を全て生成しようとすると、やはり $\Theta(N\log N)$ の時間が必要になります。
一方、$\min(a,b)\leq \sqrt{N}$ となることに注意すれば、$k = \min(a,b)$ として
for k in range(1, int(N**.5)+1):
# (a, b) = (k, b), b>=k に対する計算
# (a, b) = (a, k), a<k に対する計算などの要領で計算できます。ループの内側でも、多くの b や a に対する計算が残っていますが、今回の状況ではここが等差数列になって、ループなしにまとめて計算できます。
$N=10^{12}$ 程度で、$\sum_{n=1}^{N} \text{（$n$ の約数の個数）}$ や $\sum_{n=1}^{N} \text{（$n$ の約数の和）}$ などを計算するのは、Project Euler などでは特に頻出です。
（５）約数の表をつくらない $O(N^{1/3+\varepsilon})$
リンクだけ貼っておきましょう。競プロでACに必須になったことは見たことがありませんが、初等的な面白いアルゴリズムです。
（追記）（１）の解法を、計算結果を配列に保持しないだけで 206 ms になりました。
x = 0
for a in range(1, N+1):
for n in range(a, N+1, a):
x += nメモリへのアクセス等がなくなるのが大きいということでしょうかね。numba.pycc.CC を利用した AOT を試していますが、コードにやや手を入れる必要がある（スニペットで貼るだけですが）ので、一番手軽なのは、numba.njit を単に利用するものだと思います。
(604ms) https://atcoder.jp/contests/abc172/submissions/14785584
600 ms もかかっていて不安になりますが、import + JITコンパイルに 550ms かかっている（N の小さなサンプルでの実行時間参照）ので、メインの計算は 50ms で終わっています。3000 ms 制限だと、計算に使えるのは 2450 ms あるので、TLE までには 50 倍近く余裕を余しているという見積もりになります。
より複雑な関数も考慮すると、JIT コンパイルの時間は無視できなくなる場合もあります。JIT の結果をキャッシュして、JIT コンパイルの時間を実行時間に含めない書き方が実践的にはなかなか良いように思います（signature を指定して、入力が与えられないコンパイル用の実行時に JIT が行われるようにする）。
問題E – NEQ
攪乱順列（完全順列） と呼ばれる数え上げを経験したことがあれば、それを再現すれば解けると思います。
$A_1 = 1, \ldots, A_N = N$ の場合の計算をします。（最後に適切な定数倍をかければよいです）。$B_i\neq i$ という条件がありますが、余事象の方がきわめて扱いやすいことに注意します。
相異なる $N$ 個の数を並べる方法の全体を $X$ とします。
- $X_k$：$B_k = k$ を満たすような数列 $B\in X$ 全体の集合
とします。求めるものは、$(X_1\cup X_2\cup \cdots X_N)$ の補集合です。$S = \{k_1,\ldots,k_m\}$ に対して $X_S := X_{k_1}\cap X_{k_2}\cap \cdots X_{k_m}$ と書くことにすると、
$$|X_1\cup X_2\cup \cdots X_N| = \sum_{S} (-1)^{|S|} |X_S|$$
が成り立ちます（包除原理）。$N=2,3$ の場合などは特に有名かもしれません。
- $|X_S|$ の値が $|S|$ のみに依存して計算できる。（よって、計算すべき $|X_S|$ は $2^N$ 件ではなく、$N$ 件しかない）
- $S=\{1,2,\ldots,k\}$ としたとき、相異なる数を並べた数列 $B$ が $X_S$ に属するための条件は、$B_1 = 1, \ldots, B_k=k$ という単純な条件になる。
ことから、この包除原理による立式により効率的に計算できます。
問題F – Unfair Nim
Nim は超有名問題ですので、知らなかった場合は勉強しておきましょう。アリ本 の 4.2 節を一通り見るなど。
めちゃくちゃ簡潔でありながら、独力で思いつくのはきわめて難しいタイプの典型だと思います。知識ゲー。
結局、問題は次の通りになります：
$a,b,c$ が与えられる。$0\leqq x < a$ であって、$(a-x) \xor (b+x) = c$ となる $x$ のうち、最小のものを求めよ。
$2$ 進法表記したときの、$1$ の位の様子で場合分けしました。
$x$ の $1$ の位を $0$ とした場合、より上位の位で (a//2, b//2, c//2) の問題を解けばよいです。$x$ の $1$ の位を $1$ とした場合、より上位の位で ((a-1)//2, (b+1)//2, c//2) の問題を解けばよいです。よって、メモ化再帰などで解くことができます。
結局これは 桁 dp と呼ばれるタイプの問題でした。
ABC 154-E , ABC 138-F, などでも同様の実装を取り上げています。
- $1$ の位で場合分けをする。上位の桁で再帰的な問題を解く。
- $N$ から $\lfloor (N\pm 1) / 2\rfloor$ への遷移などを繰り返す限り、$\lfloor N/2^k\rfloor \pm 1$ の形の数にしか遷移しないことから計算量解析ができる。
- メモ化再帰での実装はとても手軽。
- 桁数が巨大（$10^5$ 桁など）のときへの対策として、配列のループで計算する方法も対策しておく。（$\lfloor N/2^k\rfloor$ に比べていくつずれているのかを状態とすればよい）。
もっとも、「桁dp は再帰実装が簡単」という主張も、配列で実装する場合の状態の持たせ方（$\lfloor N/2^k\rfloor$ に比べていくつずれているのか）も独自に考えたものであって、最も普及しているものと少し違うっぽいので、合う・合わないがあると思います。
