.lazyload-placeholder { display: none; }

作成日 : 2021-09-03
更新日 : 2021-11-01
13 min readAtCoder

【備考録】AtCoder Beginner Contest 212 A~D問題

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

そもそもAtCoderとは?
「AtCoder Beginner Contest 212」
A -> Alloy
B -> Weak Password
C -> Min Difference
D -> Querying Multiset
参考文献

目次を開く⬇︎

執筆者 - おすすめの記事3選

この記事も読まれています

.lazyload-placeholder { display: none; }

【備考録】AtCoder Beginner Contest 210 A~D問題

AtCoder Beginner Contest 210のA~D問題に関して、問題文からContest中に考えたこと、解...

この記事も読まれています

.lazyload-placeholder { display: none; }

【備考録】AtCoder Beginner Contest 211 A~D問題

AtCoder Beginner Contest 211のA~D問題に関して、問題文からContest中に考えたこと、解...

この記事も読まれています

.lazyload-placeholder { display: none; }

【備考録】AtCoder Beginner Contest 213 A~D問題

AtCoder Beginner Contest 213のA~D問題に関して、問題文からContest中に考えたこと、解...

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 212」

コンテスト情報

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

配点

問題	点数
A	100
B	200
C	300
D	400
E	500
F	500
G	600
H	600

ルール

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

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

A -> Alloy

問題文

高橋くんはAグラムの純金とBグラムの純銀(0 ≤ A, B, 0 < A + B)をよく溶かした上で混ぜ合わせ、新たな金属を生成しました。

生成された金属は「純金」「純銀」「合金」のいずれでしょうか？

なお、生成された金属は

0 < AかつB = 0なら「純金」
A = 0かつ0 < Bなら「純銀」
0 < Aかつ0 < Bなら「合金」

であるとみなします。

制約

0 ≤ A, B ≤ 100
0 < A + B
A, Bは整数

入力

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

1A B

出力

生成された金属が「純金」ならGoldと、「純銀」ならSilverと、「合金」ならAlloyと出力せよ。

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

Contest中に考えたこと

それぞれの条件分岐をif文で表現する。
それぞれの条件に対応する出力を行う。

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3
4# A = 0かつ0 < Bなら「純銀」
5if A == 0 and 0 < B:
6    print('Silver')
7# 0 < AかつB = 0なら「純金」
8elif 0 < A and B == 0:
9    print('Gold')
10# 0 < Aかつ0 < Bなら「合金」
11else:
12    print('Alloy')

B -> Weak Password

問題文

4桁の暗証番号X1 X2 X3 X4が与えられます。番号は先頭の桁が0であることもあり得ます。暗証番号は以下のいずれかの条件をみたすとき弱い暗証番号と呼ばれます。

4桁とも同じ数字である。
1 ≤ i ≤ 3をみたす任意の整数iについて、Xi + 1が、Xiの次の数字である。ただし、0 ≤ j ≤ 8についてjの次の数字はj + 1であり、9の次の数字は0である。

与えられた暗証番号が弱い暗証番号ならばWeakを、そうでないならばStrongを出力してください。

制約

0 ≤ X1, X2, X3, X4 ≤ 9
X1, X2, X3, X4は整数である。

入力

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

1X1 X2 X3 X4

出力

与えられた暗証番号が弱い暗証番号ならばWeakを、そうでないならばStrongを出力せよ。

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

Contest中に考えたこと

全て同じ番号で暗証番号が構成される場合、Weakを出力する。
最終的に暗証番号が強いかどうか判定するフラグを作成し、暗証番号の確認を行う。
9の次の数字を0にするため、% 10を利用する。

解答

1# 標準入力を受け付ける。
2s = list(input())
3
4# 全て同じ番号で暗証番号が構成される場合、Weakを出力する。
5# 重複削除参考 : https://note.nkmk.me/python-list-unique-duplicate/
6if len(list(set(s))) == 1:
7    print('Weak')
8    exit()
9
10# 直前の番号を記録する。
11frontVal = int(s[0])
12# 最終的に暗証番号が強いかどうか判定するフラグ。
13isStrong = False
14for i in range(1, len(s)):
15    # frontValが9の場合に、次の番号を0にするため % 10を行う。
16    frontVal = (frontVal + 1) % 10
17    # 暗証番号が強いと判断したら、breakする。
18    if not frontVal == int(s[i]):
19        isStrong = True
20        break
21
22if isStrong:
23    print('Strong')
24else:
25    print('Weak')

C -> Min Difference

問題文

https://atcoder.jp/contests/abc212/tasks/abc212_c

制約

1 ≤ N, M ≤ 2 × 10の5乗
1 ≤ Ai ≤ 10の9乗
1 ≤ Bi ≤ 10の9乗
入力は全て整数である。

入力

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

1N M
2A1 A2 … AN
3B1 B2 … BM

出力

答えを出力せよ。

Contest中に考えたこと

A, Bの数列に対して重複な数字を削除する。
A, Bの数列に対して、総当たり(A1とB1を比較して最小値を求める、A1とB2を比較して最小値を求める...)して答えを求める。 ⏩ 実行時間が長く、問題解決に至らなかった。
A, Bの数列をソートする。総当たり(A1とB1を比較して最小値を求める、A1とB2を比較して最小値を求める...)しながら、一つ前の最小値の結果よりも大きい値が算出された場合、後続の配列は演算しないようにした。 ⏩ Bの前から総当たり(A1とB1を比較して最小値を求める、A1とB2を比較して最小値を求める...)したので、配列の後ろの方の値が最小値となる場合に実行時間が長くなり、問題解決に至らなかった。ここで終了しました。

