Zenn
🔥

【AtCoder】ABC403をPythonで解く

に公開
Python
競技プログラミング
AtCoder
tech

1. はじめに

目的

ABCを解くことにより、とにかくRatingを上げていく。

注意点

言語はPython(PyPy 3.10-v7.3.12) を使用しています。

コンテスト情報

コンテスト名

AtCoder Beginner Contest 403

コンテストURL

https://atcoder.jp/contests/abc403

開催日

2025-04-27(日) 21:00 ~ 2025-04-27(日) 22:40 (100分)

配点

問題 点数
A 100
B 250
C 300
D 425
E 500
F 500
G 600

結果

順位：5287/7784

総合 A B C D E F G
得点 650(1) 100 250 300(1)
時間 81:14 5:08 26:48 76:14

2. 問題と解法

A: Odd Position Sum

コード

n = int(input())
a = map(int, input().split())
count = 0

for i, j in enumerate(a):
  if (i+1) % 2 == 1:
    count += j
    
print(count)

解法

  1. 条件分岐で奇数かどうかを判断する。
  2. 奇数であれば、count変数に加えていく。

改善点

特になし

B: Four Hidden

コード

t = str(input())
u = str(input())
flag = 0

for i in range(len(t)-(len(u)-1)):
  for j in range(len(u)):
    if t[i+j] != u[j] and "?" != t[i+j]:
      break
  else:
    flag = 1

if flag == 0:
  print("No")
else:
  print("Yes")

解法

  1. 最大で、len(t)-(len(u)-1)回の線形探索を行うことになる。
  2. 1回ずつの探索で、TとUが一致するかを一番前の文字から確かめていく。
    • Tのi+j番目が?であれば無条件でOK
    • Tのi+j番目がUと同じ文字ならばOK
  3. 全ての文字が条件を満たせばYes、満たすまで続けていく。

改善点

特になし。

C: 403 Forbidden

コード

n, m, q = map(int, input().split())
admitted = [set() for _ in range(n)]

for i in range(q):
  query = list(map(int, input().split()))
  if query[0] == 1:
    if "all" not in admitted[query[1]-1]:
      admitted[query[1]-1].add(query[2])
  elif query[0] == 2:
    admitted[query[1]-1].add("all")
  elif query[0] == 3:
    if "all" in admitted[query[1]-1] or query[2] in admitted[query[1]-1]:
      print("Yes")
    else:
      print("No")

解法

  1. 誰がどのページへの閲覧権限を持つのかを、set\ in\ listのadmittedに格納していく。
  2. クエリの種類が1か2か3かで処理を分ける。
    1. query[1]番目の人に、query[2]番目のページの閲覧権限を与えて、admitted[query[1]-1]にquery[2]を格納する。
    2. query[1]番目の人に、全てのページの閲覧権限を与えて、admitted[query[1]-1]に"all"を格納する。
    3. query[1]番目の人がquery[2]の閲覧権限を持てば、Yesを出力する。
  3. 集合setを使うことで、クエリ3番の閲覧権限の探索にかかる時間を減らしている。

Discussion