ARC 084
C - Snuke Festival
- A, B, CのパーツがN個ずつあり、3種類を1つずつ組み合わせる
- 個々のパーツはサイズがあり、組み合わせる際は A < B < C となっていなくてはならない
- 組み合わせの数は？
Aのパーツを固定して $a_i$ を使うと決める
(入力例3をソートしたもの)
↓
A: 2 3 6 14 53 159
B: 6 9 58 79 84 323
C: 2 50 79 288 383 2643
$a_i$より大きいパーツBを求める
↓
A: 2 3 6 14 53 159
↓ ↓ ↓ ↓
B: 6 9 58 79 84 323
C: 2 50 79 288 383 2643
パーツBそれぞれについて、自身より大きいパーツCの個数を求める
(Bに58を選んだ場合)
↓
A: 2 3 6 14 53 159
↓
B: 6 9 58 79 84 323
↓ ↓ ↓ ↓ →4個
C: 2 50 79 288 383 2643
合計する。これが$a_i$を14に固定した時の組み合わせ数となる。
↓
A: 2 3 6 14 53 159 ┌ 58: 4個
↓ ↓ ↓ ↓ ├ 79: 3個
B: 6 9 58 79 84 323 ┼ 84: 3個
└323: 2個
C: 2 50 79 288 383 2643 → 計12個
全てのAのパーツについて求め、合計する。
でもこれだと遅いので、繰り返しになる計算はできるだけ省略したい。
数列の中である数より大きい要素数は、二分探索を用いて調べる。Pythonではbisectを使えば「ソートされた数列の中に要素eを挿入しようとした場合の、適切なindex」が得られるので、Nから引けばeより大きい要素数になる。
e : 14 -> bisect(B, e) = 2 B : [6 9 58 79 84 323] 要素数 6 - 2 = 4 →Bの中でeより大きい数は4つ
$b_1$～$b_N$について、それぞれより大きいパーツCの個数を求める。
その後、後ろから累積和を取る。BAとする。すると$ba_i$は「パーツAとして『$b_i$が自身より大きい最小のサイズであるような$a$』を使った場合の組み合わせ数」になる。
B: 6 9 58 79 84 323 C: 2 50 79 288 383 2643 各Bより大きいCの個数 [5個, 5個, 4個, 3個, 3個, 2個] 後ろからの累積和 [22, 17, 12, 8, 5, 2]
各パーツAについて、自身より大きい最小のパーツBを求め、そのBAの値を合計したのが答え。
A: 2 3 6 14 53 159 B: 6 9 58 79 84 323 各Aより大きい最小のパーツBと、そのindex パーツB: [6, 6, 9, 58, 58, 323] index : [0, 0, 1, 2, 2, 5] 各パーツBに対応したBAの値 [22, 22, 17, 12, 12, 2] →計87 => 答.87
import bisect
from itertools import accumulate
def solve(n, aa, bb, cc):
def f(ff, tt):
pv = 0
ret = [0] * n
for i, e in enumerate(ff):
ret[i] = pv = bisect.bisect(tt, e, pv)
return ret
ac = f(aa, bb)
bc = f(bb, cc)
ba = list(reversed(list(accumulate(n - b for b in reversed(bc)))))
lim = bisect.bisect_left(ac, n)
return sum(ba[a] for a in ac[:lim])
n = int(input())
aa = sorted(map(int, input().split()))
bb = sorted(map(int, input().split()))
cc = sorted(map(int, input().split()))
print(solve(n, aa, bb, cc))
D - Small Multiple
- 整数Kの倍数のうち、各桁の和が最小となるような数の、各桁の和を求める
- (例) 1235だと、各桁の和は1+2+3+5=11
全く解き方を思いつかず。解説を見るとまさかのグラフに帰着させるやつ。
- 1から始めて、「1を足す」か「10倍する」ことを繰り返すと、任意の数を作れる
- 1を足すと、各桁の和は1増える（1の位が9以外）
- 10倍すると、各桁の和は変わらない
- 1から、Kの倍数まで最短経路探索をする
なお、1の位が9の時に+1の法則が成り立たなくなる問題については、問題ない。たとえば1239の次は1240だが、10の位が+1され、1の位が-9されるため、各桁の和は必ず小さくなる。（10以降の位も9だったら連鎖的に繰り上がりが続くが、いずれにしろ小さくなる）最短経路探索のアルゴリズムはコストが小さい方から確定させていくため、1239が探索された時には1240は既に探索されている。そのため、「既に探索した数」を記録しておけば、後から1239経由のコストの高い1240が探索されても、無視すればよいだけである。
しかし、何らかの制限を設けないとコストが0の10倍ばかり無限に探索され、1を足した数が探索されない。ここで、次の視点が必要になる。
- この遷移は、modの世界でも変わらない
遷移の順番は、こんな感じになる。
１┬２┬ ３──┬４┬５┬ ６...
│ └ 20... │ │ └ 50...
└10┬ 11... │ └40┬ 41...
└100... └30... └400...
ここで、法を3としmodをとってみると、以下のようになり、mod 3で合同である1と4からの遷移が等しいことが分かる。また、省略してはいるが、他の1 (mod 3)である10, 100, 40などからの遷移も等しくなる。これは偶然では無く、遷移の式から必ずそうなる。
１┬２┬ ０──┬１┬２┬ ０...
│ └ ２... │ │ └ ２...
└１┬ ２... │ └１┬ ２...
└ １... └０... └ １...
法をKとすれば、最短経路探索の頂点数はK個に抑えられ、0 mod K はKの倍数ということなので、1から出発して0への最短経路を求めればよい･･････らしい。
正直、よく分かっていない。
たとえばK=6のとき、3≡9だが、3の各桁の和は3なのに対し、9は9である。Kを法として合同な2数が、必ず各桁の和までが等しいわけではない。「1から出発してx (mod K)までの最短経路のコストがcである」というのは、あくまで「各桁の和がc+1となるx (mod K)の数が少なくとも1つ存在し、それがx (mod K)の中では最小である」と言えるだけである。ならば、1からの最短経路探索でたどり着いた0が、本当の意味での答えであるKの倍数の各桁の和の最小値と等しいと言えるのか？
たとえば最短経路探索で1→…→x→…→0と遷移できた時に、1→xの遷移でたどり着いたx mod Kが表す本当の数X1と、x→0の遷移で0にたどり着けるx mod Kが表す本当の数X2は等しいと言っていいのか？
と思ったが、X2からの遷移で0に行けたなら、全く同じ遷移でX1から0に行けるはずなので、最短経路は変わらないのか。う～む。
こんな発想無理
from collections import deque
def solve(k):
que = deque([(1, 1)])
checked = set()
while True:
cost, num = que.popleft()
if num == 0 or num == k:
return cost
if num in checked:
continue
checked.add(num)
que.appendleft((cost, num * 10 % k))
que.append((cost + 1, num + 1))
print(solve(int(input())))
E - Finite Encyclopedia of Integer Sequences
E - Finite Encyclopedia of Integer Sequences
- 1～Kの数を用いて、要素数1～Nの数列を作る
- 全ての数列を辞書順に並べた時、丁度真ん中（偶数個の場合は小さい方）の要素を出力せよ
できる数列の総数は、等比数列の和となるので、$\displaystyle \frac{k^{n+1}-1}{k-1}-1$となる。（あんまり関係ないけど）
K=3, N=2 ┌────┼────┐ １ ２ ３ ／│＼ ／│＼ ／│＼ １ ２ ３ １ ２ ３ １ ２ ３
こんな完全K分木を作ると、１つの節点が、できる数列の１つに対応する。（葉以外のノードは、長さがNに満たない数列）
よって、K=偶数の場合、左半分と右半分の個数が等しくなるので、真ん中の数列とは、左半分の最後、つまり最も右端を辿っていった数列となる。
K=4, N=2 ┌────┬────┬────┐ １ ② ３ ４ ／/\＼ ／/\＼ ／/\＼ ／/\＼ １２３４ １２３④ １２３４ １２３４
K=奇数の場合、直感的には真ん中を突っ切った数列(2,2,2)が答えのように思えるが…
K=3, N=3
┌────┼────┐
１ ② ３
／│＼ ／│＼ ／│＼
１ ２ ３ １ ② ３ １ ２ ３
(略) ／│＼ (略)
１ ② ３
実際は、(2,2,1)となる。長さが「Nの数列」ではなく「1～Nの数列」を辞書順に並べるため、長さがN未満の数列が(2,2,2)の前に配置されている。その分、真ん中の位置も手前にずれる形になる。
以下、(2,2,2)のように、Kの中央値をN個並べた数列を「仮の真ん中」と呼ぶ。一方、本当の答えを「本当の真ん中」と呼ぶ。
・全ての数列を列挙
・頭が「1」の数列と「3」の数列は個数が一緒なので省いて考える
(1) (1,1) ... (1,3,3) (2) (2,1) ... (2,3,3) (3) (3,1) ... (3,3,3)
~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~
・同様に「2,1」と「2,3」で始まる数列は省く
(2) (2,1) (2,1,1) ... (2,1,3) (2,2) (2,2,1) (2,2,2) (2,2,3) (2,3) (2,3,1) ... (2,3,3)
~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~
・「2,2,1」と「2,2,3」も同数なので省く
(2) (2,2) (2,2,1) (2,2,2) (2,2,3)
~~~~~~~ ~~~~~~~
(2) (2,2) (2,2,2)
(2,2,2)の前後から同数のものを省いたのだから、本当に(2,2,2)が真ん中なら、残った数列の中でも真ん中であるはずだが、実際はそうならない。(2)と(2,2)が入ることにより、ズレていることがわかる。
ではいくつずらせば良いかというと、手前に配置される長さN未満の数列の数がN-1個なので、その半分となる。
本当の真ん中 仮の真ん中
N/2 番目 N番目
↓ ↓
(2) (2,2) (2,2,2) ... (2,2,...,2) (2,..2,2)
└────── N-1個 ──────┘
差: N/2 (小数点以下切り捨て)
ただし、これはあくまで前後から同数の数列を取り除いて残った数列の中での話。実際の答えは省かれた数列の中にあるかも知れない。だが、「本当の真ん中は、仮の真ん中からいくつズレているか」は変わらない。N/2だけ、仮の真ん中より戻った数列が答え。
手前の要素の求め方は、末尾文字に着目する。
- 末尾が「1」なら、取る
- 末尾が「1」以外なら、1減らし、長さがNに満たなければ、NまでKで埋める
これをN/2回繰り返せば良い。
def solve(k, n):
if k & 1 == 0:
return [k // 2] + [k] * (n - 1)
ans = [k // 2 + 1] * n
l = n
for i in range(n // 2):
if ans[-1] == 1:
ans.pop()
l -= 1
else:
ans[-1] -= 1
if l < n:
ans += [k] * (n - l)
l = n
return ans
k, n = map(int, input().split())
print(*solve(k, n))
