プログラミングよくわからんケモノのABC391

Posted at 2025-02-07

ABC391感想

コンテスト2回目なのもあり、とりあえず3完目標でやってました。
結論から言うと目標は達成できましたが、まだまだ能力不足を感じましたね。
まあ現状実力不足感が否めないので、DかEに得意問題が来てくれることをしばらく祈り続けることになりそうです。

A問題

与えられた方位に対して、逆の方位を返せ。という問題ですね。

入力（方位）に対して、出力（逆の方位）は常に固定されていて、入力は非常に少ないので、適当に辞書なり、リストなり作って、出力するようにしてやれば終わりですね。

python abc391_a.py

L_A = ["N", "E", "W", "S", "NE", "NW", "SE", "SW"]
L_B = ["S", "W", "E", "N", "SW", "SE", "NW", "NE"]

print(L_B[L_A.index(input())])'

B問題

なんて説明すればいいんですかね。雑に説明すると同じ柄になる場所を探せって問題です。

制約的にでかくても 50 * 50 の広さにしかならないので、雑に左上から一致する箇所を探せばいいと思います。

かなり時間に余裕があるはずなんですが、わざわざ break で計算量減らしてますね。いらない工程。

python abc391_b.py

N, M = map(int, input().split())
area = [list(input()) for _ in range(N)]
a = [list(input()) for _ in range(M)]

ans = [-1, -1]
for i in range(N - M + 1):
  for j in range(N - M + 1):
    
    if area[i][j] == a[0][0]:
      for y in range(M):
        for x in range(M):
          if area[i + y][j + x] != a[y][x]:
            break
          
          if y == x == M - 1:
            print(f'{i + 1} {j + 1}')
            exit()
          
        if area[i + y][j + x] != a[y][x]:
          break

C問題

与えられるクエリを消化しろ。ってタイプの問題ですね。
今回のクエリは鳩を移動させるか、2匹以上鳩が入っている巣はいくつあるか答える、の2つ。

巣Aから巣Bへ鳩を移動させるということは、巣Aの鳩が1匹減って、巣Bの鳩が1匹増えるということで、増減はどちらも1しか発生していません。
聞かれるのは2匹以上入っている巣の数なので、2→1、1→2が発生するときに何らかのリストから抜いたり入れたりすれば、後はそれの要素数が答えです。

ちなみにsortedsetをわざわざ使っていますがsetでいいです。無駄です。
後普段使っている(既に改良が入っているので大分古いやつ。)テンプレのせいで見づらいかと思いますが、下手に触って動かなくなるのもあれなので、提出時そのままで。

python abc391_c.py

import sys
import bisect as bs
import itertools as it
import collections as cs
import sortedcontainers as scs

sys.setrecursionlimit(10**9)

# 入力簡易化
def IP(): return input()
def II(): return int(IP())

def IS(): return IP().split()
def MI(): return map(int, IS())

def LP(): return list(IP())
def LI(): return list(MI())
def LS(): return list(IS())

def LLP(N): return [LP() for _ in range(N)]
def LLI(N): return [LI() for _ in range(N)]
def LLS(N): return [LS() for _ in range(N)]

def MM(high, S = "#"): return [[-1 if square == S else 0 for square in LP()] for _ in range(high)]
def MMS(high, S = "#"): return [[-1 if square == S else 0 for square in LS()] for _ in range(high)]

# モジュール簡易化
def que(N): return cs.deque(N)
def counter(L): return cs.Counter(L)

def sortedset(N): return scs.SortedSet(N)
def sortedlist(N): return scs.SortedList(N)

pigeon_piece, query_num = MI()
pigeon_list = [num for num in range(pigeon_piece + 1)]
hole_list = [0] + [1] * pigeon_piece

ps_l = sortedset([])
for query in LLI(query_num):
    if query[0] == 1:
        if hole_list[pigeon_list[query[1]]] == 2:
            ps_l.discard(pigeon_list[query[1]])

        if hole_list[query[2]] == 1:
            ps_l.add(query[2])
            
        hole_list[pigeon_list[query[1]]] -= 1
        pigeon_list[query[1]] = query[2]
        hole_list[query[2]] += 1

    elif query[0] == 2:
        print(len(ps_l))

今までG問題って絶望でしかなかったのでやりようはあるな、って思えただけ成長を感じますね。それともこの回簡単だったのかな。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

プログラミングよくわからんケモノのABC391

ABC391感想

A問題

B問題

C問題

D問題

E問題

F問題

G問題