作成日 : 2021-09-05
更新日 : 2021-11-01
12 min readAtCoder

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 217」

コンテスト情報

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

配点

ルール

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

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

A -> Lexicographic Order

問題文

相異なる二つの文字列S, Tが与えられます。SがTよりも辞書順で小さい場合はYesを、大きい場合はNoを出力してください。

辞書順とは? : 辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列Sと文字列Tの大小を判定するアルゴリズムを以下に説明します。以下では「Sのi文字目の文字」をSiのように表します。また、 SがTより辞書順で小さい場合はS < T、大きい場合はS > Tと表します。SとTのうち長さが短い方の文字列の長さをLとします。i = 1, 2, …, Lに対してSiとTiが一致するか調べます。Si ≠ Tiであるiが存在する場合、そのようなiのうち最小のものをjとします。そして、SjとTjを比較して、 Sjがアルファベット順でTjより小さい場合は S < T 、大きい場合はS > Tと決定して、アルゴリズムを終了します。Si ≠ Tiであるiが存在しない場合、SとTの長さを比較して、SがTより短い場合は S < T 、長い場合はS > Tと決定して、アルゴリズムを終了します。

なお、主要なプログラミング言語の多くでは、文字列の辞書順による比較は標準ライブラリに含まれる関数や演算子として実装されています。詳しくは各言語のリファレンスをご参照ください。

制約

• S, Tは英小文字からなる長さ1以上10以下の相異なる文字列である。

入力

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

1S T

出力

SがTより辞書順で小さい場合はYesを、大きい場合はNoを出力せよ。

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

Contest中に考えたこと

• S, Tの文字を比較してS < Tの時Yes、S >= Tの時Noとする。

解答

1# 標準入力を受け付ける。
2S, T = input().split()
3
4if S < T:
5    print('Yes')
6else:
7    print('No')

B -> AtCoder Quiz

問題文

AtCoderでは現在、ABC, ARC, AGC, AHCの4つのコンテストが定期的に開催されています。AtCoderで現在定期的に開催されているコンテストはS1, S2, S3とあと1つは何ですか?

制約

• S1, S2, S3はそれぞれ、ABC, ARC, AGC, AHCのいずれかである。
• S1, S2, S3は相異なる。

入力

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

1S1
2S2
3S3

出力

答えを出力せよ。

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

Contest中に考えたこと

• 予め、ABC, ARC, AGC, AHCの値をリストへ格納する。
• S1, S2, S3が入力される度に、上記で作成したリストと合致する値を削除する。

解答

1# 予め、ABC, ARC, AGC, AHCの値をリストへ格納する。
2atcoderList = [
3    'ABC',
4    'ARC',
5    'AGC',
6    'AHC',
7]
8 
9# 標準入力を受け付ける。
10s1 = input()
11s2 = input()
12s3 = input()
13 
14# S1, S2, S3が入力される度に、上記で作成したリストと合致する値を削除する。
15# remove関数参考 : https://note.nkmk.me/python-list-clear-pop-remove-del/
16atcoderList.remove(s1)
17atcoderList.remove(s2)
18atcoderList.remove(s3)
19 
20print(atcoderList[0])

C -> Inverse of Permutation

問題文

1, 2, …, Nが1回ずつ現れる長さNの数列を「長さNの順列」と呼びます。長さNの順列P=(p1, p2, …, pN)が与えられるので、以下の条件を満たす長さNの順列Q=(q1, …, qN)を出力してください。

• 全てのi(1 ≤ i ≤ N)に対してQのpi番目の要素がiである。

ただし、条件を満たすQは必ずただ1つ存在することが証明できます。

制約

• 1 ≤ N ≤ 2 × 10の5乗
• (p1, p2, …, pN)は長さNの順列である。
• 入力は全て整数である。

入力

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

1N
2p1 p2 … pN

出力

数列Qを空白区切りで1行で出力せよ。

1q1 q2 … qN

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

Contest中に考えたこと

• 順列Qを作成するために、pi番目とiの関係を紐づける。
• piをソートして、Qを出力する。

解答

