解くに至ったもの（4問）
ABC:117C/116C
みんプロ2019:D
全国統一プログラミング王決定戦:D
ABC117C
全く思いつかなかった
M個のチェックポイントにN個の駒を置いて、それらがチェックポイントをすべて移動しきるのにかかる経路の合計を最小にする問題
結局、N個の駒は移動することによりN個の区間を被覆することになる
実例を考えてみれば
1 2 3 4 5 6 7 8 9
を3つの駒で移動させることを考えると、例えば1,3,6に駒を置けば
[1,2],[3,4,5],[6,7,8,9]
と移動させることになり、区間は3つ
そうすると、考えるべきなのは、その区間にできるN-1個の境目の距離になる
例で言うと、[2,3]と[5,6]のような感じ
ここは、与えられたチェックポイントのうち、隣り合う2個のチェックポイントの距離にあたる（隣り合っているのは区間で被覆されているため）
そうすると、答えを出すうえで目指すべきなのは、全部は被覆するという前提を崩さず、いかにN-1個の境目の距離を大きくするかということになる
つまり、隣り合うチェックポイントの距離（N-1個）をソートして、上からN-1個取ってくる それを合計し、M個のチェックポイントのうち最も遠く離れた端と端の距離から引いたものが、求める駒の移動距離の最小値になる
解けなかったもの
ABC:084D/112C/113C
ABC084D
これを参考にして書いたコードがこちら
import math
L =
prime =
for i in range(2,100000):
L.append(i)
M =
m = 0
while m+1 < math.sqrt(100000):
m = L[0]
prime.append(m)
for i in L:
if i%m == 0 :
L.remove(i)
prime = prime+L
print(prime)
これだとTLEしてしまう 原因はremoveで、これは前から見ていって初めてその数字と同じになるやつを除くので、逐一検索していかないといけないため時間がかかる
（上のコードはせいぜい10^4までしか有用でない）
これを高速化する 参考にさせていただいたのはこちらのページ
#n以下の素数列挙(O(n log(n))
def primes(n):
ass =
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False ←ここまでで、素数判定のリストis_primeの要素の0,1番を
Falseにしたのと、ass（尻ではない）という、後に素数を
入れる空のリストを作成した
for i in range(2, int(n**0.5) + 1):
if not is_prime[i]:
continue ←ここでis_prime[i]がFalseならこれより下の文には進まな
い
for j in range(i * 2, n + 1, i):
is_prime[j] = False ←ここで、iの倍数をi*2からiの倍数ずつ見て、Falseにしてい
く
for i in range(len(is_prime)):
if is_prime[i]:
ass.append(i) ←is_prime[i] == Trueであるiだけをリストassに追加していく
return ass
これで10^5でも十分速くなった ちなみにjuppyさんによるとdel,remove,insertは300点問題からだと実用性に欠けるとのこと 肝に銘じておきます
