EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC222をpythonで解いてみた

Atcoder 競技プログラミング

目的

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

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い
  • pythonはpadding用の関数があるので便利

note.nkmk.me

実装

N = input()

print(N.zfill(4))

結果

B問題

atcoder.jp

考察

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

実装

N, P = map(int, input().split())
ans = 0

for a in list(map(int, input().split())):
    if a < P:
        ans += 1

print(ans)

結果

C問題

atcoder.jp

考察

すんなり問題文が入ってこなくて焦ったけど、普通に解けた(よかった・・・)

  • ちょっと、読むと結構難しそうだけど、N, Mが小さいので、素直に実装すればなんとかなるんじゃないかと、まず思った(C問題だし)

  • (2N)3 くらいでも、 大丈夫そうなので、効率悪くてもなんとかなるかなと

  • 素直に解くのでも、ちょっと実装に時間がかかる(Cにしてはというところだが)

  • 各ラウンドで、それぞれジャンケンし、その結果をもとに、都度sortする
    • 組み込みのsortはO(NlogN)なので、今回は O(2Nlog2N) かかる
    • sort条件が、下記の2つであるが、key別で昇順/ 降順使い分けることを考えると、面倒なので、勝利数を負の数として扱うことにした
      • i ラウンド目までの勝数が多い方が上位
      • i ラウンド目までの勝数が同じときは、番号が小さい方が上位
  • ジャンケンの結果は、愚直にIF文で書いた
    • Player1の結果として固定してみて、負けならば、Player2の勝利として考えた

実装

N, M = map(int, input().split())

A = [list(input()) for _ in range(2*N)]
result = [[i, 0] for i in range(2*N)]


def duel(hand1, hand2):
    if hand1 == hand2:
        return "drew"
    if hand1 == "G" and hand2 == "C":
        return "win"
    if hand1 == "G" and hand2 == "P":
        return "lose"
    if hand1 == "C" and hand2 == "P":
        return "win"
    if hand1 == "C" and hand2 == "G":
        return "lose"
    if hand1 == "P" and hand2 == "G":
        return "win"
    if hand1 == "P" and hand2 == "C":
        return "lose"


for j in range(M):
    for i in range(N):
        k1, k2 = 2*i, 2*i+1
        p1, p2 = result[k1][0], result[k2][0]
        hand1, hand2 = A[p1][j], A[p2][j]
        ret = duel(hand1, hand2)
        if ret == "win":
            result[k1][1] -= 1
        elif ret == "lose":
            result[k2][1] -= 1
    result.sort(key=lambda x: (x[1], x[0]))

ans = []
for i, _ in result:
    ans.append(i+1)

print(*ans, sep="\n")

結果

D問題

atcoder.jp

考察

方針はあってたが、初期化部分や更新部分でバグらせてしまったようで、焦って時間切れに

  • 広義単調増加 な数列Cを求めるので、Ai, Biの間の数を調べて、数えるだけだとできない(D問題なので当たり前だが)

  • 一つ前に取る値によって、次取れる値の範囲が変わってしまうため

  • なんとなく、DPのオーラを感じたのでDPで考えた

    • Nも3000で、A,Bも3000以下なので、O(N*max(B))くらいでもなんとかなりそう
    • Cの数列の個数をdpの値とし、以下で考えた
      • i は Cの項番号
      • j は 項の値
    • サンプルなどを机上計算していく中で、dp[i][j] は dp[i-1][0] - dp[i-1][j] までの和 であることに気づいたので、その値を保持する cnt という配列を別途用意
      • 都度計算していると、O(N*max(B)2) とかになって TLE しそうだと思ったので、jのループで同時に計算することを考えた

f:id:kazu_0716:20211010000020p:plain
ABC222 D問題メモ

実装

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

mi, ma = A[0], B[-1]
diff = ma - mi + 1
dp = [[0]*diff for _ in range(N)]
cnt = [[0]*diff for _ in range(N)]

for i in range(N):
    a, b = A[i]-mi, B[i]-mi
    for j in range(diff):
        if a <= j and j <= b:
            if i == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = cnt[i-1][j]
        if j == 0:
            cnt[i][j] = dp[i][j]
        else:
            cnt[i][j] = (cnt[i][j-1] + dp[i][j]) % MOD

print(sum(dp[-1]) % MOD)

結果

落ち着いたらすぐ解けた・・・なぜ時間内にできなかったのか・・・！！

まとめ

  • C問題で少し焦ったが、 No WA で無事緑パフォーマンス達成
    • 再度600超えを達成した

f:id:kazu_0716:20211010000945p:plain
ABC222の結果

  • ただ、今回のD問題は確実に解いておきたかったので、非常に悔いが残った

    • 特に初期化をfor文内部に持たせてしまったので、その辺で結果が思った通りに出ず、debugしてたら焦って多くの時間を使ってしまった
    • また、机上検討をしたものを、コードに落とす部分も結構遅いのかな〜と最近D埋めしていて思ったりする
    • debug力は、相変わらず低く、サンプル以外でWAだすと手も足も出なくなってしまうので、その辺も磨いていく必要がある

  • 腐らずに、D埋めを続けていくぞ！

    • だいぶ、緑以下だと解けることも多くなってきたので、手応えは感じてきている
      • 考察や、方針はそこそこできてきている
      • ただ、それを実装に落とす部分で、結構時間かかっていて、結果長い時間かけて解いている気がする
        • 実装力が低い or 考察が雑なので考えながら書いてる？ というところは明確にした上で、弱点を補強していきたい
    • が、コンテストでは結果が出てないので、その辺は辛いところ(といっても、粘り強く続ける or もう諦める の2択なのだが)

  • 今週も毎日ACできてたので、腐らず1日1AC続けていくぞ！