Atcoder-ABC220をpythonで解いてみた

目的

今回私用により、30分程度遅れて開始した

• Atcoderで上を目指すべく頑張っている中でABC220を解いたので、解説してみる
  • pypy7.3を使って解いている

A問題

atcoder.jp

考察

• 問題文通りに解けば良い

実装

A, B, C = map(int, input().split())

ans = 0
for c in range(0, B+1, C):
    if c >= A:
        ans = c
        break

if ans == 0:
    print(-1)
else:
    print(ans)

結果

• 無事に解けた

B問題

atcoder.jp

考察

• 問題文通りに解けば良い
• n進法への変換はこの辺見てもらえると(数Aの範囲であったことに驚いたw)

math.nakaken88.com

実装

K = int(input())
A, B = map(int, (input().split()))


def convert(n, k):
    result, cnt = 0, 0
    for i in list(str(n))[::-1]:
        result += int(i) * pow(k, cnt)
        cnt += 1
    return result


print(convert(A, K)*convert(B, K))

結果

• 無事に解けた

C問題

atcoder.jp

考察

前回同様爆死しかけて、焦ってWA出しまくり、大きく時間とパフォーマンスを無駄にしてしまった・・・

• XをAのsumで割り、余りを用いて、何項目まで用いるか考える 　- Aの累積和を作成しておき、二分探索で、余りがどこになるかを考えれば良いと考えた

が、どうしてもWAが取れず・・・

• 無闇に提出し、WAを連発してしまった

  • 余りや割った数の場合分けの問題かと思ったが、よく検証したら最初でそこはクリアできてた

• そもそも、bisectでのidxで何かモレや勘違いがあると思い、方針を変えた

  • 結果、原因は分かっていないが解くことができた(O(N)でも十分解けることは机上計算済みだったが・・・)
    • 前回同様、変なこだわりでいたずらに時間とWAを浪費することに・・・

実装

from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))
X = int(input())

cum = list(accumulate(A))
cum.sort()
s = cum[-1]

q, mod = divmod(X, s)
cnt = 0
for i in range(N):
    cnt += 1
    if mod < cum[i]:
        break

print(N*q+cnt)

結果

• 無事に解けた

D問題

atcoder.jp

考察

実装方針はあっていたが、時間足らず焦りもあり解けず

• 一番左にある数に着目する
• i番目の数列を扱った際に、どうなるのか考える
  • F(最も左の2数を足した、一の位の値を最も左の数とする)でDPを遷移させる
  • G(最も左の2数を掛けた、一の位の値を最も左の数とする)でDPを遷移させる
• DPを考えたときに、一つ前の処理のでの一番左の数それぞれで、F,Gの処理をしていく
  • MODでの処理も忘れずに

ABC220 Dメモ

実装

N = int(input())
A = list(map(int, input().split()))
MOD = 998244353

dp = [[0]*10 for _ in range(N)]
dp[0][A[0]] = 1


for i in range(1, N):
    for j in range(10):
        f = (j + A[i]) % 10
        g = (j * A[i]) % 10
        dp[i][f] = (dp[i][f] + dp[i-1][j]) % MOD
        dp[i][g] = (dp[i][g] + dp[i-1][j]) % MOD

print(*dp[-1], sep="\n")

結果

解説見ずに無事に解けた

• 無事に解けた

まとめ

• 前回同様、C問題で大こけし、大きくレートを落としてしまった・・・
  • 二回続くと辛いし、ここ二回で100近くレートが下がってしまった・・・

ABC220の結果

• 課題がいくつか分かった

  • C問題でも、苦手が来たり、焦ってたりすると途端に解けない
    • 基礎力不足の課題
    • 困難にぶつかったときになんともならない現状
      • WAが数個取れない際での、debug力不足(sample以外のテスト用のデータを用意するなどが、コンテスト内でできていない)
  • 今回、遅れての参戦になったが、こういう時は素直に出るのを諦めた方が良さそう・・・
    • 時間ない中焦るとろくなことがない
    • 前回のCが解けず・・・があり、WAを繰り返し、結果前回以下のパフォーマンスとなってしまった

• Educational DPの効果はある

  • 実際あと2分程度あれば、Dも解けていた
  • パフォーマンスやレートが下がっても、競プロ力が落ちたわけではないので、腐らず続けていく