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

## ABC391感想

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

## [A問題](https://atcoder.jp/contests/abc391/tasks/abc391_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問題](https://atcoder.jp/contests/abc391/tasks/abc391_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問題](https://atcoder.jp/contests/abc391/tasks/abc391_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))

```

## [D問題](https://atcoder.jp/contests/abc391/tasks/abc391_d)
初期状態が与えられるので重力の影響を与えて、一列揃ったら消すというテトリスをやります。
何秒後に特定のブロックが残っているかを何回か聞かれるので答えろ。って問題です。

結局解けませんでしたが、とりあえず揃ったら消すをブロックが地面についたら消える、に一旦置き換えるとxごとに分けてみたとき、それぞれブロックが地面につくのが何秒後かのリストを出せるわけです。
で、このxごとに分けたリストの前からmaxを取っていくと、下からn個目(n列目)のブロックが何秒後に消えるかのリストを作れると。(一番下に落ちないと消えない特性があるため、そこは注意)
後は各ブロックに、それぞれ消える時間を与えて質問に答え続ければよさそうかな、と思っています。


## [E問題](https://atcoder.jp/contests/abc391/tasks/abc391_e)
トーナメントがあり、それぞれのブロックの勝者を決めていく～みたいな処理をし続けたときに出る値を反転させるには、何個の数字を反転させる必要があるか。って問題ですね。

Nの値があまりにも小さい(12)ので、何とかしてくれって感じですかね。
考察はほとんどしていませんけど、000というブロックを1になるためには0を2つ1に。001の場合は、0を1つ1に。で終わりなんですよね。
Nの値も大したことないので、DPを駆使すれば解けそうだなぁ。と思っています。

## [F問題](https://atcoder.jp/contests/abc391/tasks/abc391_f)
問題文の通りです。よく理解できていません。

全く考察出来てませんけど、全部一番小さいのを選べば最小、逆だと最大にはなりますよね。
値を見つける問題ですし、二分探索をすんごい応用すれば解けるんですかね～。

## [G問題](https://atcoder.jp/contests/abc391/tasks/abc391_g)
これも問題文の通りです。　全くわからん。

解ける気はしていませんが3文字の中にabって文字列が入るのってab\*か、\*abのどっちかでしかないですよね。とりあえずab*が26通りあって、\*abが26通りあって、abaの場合どっちにも入っちゃうから1引いて51通り？
で、a\**とb\**も似た感じで計算して～ってやると答えは出せそう。

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