ABC331 - 大和証券
2023/12/2(土)に開催されたコンテストについての記事になります。
現在、私は入茶を目指しているため、A~Cまでの解説をしようと思います。
解説
A - Tomorrow （100）
問題文
AtCoder国の暦では、1年は1月からM月までのMヶ月からなり、どの月も1日からD日までのD日からなります。
AtCoder国の暦でy年m月d日の翌日は何年何月何日であるか求めてください。
制約
- 1000 ≤ y ≤ 9000
- 1 ≤ m ≤ M ≤ 99
- 1 ≤ d ≤ D ≤ 99
- 入力は全て整数である
入力
M D
y m d
出力
AtCoder国の暦でy年m月d日の翌日がy′年m′月d′日であるとき、y′, m, d′をこの順に空白区切りで出力せよ。
考え方
入力された日付の翌日にあたる日付を出力するという問題。
12 30
2023 12 30
例えば、上記のような入力を受け取った時、1月1日から12月30日までのカレンダーを考えます。
2023/12/30の翌日を出力するので、正しい出力は以下のようになります。
2024 1 1
私のコードは以下の通りです。
M, D = map(int, input().split())
y, m, d = map(int, input().split())
d += 1
if d > D:
m += 1
d = 1
if m > M:
y += 1
m = 1
print(y, m, d)
- まず、それぞれの入力を受け付けます
- 翌日の日付を考えるので、d の値に1を足します
- 更新した d の値が D（月の末日）を超える場合、月を跨ぐので m にも 1 を加えます
- 同様に更新した m の値が M（1年の最終月）を超える場合、年を跨ぐので y にも 1 を加えます
- 「y m d」が題意を満たす日付なので出力すればok!
B - Buy One Carton of Milk （200）
問題文
スーパーマーケットで卵のパックが売られています。
卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。
どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。
制約
- 1 ≤ N ≤ 100
- 1 ≤ S, M, L ≤ 10^4
- 入力は全て整数である
入力
N S M L
出力
答えを出力せよ。
考え方
いわゆる 全探索 の問題です！
解説から引用します。
必要な卵の個数が高々 100 個であることから、どのパックも高々 100 個買えば十分です。よって、各パックを買う個数を 0 から 100 まで全探索することでこの問題を解くことができます。
解説に載っている解答例は以下の通りでした。
N, S, M, L = map(int,input().split())
ans = 10**8
for a in range(101):
for b in range(101):
for c in range(101):
if a*6 + b*8 + c*12 >= N:
ans = min(ans, a*S + b*M + c*L)
print(ans)
- 入力を受け取ります
- 出利用の変数（ans）を用意して、適当に大きい値を代入します
- ループを重ねて、各パックの購入数の全通り（各0~100個）に対して、購入する卵の合計個数がNの値を超える（必要個数を買うことが出来る）かどうか比較します
- 3のループの中で、Nの値を超える場合に、「支払い金額」と「現時点で題意を満たす最低金額（ans）」を比較して、小さい方をansに代入します
- 多重ループを抜けた後、全通り試した結果の ans を出力すればOK!
この全探索と呼ばれる考え方は、ABC の B問題で鉄板ネタらしいので覚えておきましょう。
例）
16 120 150 200
例えば、卵を16個以上買うのに最も安い買い方は8個入りを2つ買う場合なので、150円 * 2 で 300 を出力することになります。
300
問題を最初に見た時、6個→8個→12個の順番で割高になると考えて、L→M→Sの順にいくつずつ買えるかと考えていたのですが、そんな定義付けは問題文中で行われておらず、Lを1つ買うよりもSを2使う方がお得なんてケースも考えなくてはいけませんでした（サンプルケースの2つ目など）。
少し改良
解説通りの解き方で問題ありませんが、もう少し効率的な方法を考えてみます。制約の Nが1以上100以下 という点に注目します。
この制約を踏まえて、各パックの購入可能な範囲を具体的に計算してみましょう：
- Sパック（6個入り）: 100個の卵を購入するために必要なSパックの最大数は、100を6で割った時の商（16）に1を加えた数です。1を加えるのは、16パックでは96個しか購入できないためです。従って、Sパックの購入範囲は 0～17 となります。
- Mパック（8個入り）: 同様に、Mパックの購入範囲は 0～13 です。
- Lパック（12個入り）: 同様に、Lパックの購入範囲は 0～9 です。
これらの範囲に合わせて、全探索の範囲を狭めることによって実行時間を短縮することができます。
N, S, M, L = map(int,input().split())
ans = 10**8
for a in range(18):
for b in range(14):
for c in range(10):
if a*6 + b*8 + c*12 >= N:
ans = min(ans, a*S + b*M + c*L)
print(ans)
min関数 も使用する機会が多いので、忘れずに覚えておきます。
C - Sum of Numbers Greater Than Me （300）
問題文
長さ N の数列 A=(A1,…,AN) が与えられます。
i = 1,…,N のそれぞれについて次の問題を解いてください。
問題：A の要素のうち Ai より大きな要素全ての和を求めよ。
制約
- 1 ≤ N ≤ 2×10^5
- 1 ≤ Ai ≤10^6
- 入力は全て整数である
入力
N
A1 … AN
出力
各1 ≤ k ≤ N について、i=k に対する問題の答えを Bk とする。
B1,…,BN をこの順に空白区切りで出力せよ。
入出力サンプル
5
1 4 1 4 2
10 0 10 0 8
A[1]の時、1より大きい値の合計値は 4+4+2=10 となります。
考え方
結果から書くと、TLE（実行時間エラー）が解消できずにコンテストが終わってしまいました。。。
どう間違えたか
私の書いたコードは以下の通りです。
n = int(input())
A = list(map(int, input().split()))
B = sorted(A, reverse=True)
for i in range(n):
sum = 0
for j in range(n):
if A[i] < B[j]:
sum += B[j]
else:
break
A[i] = sum
print(*A)
- 入力を受けたら、リストAの要素を値の大きい順にソートしたリストBを作成します
- リストAの各要素に対して、リストBの値と比較してA[i]がB[j]より小さいところまでは値を足していき、B[j]以上になったらループを抜け、そこまでのsumをA[i]に代入します。
- リストAの全ての要素に対して処理を繰り返し、最後に更新されたリストAの要素を出力します
このプログラムは二重ループを使用しており、計算量が大体 O(N^2) になるため、実行時間エラー（TLE）になります。そのため、重ねるループの数を減らす必要があります。その解決策の1つとして、辞書 を利用して各要素の 累積和 を計算する方法があります。各要素の累積和を辞書に保存、参照することで計算量を O(N log N) と、実行時間を大幅に短縮することが出来ます。
n = int(input())
A = list(map(int, input().split()))
d = {}
sum = 0
for a in sorted(A, reverse=True):
if a not in d:
d[a] = sum
sum += a
for a in A:
print(d[a], end=' ')
- 入力を受けます
- 空の辞書 d と、累積和の計算に用いる変数 sum を作成します
- リスト A を降順にソートして各要素 a に対して、a が初めて出てくる値であれば、a をキーとして現在の sum の値を辞書に追加します
- 出来上がった辞書を用いて、A[i]毎に対応する辞書 d の値（累積和）を空白区切りで出力します
また、コードを提出する際の言語では PyPy を選択しましょう。Pythonコードの提出には複数選択肢がありますが、基本的にPyPyでの実行が速いためです。
修正後の実行時間は、CPythonを使用すると253ms、PyPyを使用すると179msと、74ms 短かったです。（CPythonでも制限時間内に解き終わります）
最後に
今回は、ABC331のA~C問題について書きました。
最後まで読んでいただき、ありがとうございます。
復習に時間かけすぎかなと思いつつ、まずは丁寧に理解していこうと思います。
また別のコンテストにも挑戦していくので、応援よろしくお願いします。