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

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

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

そもそもAtCoderとは?

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

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

「AtCoder Beginner Contest 221」

コンテスト情報

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

配点

ルール

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

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

A -> Seismic magnitude scales

問題文

地震のマグニチュードは、その地震のエネルギーの大きさを対数で表した値です。マグニチュードが1増える度にエネルギーは約32倍になることが知られています。

ここではマグニチュードが1増える度に地震のエネルギーがちょうど32倍になるとします。このとき、マグニチュードAの地震のエネルギーの大きさはマグニチュードBの地震のエネルギーの大きさの何倍ですか?

制約

• 3 ≤ B ≤ A ≤ 9
• A, Bは整数

入力

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

1A B

出力

答えを整数で出力せよ。

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

Contest中に考えたこと

• BがAよりも大きくならないことを理解する。 ⏩ A - Bがマイナスにならないことを確認する。
• 32の(A - B)乗を演算する。(A - Bが0の場合も32の0乗 = 1になるので問題なし。)

解答

1# 標準入力を受け付ける。
2A, B = map(int, input().split())
3
4# 32の(A - B)乗を演算する。(A - Bが0の場合も32の0乗 = 1になるので問題なし。) 
5print(32 ** (A - B))

B -> typo

問題文

文字列S, Tが与えられます。以下の操作を高々1回行うことで、SをTと一致させることができるかを判定してください。

• Sの隣り合う2文字を選び、入れ替える。

なお、上記の操作を一度も行わないことも可能です。

制約

• S, Tはそれぞれ英小文字のみからなる、長さ2以上100以下の文字列
• Sの長さとTの長さは等しい

入力

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

1S
2T

出力

問題文中の操作を高々1回行うことでSをTと一致させることができるならYesを、できないならNoを出力せよ。

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

Contest中に考えたこと

• Sの長さとTの長さは等しい ⏩ Sの長さ != Tの長さの場合を考えなくて良い。
• Sを操作することなく、S = Tになる場合は、即座にYesを出力する。
• S[0]とS[1]を入れ替え、S[1]とS[2]を入れ替え、S[2]とS[3]を入れ替え、、、の場合を検証する。
• 入れ替えた場合にS = Tになるか検証する。
• 入れ替えてS = Tを検証した後は、一度元のSに戻すことを忘れない。
• Sの最大の長さが100であるため、ループ回数の大きさを気にする必要はない。

解答

1# 標準入力を受け付ける。
2S = input()
3T = input()
4 
5# Sを操作することなく、S = Tになる場合は、即座にYesを出力する。
6if S == T:
7    print('Yes')
8    exit()
9 
10S = list(S)
11for i in range(len(S) - 1):
12    # S[0]とS[1]を入れ替え、S[1]とS[2]を入れ替え、S[2]とS[3]を入れ替え、、、の場合を検証する。
13    tmp = S[i + 1]
14    S[i + 1] = S[i]
15    S[i] = tmp
16 
17    # 入れ替えた場合にS = Tになるか検証する。
18    if ''.join(S) == T:
19        print('Yes')
20        exit()
21    
22    # 入れ替えてS = Tを検証した後は、一度元のSに戻すことを忘れない。
23    tmp = S[i + 1]
24    S[i + 1] = S[i]
25    S[i] = tmp
26 
27print('No')

C -> Select Mul

問題文

整数Nが与えられます。Nの各桁の数字を取り出して並べ（並べる順序は好きに変えてよい）、2つの正整数に分離することを考えましょう。

例えば、123という整数に対しては以下の6通りの分離の仕方が考えられます。

• 12と3
• 21と3
• 13と2
• 31と2
• 23と1
• 32と1

なお、ここで分離されたあとの2整数にleading zeroが含まれていてはなりません。例えば、101という整数を1と01の2つに分離することはできません。また上述の「正整数に分離する」という条件より、101を11と0の2つに分離することもできません。

適切にNを分離したとき、分離後の2数の積の最大値はいくらになりますか？

制約

• Nは1以上10の9乗以下の整数
• Nには0でない桁が2つ以上含まれる

入力

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

1N

出力

分離後の2数の積の最大値を出力せよ。

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

Contest中に考えたこと

• 2整数に分離した時に、左の桁の数字が大きい方が最大値に近づく = 数字の順序は関係ないので降順にソートしておく。
• 2整数に分離する場合を全通り探索しても、うまく行かないと思ってしまった。。ここで終了しました。 ⏩Nの最大数 = 1000000000である。bit全探索を利用して全通り探索する場合、2のN乗かかるので、2の10乗で済む。(1024ループ x Nの長さ)くらいで処理が完了するので、bit全探索で実装すべきだった。

解答

1# 標準入力を受け付ける。
2N = input()
3
4N = list(N)
5
6ans = 0
7# bit全探索を行う。計算量 : 2のN乗
8for i in range(2 ** len(N)):
9    a = []
10    b = []
11    # bitをjの値ぶん右シフトさせて、1であるbitを探す。
12    for j in range(len(N)):
13        if i >> j & 1:
14            a.append(N[j])
15        else:
16            b.append(N[j])
17    # aが[] or bが[] ⏩ 片方が正整数になっていないため、後続処理を行うことなく、continueする。
18    if a == [] or b == []:
19        continue
20
21    # 選んだ数字の中で最大値になるのは、左の桁へ大きい数字がくる場合なので、降順ソートを行う。
22    a.sort(reverse=True)
23    b.sort(reverse=True)
24
25    ans = max(ans, int(''.join(a)) * int(''.join(b)))
26
27print(ans)

D -> Online games

問題文

あるオンラインゲームがあり、N人のプレイヤーが登録しています。サービス開始日から10の100乗日を迎えた今日、 開発者である高橋君がログイン履歴を調べたところ、i番目のプレイヤーはサービス開始日を1日目として、Ai日目からBi日間連続でログインし、 それ以外の日はログインしていなかったことが判明しました。 すなわち、i番目のプレイヤーはサービス開始日から、Ai, Ai + 1, … , Ai + Bi − 1日目に、かつそれらの日にのみログインしていたことが分かりました。

1 ≤ k ≤ Nをみたす各整数kについて、 サービス開始日から今日までの間で、ちょうどk人がログインしていた日数を答えてください。

制約

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

入力

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

1N
2A1 B1
3A2 B2
4:
5AN BN​

出力

次のように空白区切りでN個の整数を出力せよ。

1D1 D2 ⋯ DN

ただし、 Diはちょうどi人がゲームにログインしていた日数を表す。

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

解答

1# 標準入力を受け付ける。
2N = int(input())
3
4# 0~N人ログインしていたユーザーの日数を格納する。
5ans = [0] * (N + 1)
6query = []
7for _ in range(N):
8    A, B = map(int, input().split())
9    # ログイン開始日を記録する。
10    start = A
11    # ログイン終了日を記録する。
12    end = A + B
13    query.append((start, 1))
14    query.append((end, -1))
15
16# ログイン開始日 or ログイン終了日を基準にしてソートする。
17query.sort()
18
19loginNum = 0
20# ひとつ前のログイン日開始日 or ログイン終了日を格納する。
21last = -1
22
23for (A, B) in query:
24    # queryの内容が重複していても問題ない。日付間隔がないため。
25    ans[loginNum] += A - last
26    last = A
27    loginNum += B
28
29for i in range(1, N + 1):
30    print(str(ans[i]) + ' ', end='')

2021年10月2日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• 対数とは?
• AtCoder株式会社について
• 高々とは?
• bit全探索とは?
• 降順とは?
• Atcoder 221に関するコードまとめ