ABC 295 備忘録 #Python

概要

　今回はABC295（2023年3月25日21:00 ~ 22:40）の参加記録について自分の実装と感想について記していこうと思う。

A問題

ポイント

入力をN個の文字列として標準入力から受け取る
条件である and, not, that, the, you に一致するものがあるかどうかをこれらを配列としたものの中に一致するものがあるかどうかを判断させる
一致するものがあった時点でYesと出力し、プログラムをループ中で終了
ループ中で終了しなかった場合は、ループ後にNoと出力し、プログラムを終了

自分の実装

ABC_295.py

import sys

N = int(input())

W = list(map(str, input().split()))

judge = ["and", "not", "that", "the", "you"]

for word in W:
    if word in judge:
        print("Yes")
        sys.exit()

print("No")

B問題

ポイント

マス目をR行のリストとして標準入力から保存
爆弾のマス目の場合、つまり数字のマス目の場合は壁（ = #）のマス目を壊す処理を実行
マンハッタン距離の処理の際に実際に配列のインデックスから出ないように条件文で制限することを忘れない
# 以外のマス目には爆弾の処理が行われないようにする
爆弾自体のマス目の処理はそのマス目の爆弾処理が全て終わった場合に行われるようにする（ = ループを抜けた時に初めて行われるようにする）
最後に行区切りで文字列となるように出力

自分の実装

ABC_295_B.py

R, C = map(int,input().split())

walls = list(list(input()) for i in range(R))

for line in range(R):
    for row in range(C):
        if walls[line][row] != "." and walls[line][row] != "#":
            attack = int(walls[line][row])
            for i in range(attack+1):
                for j in range(attack+1-i):
                    if i != 0 or j != 0:
                        if line-i >= 0 and row-j >= 0:
                            if walls[line-i][row-j] == "#":
                                walls[line-i][row-j] = "."
                        if line+i <= R-1 and row-j >= 0:
                            if walls[line+i][row-j] == "#":
                                walls[line+i][row-j] = "."
                        if line-i >= 0 and row+j <= C-1:
                            if walls[line-i][row+j] == "#":
                                walls[line-i][row+j] = "."
                        if line+i <= R-1 and row+j <= C-1:
                            if walls[line+i][row+j] == "#":
                                walls[line+i][row+j] = "."
            walls[line][row] = "."


for line in range(R):
    print("".join(walls[line]))

C問題

ポイント

靴下の色を標準入力からキューとして格納し、照準となるようにソート
最終的に何個のペアが作れるかどうかは、ある色の靴下の個数が2で割って何個のペアを作れるかどうかを加算
リストでその個数を数えると計算量がオーバーしてしまうため、キューで前の靴下の色と同じかどうかを判断
色の判断時にすでにペアとなってしまっている場合は。前のペアなしとして "" 判断させるようにして区別

自分の実装

ABC_295_C.py

from collections import deque

N = int(input())

A = sorted(list(map(int,input().split())))

A = deque(A)
count = 0

ex_color = ""

for i in range(N):
    present_color = A.popleft()
    # 色が一緒ならば、ペアを作る（前の色が残っている場合）
    if ex_color == present_color:
        count += 1
        ex_color = ""
    else:
        ex_color = present_color

print(count)

D問題

ポイント

嬉しい列になるためには、部分文字列の中の各位の数字の個数が偶数個であることが条件
部分文字列中の数字の個数はl-1文字目までの数字の個数とr文字目までの数字の個数を比較すれば良い

自分の実装

まだ実装できていない。

感想

B問題にかなり時間がかかってしまった。爆弾の処理の条件分岐を正しく実装するのに手間取ってしまったことが原因と考えられる。具体的には、条件分岐の際に爆弾の処理が及ぼすマス自体についてフォーカスしてしまったので、そのマスがインデックス内であるかどうかを考慮する必要が出てきてしまった。公式の解答にあるように元々のマス目自体にフォーカスしてやればよかった。個人的には、C問題の方が条件分岐を考えなければ良い分、簡単だった。D問題については、考え方はわかったものの計算量を時間内に収めるのにどう実装すれば良いかわからなかったのでコンテスト中に解ききれなかった。