RONの技術ブログ

駆け出しエンジニアの備忘録

【AtCoder】ABC203 感想戦

2021/5/30に開催されたABC203を振り返ります。
結果はA~Cの3完でした。
順位:1997位、パフォーマンス:1087、レート:694→742(茶)

  • A問題:A - Chinchirorin
    3つサイコロを振って、2つが同じときは残りの1つのサイコロの目を、同じものがないときは0を出力する問題です。
    スマートな解き方があるかと思い、少し考えましたが結局全パターンチェックに落ち着きました。
def main():
    a, b, c = map(int,input().split())

    if a == b:
        return c
    elif a == c:
        return b
    elif b == c:
        return a
    else:
        return 0

print(main())
  • B問題:B - AtCoder Condominium
    マンションの部屋番号の総和を求める問題です。
    このマンションはN階建てで、各階K室の部屋があり、i階のj号室の部屋番号はi0jで表されます。
    部屋番号はi * 100 + jで求められるので、部屋毎に足していけば良いです。
def main():
    N, K = map(int,input().split())
    ans = 0

    for n in range(1,N+1):
        for k in range(1, K+1):
            room = n * 100 + k
            ans += room
    
    return ans

print(main())
  • C問題:C - Friends and Travel costs
    10100 + 1個の村があり、村i → 村i+1に移動するのに1円かかります。
    友達がいる村にたどり着いた場合、その友達からお金をもらうことができます。
    この条件でどこの村までたどり着けるか求める問題です。
    方針としては、友達がいる一番近い村までたどり着けるかどうか検証しながら所持金を管理してどこまで進めるかを調べました。
def main():
    N, K = map(int,input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    AB.sort()
    mura = 0

    for a, b in AB:
        dist = a - mura
        if dist > K:
            return mura + K
        else:
            mura += dist
            K += b - dist
    
    return mura + K

print(main())
  • D問題:D - Pond
    制約条件的に二分探索かな?と頭によぎりましたが、全く手が動きませんでした。
    この問題は2次元配列での累積和を求めるやり方を学びました。
    こういうテクニックは知らないと使えないですね。
    やっぱりまだDの壁は厚いな〜と実感しました。
def main():
    N, K = map(int,input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    S = [[0]*801 for _ in range(801)]

    ng = 0
    ok = 10**9 + 1

    lim = int(K*K/2 + 1)

    # 二分探索
    while ng+1 < ok:
        mid = (ng+ok) // 2

        # 2次元配列の累積和を求めておく。
        for i in range(N):
            for j in range(N):
                S[i+1][j+1] = S[i+1][j] + S[i][j+1] - S[i][j]

                if A[i][j] > mid:
                    S[i+1][j+1] += 1

        ext = False
        for i in range(N-K+1):
            for j in range(N-K+1):
                if S[i+K][j+K] + S[i][j] - S[i][j+K] - S[i+K][j] < lim:
                    ext = True
        
        if ext: ok = mid
        else: ng = mid
    
    return ok

print(main())
  • まとめ
    今回はC問題を早解きできたこともあり、レートが結構上がりました。
    Cの難易度によってレートが不安定になるので、早くD問題を解けるようになりたいです。
    6月中に入緑を目指して頑張りたいと思います。
    お疲れ様でした。