[AtCoder Daily Training HARD 2024/04/23 17:30start] 参加記録
AtCoder Daily Training HARD 2024/04/23 17:30start に参加しました。
後述しますが惜しくも2冠です。
E - Happy New Year!
もしくは こちら
考え方
0 と 2 の二つの文字のみを用いた数字列であることから、2進数をベースに考える。
N進数について
N進数は、N種類の数字を使って数を表す方法です。
数字は所詮文字でしかないので、 0 と 1 であろうが a と b であろうが何でも良いです。
ちなみに、中学受験算数では任意の文字の並び替えがN進数、順番が10進数である順列の問題をしばしば見ます。
そうすると、数 K を 2進数で表した後、 1 を 2 に置き換えれば求めるものになる。
def solve(k: int) -> int:
k_2 = bin(k)[2:]
rtn = ""
for k_i in k_2:
if k_i == "1":
rtn += "2"
else:
rtn += "0"
return int(rtn)
if __name__ == "__main__":
K = int(input())
print(solve(K))
感想
非常にシンプルです。
F - Repunit Trio
もしくは こちら
考え方
とりあえず並べてみる。
ちょうど 3 つのレピュニットの和として表せる整数を並べると以下の通り。
| r1 | r2 | r3 | sum |
|---|---|---|---|
| 1 | 1 | 1 | 3 |
| 1 | 1 | 11 | 13 |
| 1 | 11 | 11 | 23 |
| 11 | 11 | 11 | 33 |
| 1 | 1 | 111 | 113 |
| 1 | 11 | 111 | 123 |
| 11 | 11 | 111 | 133 |
| 1 | 111 | 111 | 223 |
| 11 | 111 | 111 | 233 |
| 111 | 111 | 111 | 333 |
レピュニットの特徴から一の位が必ず 3 であることがわかる。
よってそれより上の桁を見てみると桁数ごとに分離すると法則性が見つかる。
- 1桁: 0 (なし)
- 2桁: 1, 2, 3
- 3桁: 11, 12, 13, 21, 22, 33
N 桁の求める数は、1・2・3 の N-1 個の重複あり組み合わせに 3 を付け足したものになる。
さらに、それぞれ N 桁の数の種類は 1 から N までの和になる。
ということで、1桁から順に数えていって、条件を満たす桁数を見つけ出し、
K 番目まで残りを itertools の combinations_with_replacement を用いて数え上げる。
from itertools import combinations_with_replacement
def solve(n: int) -> int:
digit = 0
tmp = 0
for i in range(1, n + 1):
if tmp + (1 + i) * i // 2 >= n:
digit = i - 1
break
tmp += (1 + i) * i // 2
# print(f"digit: {digit} ({tmp})")
index = tmp + 1
for cmb in combinations_with_replacement(range(1, 4), digit):
if index == n:
return int("".join(map(str, (*cmb, 3))))
# print(f"{cmb} ({index})")
index += 1
return -1
if __name__ == "__main__":
N = int(input())
print(solve(N))
感想
一度解いたことがある問題だったはずでしたが、解法を思い出せず考え直してしまいました……
これに時間を取られていなければ、3冠できた可能性が非常に高いです。
G - Sum of Maximum Weights
もしくは こちら
考え方
概ね 公式解説 通り。
純粋に二つの頂点の組み合わせを列挙するだけで O(N) となり、今回の問題では決して間に合わないので、別のアプローチが必要。
ここで、必要なのが 経路の途中にある辺の最大の重み であることから、最終的な各2頂点の最短パスの重みは高々辺の数、つまり N-1 であることがわかる。
ここで、 木においてとある値を調べる という問題を 木を構築していきながら計算する と置き換えられることを利用する。
つまり、すでに構築済みの木を用いて計算するのではなく、辺を追加する都度状態を更新していくということ。
今回でいえば、辺を追加するたびに求めるべき値を更新していく。
重要なのは、 どの順番で辺を追加するか である。
今回は、辺の重みが小さい順についかすればうまくいくのではないかと考えた。
最短経路と指定されているが木であることから、経路がそもそも一意に定まる。
このことから、辺を足すことは木を合成することであると同時に、 二つの木それぞれから選んだ2頂点を結ぶ経路ができる ということになる。
足される辺の重みは、それまでの木に含まれるどの辺よりも大きいため、新しくできた経路の最大の重みは、新しく足された辺の重みになる。
結論として、重みが小さい順に辺を追加していくたびに、その辺を含む経路の最大の重みを足していけばいい。
木の合成を行うため、とりあえず UnionFind を用いる。
木 a と木 b を合成するとき、木 a の頂点数を n、木 b の頂点数を m とすると、合成時に増える経路の数は n * m である。
それら経路全て求める値が新しく加える辺の重み w であるため、合成時に求めるべき値は n * m * w である。
これを辺の数だけ繰り返す。
最終的に一つの木ができたときの値が答えになる。
def solve(n: int, weights: list[tuple[int, int, int]]) -> int:
# weights[i] = (u_i, v_i, w_i)
# 木を構成しつつ計算していく
# w_i で最小のものから順に木を構成していく
sorted_weights = sorted(weights, key=lambda x: x[2])
# UnionFind で木を構成していく
parents = list(range(n))
size = [1] * n
def find(x: int) -> int:
if parents[x] == x:
return x
parents[x] = find(parents[x])
return parents[x]
# 辺の重み * 増える2点の組み合わせの数 + 元々の木の値
rtn = 0
for u, v, w in sorted_weights:
u_root = find(u - 1)
v_root = find(v - 1)
if u_root == v_root:
continue
u_size = size[u_root]
v_size = size[v_root]
rtn += w * u_size * v_size
# 木を結合する
if u_size < v_size:
parents[u_root] = v_root
size[v_root] += u_size
size[u_root] = -1
else:
parents[v_root] = u_root
size[u_root] += v_size
size[v_root] = -1
return rtn
if __name__ == "__main__":
N = int(input())
WEIGHTS = [tuple(map(int, input().split())) for _ in range(N - 1)]
print(solve(N, WEIGHTS))
感想
「解けたあ！」と思った瞬間コンテストが終わりました……
実際は少しコーディングミスがあって、サンプルで RE があったので修正しなければなりませんでしたが、結局コンテスト終了後 1 分程度で AC できました。
F で時間を取られなければ確実に解けたと思います。
その点が非常に悔しいです。
Discussion