解答

1# 二分探索を行う関数
2def binary_search(a, b):
3    min = 0
4    max = len(b) - 1
5    while min <= max:
6        # 中央のインデックスを取得する。
7        middle = (min + max) // 2
8        if b[middle] == a:
9            min = max = middle
10            break
11        elif b[middle] < a:
12            min = middle + 1
13        else:
14            max = middle - 1
15
16    return [min, max]
17
18# 標準入力を受け付ける。
19N, M = map(int, input().split())
20
21A = list(map(int, input().split()))
22B = list(map(int, input().split()))
23
24# 重複削除を行う。
25A = list(set(A))
26B = list(set(B))
27
28# 桁の大きい値を設定する。
29INF = 1000000000000
30# Bの値の最小値、最大値を設定する。
31# 二分探索が終了しない問題を解決するため。
32# 二分探索とは? : https://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2.html
33B.append(-INF)
34B.append(INF)
35
36B.sort()
37
38ans = INF
39for i in range(0, len(A)):
40    # 二分探索を用いて、A[i]に近いBの値を探す。
41    minIdx, maxIdx = binary_search(A[i], B)
42    ans = min(ans, abs(A[i] - B[minIdx]))
43    ans = min(ans, abs(A[i] - B[maxIdx]))
44print(ans)

D -> Querying Multiset

問題文

高橋君は何も書かれていないたくさんのボールと1つの袋を持っています。最初、袋は空で、高橋君はQ回の操作を行います。それぞれの操作は以下の3種類のうちのいずれかです。

操作1 : まだ何も書かれていないボール1つに整数Xiを書き込み、袋に入れる。
操作2 : 袋に入っているすべてのボールについて、そこに書かれている数を、それにXiを加えたものに書き換える。
操作3 : 袋に入っているボールのうち書かれている数が最小のもの（複数ある場合はそのうちの1つ）を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。

1 ≤ i ≤ Qについてi回目の操作の種類Piおよび操作1, 2におけるXiの値が与えられるので、操作3において記録された数を順に出力してください。

制約

1 ≤ Q ≤ 2 × 10の5乗
1 ≤ Pi ≤ 3
1 ≤ Xi ≤ 10の9乗
入力は全て整数である。
Pi = 3であるようなiが1つ以上存在する
Pi = 3であるとき、i回目の操作の直前の時点で、袋には1つ以上のボールが入っている。

入力

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

1Q
2query1
3query2
4:
5queryQ

2行目からQ + 1行目の各queryiは次のいずれかの形で与えられる。

11 Xi

12 Xi

まず、1 ≤ Pi ≤ 3が与えられる。これは操作の種類を表す。 Pi = 1またはPi = 2ならば、その後に空白区切りでXiが与えられる。

出力

Q回の操作のうち操作の種類がPi = 3であるような各操作について、記録された数を改行区切りで出力せよ。

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

要点

Pi = 2の場合の値を別の変数に持たせておく。
Pi = 3の場合に、最小値をすぐに取り出せるように、ヒープソートさせておく。

解答

1# ヒープソートを行う関数
2# 配列を二分木として扱う。
3# 二分木とは? : https://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%9C%A8.html#:~:text=%E4%BA%8C%E5%88%86%E6%9C%A8%E3%81%A8%E3%81%AF%E3%80%81%E3%83%87%E3%83%BC%E3%82%BF,%E6%A7%8B%E9%80%A0%E3%81%AE%E6%9C%A8%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82
4# 新しく追加した値 = 子, (pos - 1) >> 1のインデックスに該当する値を親とする。
5# 親と子の値比較を行い、配列の順番を並び替える。
6# (pos - 1) >> 1を繰り返し、親を探索する。親が存在しなくなるまで、親子の値入れ替えを行う。
7def _siftdown(heap, startpos, pos):
8    newitem = heap[pos]
9    while pos > startpos:
10        parentpos = (pos - 1) >> 1
11        parent = heap[parentpos]
12        if newitem < parent:
13            heap[pos] = parent
14            pos = parentpos
15            continue
16        break
17    heap[pos] = newitem
18
19# 参考 : https://docs.python.org/ja/3/library/heapq.html
20from heapq import heappop
21
22# 標準入力を受け付ける。
23Q = int(input())
24arr = []
25offset = 0
26for i in range(0, Q):
27    s = input().split()
28    p = int(s[0])
29    if p == 1:
30        x = int(s[1])
31        # 配列に値を追加する際に、以前までのoffsetは加算されない。
32        # offsetとは? : https://wa3.i-3-i.info/word11923.html
33        arr.append(x - offset)
34        _siftdown(arr, 0, len(arr) - 1)
35    elif p == 2:
36        x = int(s[1])
37        # offsetの演算を行う。
38        offset += x
39    else:
40        # ヒープソートされた配列の最小値を取り出す。
41        # ヒープソートとは? : https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88
42        val = heappop(arr)
43        print(offset + val)