[AtCoder 参加感想] 2020/04/12:ABC 162

	A	B	C	D	E	F
問題文	■	■	■	■	■	■
自分の提出	■	■	■	■	■	■
結果	AC	AC	AC	AC	AC	AC

全体感想
問題A – Lucky 7
問題B – FizzBuzz Sum
問題C – Sum of gcd of Tuples (Easy)
問題D – RGB Triplets
問題 E – Sum of gcd of Tuples (Hard)
問題 F – Select Half

全体感想

26分全完で、20位でした。

言語アプデと関係なく、個人的に環境をちょっといじった直後だったので、少しトラブルもありました。数分ロスしたかな？

問題A – Lucky 7

いくつかの方法があります。

while N:
  N, r = divmod(N, 10)
  # r に対する処理

として各桁の数を見ましたが、文字列としても良かったですね。

print('Yes' if N.count('7') else 'No')
print('Yes' if N.find('7') != -1 else 'No')

問題B – FizzBuzz Sum

numpy によるベクトル演算。簡単なものから慣らしてはいかがでしょうか。

x = np.arange(N + 1, dtype=np.int64)
x[::3] = 0
x[::5] = 0
print(x.sum())

問題C – Sum of gcd of Tuples (Easy)

x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)

ufunc $f$ に対して $C[i,j] = f(A[i], B[j])$ のタイプの array $C$ を得るためには、ufunc.outer が簡潔ですね。他に、軸を次元を変えてからブロードキャストする方法（$C = f(A[:,None], B[None, :]$ など）もあります。（None は np.nexaxis と同義）

問題D – RGB Triplets

$j – i = k – j$ の場合を引きます。

for i in range(N):
  for j in range(i+1, N):
    k = j + j - i

のようにしてもよいですし、

for i in range(N):
  for d in range(1, N):
    j = i + d
    k = j + d

のようにしてもよいと思います。この手の処理は Python の苦手分野ですが、Numba, PyPy, Cython などの高速化手段が AtCoder 環境に充実しています。私も不勉強な話が多いので、これを機に練習の機会が増えたり、他の人のコードから学びやすくなってスキルアップできることを期待しています。

先週ツイートしたものをいくつか貼っておきます。

たぶんしばらく、「cython / numba を使ったのに遅いじゃねーか」案件多発するんですよね。動けばヨシ！で使ってみるよりは、公式のチュートリアルをこなしたり、プロファイリング方法を学ぶことが有益かと思います。

その点皆さんご存知のように、pypyはほぼ勉強なしで使えるのはすごいところです。
— maspy (@maspy_stars) April 7, 2020

1. Cython 832ms / 8991ms
cython は、最適化できなかったコードはあきらめてpythonで動かしたりして、極端にパフォーマンスが落ちることがあります。

どのオブジェクトが最適化を妨げているかをプロファイリングする方法もあるので、使用を考えている方はよく勉強しておくとよいです。 pic.twitter.com/9okzswGPpJ
— maspy (@maspy_stars) April 7, 2020

2. Python + Numba 977ms
JITコンパイル用のモジュール numba が、アプデで導入。977ms かかっていますが、2 枚目を見ると、その半分以上が import / JITコンパイルであり、主要な計算は速くTLEに強いことが分かります。

なお制限時間が長いほど、この辺のオーバーヘッドが問題にならなくなります。 pic.twitter.com/5Jw48EoFiN
— maspy (@maspy_stars) April 7, 2020

numba.jit も、上手く最適化できない部分は python オブジェクトのままあれこれやってくれます。ただし先ほど挙げた cython の例を見ても、エラーが出てくれる方が嬉しいことが多いです。
numba 公式でも @jit(nopython=True) あるいは同義の @njit が推奨されています。
— maspy (@maspy_stars) April 7, 2020

問題 E – Sum of gcd of Tuples (Hard)

「$\gcd$ が $d$ に等しい」という条件は扱いにくいのですが、「$\gcd$ が $d$ の倍数である」という条件は扱いやすいです。

$\gcd$ が $d$ に等しいものの個数を $A(d)$ とし、$\gcd$ が $d$ の倍数であるようなものの個数を $B(d)$ とします。このとき、$B(d) = \sum_{d\mid n} A(d)$ が成り立ちます。

これは、ゼータ変換と呼ばれるものの一種で、$F$ から $f$ はメビウス変換により得られます。

これの最も有名な場合が累積和で、例えば $2$ 次元累積和

$$B[i,j] = \sum_{k\leq i, l\leq j} A[i,j]$$

がゼータ変換です。この場合には、ゼータ変換（$2$ 次元累積和）の高速化ができて、各軸について累積和をとることを繰りかえせばよいです。この逆変換（メビウス変換）は、各軸について差分をとればよいです（高速ゼータ変換・高速メビウス変換の一種）。

自然数の整除関係は、だいたい多次元の格子の順序と同じですから、同種の操作が可能です。つまり、$n = 2^{n_2}3^{n_3}5^{n_5}\cdots$ が座標 $(n_2,n_3,n_5,\ldots)$ を持つとして、累積和の真似をしてあげればよいです（ただし今回は、約数に向かって足しこむため、逆の順序になっています）。$N$ を適当にとり、$P$ を $N$ 以下の素数全体とします。

ゼータ変換：$A\colon [1,N] \longrightarrow \Z$ が与えられたとき、$B\colon [1,N]\longrightarrow \Z$ を $$B(d) = \sum{d\mid n} A(n)$$となる $B$ を計算せよ。

【高速ゼータ変換】

B = A.copy()
for p in P:
  for i in range(N//p + 1):
    A[i] += A[i*p]

メビウス変換：$B\colon [1,N] \longrightarrow \Z$ が与えられたとき、$B\colon [1,N]\longrightarrow \Z$ を $$B(d) = \sum{d\mid n} A(n)$$となる $A$ を計算せよ。

【高速メビウス変換】

A = B.copy()
for p in P:
  for i in range(N//p + 1):
    B[i] -= B[i*p]

元の配列を破壊してよければ、copy は不要です。in-place に処理できます。
どちらもほぼ定義通りの愚直な計算（特にゼータは分かりやすい）によって、計算量 $\Theta(N\log N)$ での計算が可能ですが、高速ゼータ・メビウス変換をすると、計算量が $\Theta(N\log\log N)$ に落ちます。

私は高速化せずに通しましたが、高速ゼータ・メビウスによる解法コードも載せておきます → ■

問題 F – Select Half

どの時点で見ても「だいたい半分」の個数をとらなければいけないことが分かります。

$k$ 番目まで見たときに、 $\lfloor\frac{k-1}{2}\rfloor$ , $\lfloor\frac{k+1}{2}\rfloor$ のどちらかの個数をとった状態だけを持っておけばよいです。

したがって、$2$ つの配列を持って dp をすればよさそうで……。

さらに、「最後の数を選んでいるか」のフラグも必要ですね。配列で書けた方が良いのですが、状態と添字の対応が面倒になったので、defaultdict を使って、（$k$ 番目まで見て $j$ 個選んでいる）ときに、タプル $(k,j)$ がキーとなるように実装しました。

計算量は余裕があるので、戦略としては悪くなかったと思います。