作成日 : 2021-08-15
更新日 : 2021-11-01
13 min readAtCoder

【備忘録】AtCoder Beginner Contest 214 A~D問題

AtCoder Beginner Contest 214のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。

そもそもAtCoderとは?

AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。

今回は 「AtCoder Beginner Contest 214」のプログラミングコンテストへ参加しました。

「AtCoder Beginner Contest 214」

コンテスト情報

• コンテスト時間 : 100分
• レーティング更新対象 : 0 - 1999

配点

ルール

1. コンテスト中に問題に正解すると点数を獲得できます。
2. 順位は総合得点で決定します。
3. 同点の場合は提出時間の早い人が上の順位になります。
4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)

このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。

A -> New Generation ABC

問題文

AtCoder Beginner Contestは、今回で214回目の開催となりました。

今までの AtCoder Beginner Contestにおいて、出題される問題数は次のように変化しました。

• 1回目から125回目までは4問
• 126回目から211回目までは6問
• 212回目から214回目までは8問

N回目のAtCoder Beginner Contestにおいて出題された問題数を求めてください。

制約

• 1 ≤ N ≤ 214
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

1N

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、A - New Generation ABC問題を参照しております。

Contest中に考えたこと

• if文を利用して、N回目のコンテストに対応する、問題数を出力すればうまくいきそう

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# 1回目から125回目までの場合4を出力する。
5if N >= 1 and N <= 125:
6    print(4)
7# 126回目から211回目までの場合6を出力する。
8elif N >= 126 and N <= 211:
9    print(6)
10# 212回目から214回目までの場合8を出力する。
11else:
12    print(8)

B -> How many?

問題文

a + b + c ≤ S かつ a × b × c ≤ Tを満たす非負整数の組(a, b, c)はいくつありますか？

制約

• 0 ≤ S ≤ 100
• 0 ≤ T ≤ 10000
• S, Tは整数である。

入力

入力は以下の形式で標準入力から与えられる。

1S T

出力

条件を満たす非負整数の組(a, b, c)の個数を出力せよ。

本問題は、AtCoder株式会社で作成された、B - How many?問題を参照しております。

Contest中に考えたこと

• まず非負整数の意味を調べました。こちらの記事を参考にし、非負整数 = 0以上の整数であることを理解しました。
• a, b, cの組み合わせを、総当たりして問題が解けるのか考えました。a + b + c ≤ Sを満たすとき、a, b, cの最大値はS(a + 0 + 0 <= S)になること、a x b x c ≤ Tを満たすとき、a, b, cの最大値はT(a x 1 x 1 <= T)になる(考え方を間違えていた。a, b, cの最大値は無限大になる。なぜならa, b, cに0が入りうるから)と考えて、S < Tの時、T回総当たりする、反対に S >= Tの時、S回総当たりするコードを書きました。TLEやREが発生しました。
• 次にa + b + c ≤ S かつ a × b × c ≤ Tに該当する、(a, b, c)の組みあわせの増え方に、規則性がないか考え、アルゴリズムに落とし込めないか試行した。S=0の時、1通り、S=1の時、4通り、S=2の時、10通り、S=3の時、20通り、S=4の時、35通り、、、とa + b + c ≤ Sに関しては、規則的に増えていると感じたが、a × b × c ≤ Tの時、a, b, cのどれかに0を入れると、あとはなんの値を入れてもよくなるので、規則性はないと感じた。ここで終了しました。

解答

1# 標準入力を受け付ける。
2S, T = (int(x) for x in input().split())
3
4# 組み合わせの数を格納する。
5count = 0
6# <方針>
7# aの値を総当たりして、a + b + c <= Sの条件に当てはまるb, cの値の幅を決める。(b : S - a), (c : S - a - b)
8for a in range(0, S + 1):
9    for b in range(0, S - a + 1):
10        for c in range(0, S - a - b + 1):
11            # a, b, cに当てはまる値は、a + b + c <= Sに該当する値のみなので、a * b * c <= Tをcountすればいい。
12            if a * b * c <= T:
13                count = count + 1
14print(count)

C -> Distribution

問題文

N人のすぬけ君が円周上に並んでおり、反時計回りに1, 2, ..., Nの番号がついています。i(1 ≤ i ≤ N)番目のすぬけ君は時刻tに宝石をもらうとSi単位時間後、すなわち時刻t + Siにその宝石を(i + 1)番目のすぬけ君に渡します。ただし、(N + 1)番目のすぬけ君とは1番目のすぬけ君のことを指すとします。

また、高橋君は時刻Tiにi番目のすぬけ君に宝石を渡します。全てのi(1 ≤ i ≤ N)について、i番目のすぬけ君が初めて宝石をもらう時刻を求めてください。

なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

• 1 ≤ N ≤ 200000
• 1 ≤ Si, Ti ≤ 10の9乗
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

1N
2S1 S2 … SN
3T1 T2 … TN

出力

N行出力せよ。i(1 ≤ i ≤ N)行目には、i番目のすぬけ君が初めて宝石をもらう時刻を出力すること。

