Zenn
🔥

【AtCoder】ABC404をPythonで解く

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

1. はじめに

目的

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

注意点

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

コンテスト情報

コンテスト名

AtCoder Beginner Contest 404

コンテストURL

https://atcoder.jp/contests/abc404

開催日

2025-05-03(土) 21:00 ~ 2025-05-03(土) 22:40 (100分)

配点

問題 点数
A 100
B 250
C 300
D 400
E 475
F 550
G 600

結果

順位：7607/9579

総合 A B C D E F G
得点 350(2) 100 250(2)
時間 106:43 8:59 96:43

2. 問題と解法

A: Not Found

コード

s = str(input())

words = [i for i in s if s.islower]
for j in [chr(ord("a")+i) for i in range(26)]:
  if not(j in words):
    print(j)
    break

解法

  1. 与えられた文字列の中から、小文字であるものだけを抜き出してリストwordsに格納する。
  2. ord関数を使って、文字aをアスキーコードに変換して、0から26までを加えて、再度文字aからzに変換する。
  3. aからzまでの文字がリストwordsになければ、その時点での文字を出力してプログラムを終了させる。

改善点

s = str(input())

- words = [i for i in s if s.islower]
for j in [chr(ord("a")+i) for i in range(26)]:
-   if not(j in words):
+   if not(j in s):
    print(j)
    break

最初から小文字であることはわかっているので、islowerメソッドを使う必要がない。

B: Grid Rotation

コード

n = int(input())
s = [list(input()) for _ in range(n)]
t = [list(input()) for _ in range(n)]

def rotation(s):
  update = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      update[j][n-(i+1)] = s[i][j]
  for i in range(n):
    for j in range(n):
      s[i][j] = update[i][j]

min_total = n * n + 4
s_copy = [[s[i][j] for j in range(n)] for i in range(n)]

for rotation_num in range(4):
  change_num = 0
  for i in range(n):
    for j in range(n):
      if s_copy[i][j] != t[i][j]:
        change_num += 1
  total = rotation_num + change_num
  if total < min_total:
    min_total = total
  rotation(s_copy)

print(min_total)

解法

  1. グリッドSとTをlist\ in\ listとして保存する。
  2. グリッドを右に90度回転させるローテーション関数を定義する。
  3. 回転数は0から3回のいずれかであり、各々でグリッドSとTの異なるマス（変更が必要なマス）の数を数えて変数change\_numに代入する。
  4. 変数change\_numに回転数rotation\_numを加えたものが操作回数であり、これが最小になる値min\_totalが求める値である。

改善点

- s = [list(input()) for _ in range(n)]
- t = [list(input()) for _ in range(n)]
+ s = [input() for _ in range(n)]
+ t = [input() for _ in range(n)]

グリッドSとTはリスト文字列であるため、list関数を使用する必要はない。

- def rotation(s):
-   update = [[0]*n for _ in range(n)]
-   for i in range(n):
-     for j in range(n):
-       update[j][n-(i+1)] = s[i][j]
-   for i in range(n):
-     for j in range(n):
-       s[i][j] = update[i][j]
+ def right_rot(S):
+   return list(zip(*S[::-1]))

リストを使って回転を行い、それをまた代入し直す処理を行なっても問題ないが、zip関数とスライスを使えばより簡潔に書くことができる。

スライス[::-1]は上下を逆にすることができる。
zip(*)は行と列を入れ替える（転置）することができる。
この作業を逆に行うことで、左回転も可能である。

Discussion