【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月中に入緑を目指して頑張りたいと思います。
お疲れ様でした。