ABC 296 備忘録

概要

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

A問題

ポイント

• 文字列をリストとしてインプット
• リストの中身を見ていき、前の文字と一致しているかどうかを判断させる
• 連続してしまっていたら、その時点で "No" と返してsys.exitする

自分の実装

ABC_296_A.py

import sys

N = int(input())

S = list(input())

last = ""
now = ""

for i in S:
    if now == "":
        now = i
    else:
        now = i
        if last == now:
            print("No")
            sys.exit()
    last = i
print("Yes")

B問題

ポイント

• 入力を2次元のリストとして格納
• "*" のグリットのところを for 文でサーチ
• グリットの位置を ASCII 文字変換によりアルファベットに変換
• 列は左で行は下からカウントしていることに注意

自分の実装

ABC_296_B.py

S = list(list(input()) for i in range(8))

for i in range(8):
    for j in range(8):
        if S[i][j] == "*":
            print(chr(j+97)+str(8-i))

C問題

ポイント

• リスト型で全ての要素比較をすると $O(N^2)$ で TLE する
• ハッシュテーブルを用いて、それぞれの要素について差が X となるような数字を格納
• 元のリストの要素にハッシュテーブル内の要素と一致するものがあるかどうかを検索

自分の実装

ABC_296_C.py

# 入力を受け取る
N, X = map(int, input().split())
A = list(map(int, input().split()))

# ハッシュテーブルを初期化する
hash_table = {}

# ハッシュテーブルに要素を格納する
for i in range(N):
    hash_table[A[i]+X] = i

# 数列 A の要素を順番に見ていき、ハッシュテーブルに要素が存在するか調べる
for i in range(N):
    if A[i] in hash_table:
        # 条件を満たす組が存在するため、Yes を出力して終了する
        print("Yes")
        exit()

# 条件を満たす組が存在しないため、No を出力する
print("No")

感想

　今回もD問題で詰まってしまった。他の方の記事を参考にしながら後日再度挑戦したい。