1# 標準入力を受け付ける。
2N = int(input())
3P = list(map(int, input().split()))
4 
5Qinfo = []
6for i in range(0, N):
7    # 順列Qを作成するために、pi番目とiの関係を紐づける。
8    Qinfo.append({
9        'index': P[i],
10        'position': i + 1,
11    })
12 
13# piをソートする。
14# key optionについて : https://note.nkmk.me/python-key-sort-sorted-max-min/
15Qinfo = sorted(Qinfo, key=lambda x:x['index'])
16 
17ans = ''
18# Qを出力する。
19for i in range(0, N):
20    ans += str(Qinfo[i]['position']) + ' '
21 
22print(ans)

D -> Cutting Woods

問題文

長さLメートルの直線状の木材があります。x = 1, 2, …, L − 1に対して、木材の左端からxメートルの地点には目印として線xが引かれています。

Q個のクエリが与えられます。i番目のクエリは数の組(ci, xi)によって表されます。

以下の説明に従ってクエリをiの昇順に処理してください。

• ci = 1のとき : 線xiがある地点で木材を2つに切る。
• ci = 2のとき : 線xiを含む木材を選び、その長さを出力する。

ただしci =1, 2の両方に対して、線xiはクエリを処理する時点で切られていないことが保証されます。

制約

• 1 ≤ L ≤ 10の9乗
• 1 ≤ Q ≤ 2 × 10の5乗
• ci =1, 2(1 ≤ i ≤ Q)
• 1 ≤ xi ≤ L − 1(1 ≤ i ≤ Q)
• 全てのi(1 ≤ i ≤ Q)に対して次が成り立つ : 1 ≤ j < iかつ(cj, xj​) = (1, xi)を満たすjは存在しない。
• 入力は全て整数である。

入力

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

1L Q
2c1 x1
3c2 x2
4​⋮
5cQ xQ

出力

ci = 2を満たすクエリの回数と等しい行数だけ出力せよ。j行目ではj番目のそのようなクエリに対する答えを出力せよ。

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

Contest中に考えたこと

• 木材の目印線を配列で管理する。
• xiに一番近い目印線を2つ探索する。 ⏩ 探索して見つけた目印線2つを引き算して、木材の長さを洗い出す。
• xiに一番近い目印線を2つ探索する = 配列がソートされていて、xiの両隣にある値を探し出すことを意味する。 ⏩ 二分探索を利用する。
• 二分探索を利用して実装したが、配列のメモリ関係のことや、ソートの利用回数が多い等の理由で、TLEの結果が続いて、コンテストが終了した。

解答

1# arrayについて : https://docs.python.org/ja/3/library/array.html
2import array
3import bisect
4
5# 二分探索を行う関数
6def binary_search(a, b):
7    min = 0
8    max = len(b) - 1
9    while min <= max:
10        # 中央のインデックスを取得する。
11        middle = (min + max) // 2
12        if b[middle] == a:
13            min = max = middle
14            break
15        elif b[middle] < a:
16            min = middle + 1
17        else:
18            max = middle - 1
19    return [min, max]
20
21# 標準入力を受け付ける。
22L, Q = map(int, input().split())
23
24# メモリの使用量を抑えるために、一次元配列のみ & 型制限されるarrayを利用する。
25# 参考 : https://note.nkmk.me/python-list-array-numpy-ndarray/
26arr = array.array("i", [0, L])
27
28for _ in range(Q):
29    # 標準入力を受け付ける。
30    c, x = map(int, input().split())
31    if c == 1:
32        # xから一番近いarrの値 < x < xから一番近いarrの値になるように、xを格納する。
33        # bisect.insortについて : https://docs.python.org/ja/3/library/bisect.html#bisect.insort
34        bisect.insort(arr, x)
35    elif c == 2:
36        # 二分探索を利用して、xに近いarr(配列)のインデックス値を取得する。
37        # 二分探索とは? : https://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2.html#:~:text=%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%81%A8%E3%81%AF%E3%80%81%E3%83%87%E3%83%BC%E3%82%BF,%E3%81%AB%E6%8E%A2%E7%B4%A2%E3%82%92%E8%A1%8C%E3%81%86%E6%89%8B%E6%B3%95%E3%80%82
38        minIdx, maxIdx = binary_search(x, arr)
39        print(max(arr[minIdx] - arr[maxIdx], arr[maxIdx] - arr[minIdx]))

2021年9月4日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• 順列とは?
• 昇順とは?
• 二分探索とは?
• Atcoder 217に関するコードまとめ