本問題は、AtCoder株式会社で作成された、C - Distribution問題を参照しております。

要点

• すぬけくんが宝石を始めてもらう方法は2通り。隣のすぬけくんから受け取るか、高橋くんから直接受け取るか。 → どちらの宝石の受け取りが早いか、計算すると良い。
• すぬけくんは宝石を渡すことしかできない。 → はじめに高橋くんから直接宝石を受け取るところからスタートする。

解答

1# 標準入力を受け付ける。
2N = int(input())
3S = list(map(int, input().split()))
4T = list(map(int, input().split()))
5
6# 最初に高橋くんからすぬけくんへ宝石を渡した最小時間を見つける。宝石の授受がここから始まる。
7minIdx = 0
8for i in range(0, N):
9    if T[i] <= T[minIdx]:
10        minIdx = i
11
12# 最小時間を格納しておく。
13currentTime = T[minIdx]
14# 答えリスト。
15ans = [0] * N
16
17for i in range(0, N):
18    # 現在時間 + すぬけくんから隣のすぬけくんへ宝石を渡す時間 = 始めて宝石をもらう時間にすべきか、それとも高橋くんから直接宝石をもらう時間 = 始めて宝石をもらう時間にすべきか、最小時間で高橋くんから直接宝石をもらった、すぬけくんのところから検証を始める。
19    # % N : minIdxが0から始まるとは限らない。1周して1番目のすぬけくんに戻ることを加味する。
20    nowIdx = (minIdx + i) % N
21
22    # 宝石をすぬけくんからもらった時間にすべきか、それとも高橋くんからもらった時間にすべきか判定する。
23    currentTime = min(currentTime, T[nowIdx])
24
25    # i番目の時間を記録しておく。
26    ans[nowIdx] = currentTime
27
28    # すぬけくんから宝石をもらった場合の時刻を記録しておく。
29    currentTime += S[nowIdx]
30
31# 答え出力
32print(*ans)

D -> Sum of Maximum Weights

問題文

https://atcoder.jp/contests/abc214/tasks/abc214_d

制約

• 2 ≤ N ≤ 10の5乗
• 1 ≤ ui, vi ≤ N
• 1 ≤ wi ≤ 10の7乗
• 与えられるグラフは木である。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

1N
2u1 v1 w1
3⋮
4uN −1 vN−1 wN−1

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、D - Sum of Maximum Weights問題を参照しております。

要点

• 与えられるグラフは木である。 → 各頂点は必ずどこかと繋がっていて、親子関係を形成している。
• 頂点から頂点へ全ての通る辺に関して、一番大きい重みを足し合わせる。(二重総和について)
• 一番小さな重みで繋がっている頂点どおしから演算する。( 「現在参照する重みの最大値 x 現在参照する重みの最大値が、最大値になる通りの数」で演算できるようにするため)
• 重みの計算を完了したら、頂点どおしのつなぎ合わせを行う。

解答

1import sys
2
3# 再起の上限を設定するために利用する。
4# 参考 : https://note.nkmk.me/python-sys-recursionlimit/
5sys.setrecursionlimit(10**6)
6
7# 標準入力を受け付ける。
8n = int(input())
9
10edges = []
11for _ in range(n - 1):
12    u, v, w = map(int, input().split())
13    # 配列のインデックスが0から始めることを加味して、-1する。
14    # インデックスとは? : https://wa3.i-3-i.info/word11906.html
15    u -= 1
16    v -= 1
17    edges.append((w, u, v))
18
19# 重みの小さい順に並べる。
20# 「現在参照する重みの最大値 x 現在参照する重みの最大値が、最大値になる通りの数」を実現するため。
21edges.sort()
22
23# 親のインデックスを探索する関数
24# 親のインデックスを見つけるまで再起処理を行う。
25# 親のインデックスが見つかったら、再起が終了するまで、同じ値(親のインデックス値)を保持させ続ける。
26def root(x):
27    if parent[x] < 0:
28        return x
29    else:
30        parent[x] = root(parent[x])
31        return parent[x]
32
33# 頂点を繋ぎ合わせる処理。
34# 親を洗い出して、子と繋ぎ合わせる。
35def unite(x, y):
36    x = root(x)
37    y = root(y)
38    parent[x] += parent[y]
39    parent[y] = x
40
41# 頂点に該当する親の値を返す。
42def size(x):
43    x = root(x)
44    return -parent[x]
45
46# 各頂点の親情報を格納する。親は-1とする。
47parent = [-1] * n
48# 答えを格納する変数
49ans = 0
50
51for w, u, v in edges:
52    ans += w * size(u) * size(v)
53    unite(u, v)
54
55print(ans)

2021年8月14日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• 非負整数とは?
• 総当たりとは?
• TLE, REとは?
• 親子関係とは?
• Python再起の上限設定方法
• インデックスとは?
• 二重総和について
• catupperさん動画
• Atcoder 214に関するコードまとめ