Magicode logo
Magicode
11 min read

入水したい緑コーダーがABC264のA~Eまで

https://cdn.apollon.ai/media/notebox/ef88696e-effd-412c-9b49-d1e6dc09dbfd.jpeg

freee プログラミングコンテスト2022(AtCoder Beginner Contest 264)

ABC264のA~Eに関する解説(という名の自分用メモ書き)です。

戦績

ついに!!!!!!!!!ついに!!!!!!!!!!!!やった!!!!!!!やりました!!!!!!!!!!!!!!!!!
5完&青パフォ達成!!!!!!!!!!!!!やったあああああああ!!!!!!!!!! 嬉しい!!!!!嬉しい!!!!!!!!5問解けたあああああ!!!!!!!!!!! ノーペナで!!!!!!!!!46:43で!!!!!!!!!!EまでAC!!!!!!!!!!!!!!! 黒ココアさん超絶強いのでは…!?!?!?!?わー嬉しい嬉しい嬉しい…!!!!!!!!!!! 全部得意セットだったので…正直実力感というか、ご褒美セットだった気はします…!!!!! このまま一気に入水したい…!!!!!!!!次回も同じパフォ出せたら入水!!!!!!!!!!!
次も!!!!!5完したい!!!!!!(1回目)

全体のざっくり解説

  • A : スライス切り出し
  • B : グリッド埋め込み
  • C : 2重bit全探索
  • D : バブルソート(転倒数)
  • E : UnionFind&クエリ逆読み

A - "atcoder".substr()

問題要約

文字列atcoderLL文字目からRR文字目までを出力してください。

制約

  • L,RL,Rは整数
  • 1LR71 \leq L \leq R \leq 7

考察

  • スライスで文字列の部分を切り出す話!
  • string[開始位置:終了位置]
    • 0-indexedだし、終了位置の文字は含まれないので、そこだけ注意したらOK!
python
# 入力を受け取って…
L, R = map(int, input().split())

# 文字列のほしい所だけスライス!
print("atcoder"[L - 1:R])

B - Nice Grid

問題要約

15×1515 \times 15の次のグリッドにおいて、上からR行目、左からC列目のますが何色かを出力して下さい。
■■■■■■■■■■■■■■■
■□□□□□□□□□□□□□■
■□■■■■■■■■■■■□■
■□■□□□□□□□□□■□■
■□■□■■■■■■■□■□■
■□■□■□□□□□■□■□■
■□■□■□■■■□■□■□■
■□■□■□■□■□■□■□■
■□■□■□■■■□■□■□■
■□■□■□□□□□■□■□■
■□■□■■■■■■■□■□■
■□■□□□□□□□□□■□■
■□■■■■■■■■■■■□■
■□□□□□□□□□□□□□■
■■■■■■■■■■■■■■■

制約

  • 1R,C151 \leq R,C \leq 15
  • R,Cは整数

考察

  • 偉い人たちや強い人達は「中央からの距離の偶数奇数で…」とか、「チェビシェフ距離が…」とか言われてますけど…
  • ええい、15×1515\times15で規則性があるサイズなら自家で埋め込んでしまえばいいじゃない!!!
  • 使わなくて良い頭は使わないで…!!!(脳筋物理)
python
# グリッド用意ー!
L = [
    "###############",
    "#.............#",
    "#.###########.#",
    "#.#.........#.#",
    "#.#.#######.#.#",
    "#.#.#.....#.#.#",
    "#.#.#.###.#.#.#",
    "#.#.#.#.#.#.#.#",
    "#.#.#.###.#.#.#",
    "#.#.#.....#.#.#",
    "#.#.#######.#.#",
    "#.#.........#.#",
    "#.###########.#",
    "#.............#",
    "###############"
]

# 入力
R, C = map(int, input().split())
# 0-indexedに直して…
R -= 1
C -= 1

# 色判定!終わり!
if L[R][C] == "#":
    print("black")
else:
    print("white")

C - Matrix Reducing

問題要約

H1H_1W1W_1列の行列AAと、H2H_2W2W_2列の行列Bが与えられます。
行列AAに対して、下記の2つの操作のうちどちらかを行うことを、好きなだけ(0回でも良い)繰り返すことができます。
  • AAの行を任意に1つ選んで削除する
  • AAの列を任意に1つ選んで削除する
行列AAを行列BBに一致させることができるかどうかを判定して下さい

制約

  • 1H2H1101 \leq H_2 \leq H_1 \leq 10
  • 1W2W1101 \leq W_2 \leq W_1 \leq 10
  • 1Ai,j1091 \leq A_{i,j} \leq 10^9
  • 1Bi,j1091 \leq B_{i,j} \leq 10^9
  • 入力中の値はすべて整数

考察

  • んー…2つの行列があって、片方を弄くり回してもう一方と一致させられるか問題…
  • 回転したり周りを切ったりする問題があったのを思い出す…。
  • 今回は…制約が縦横大きくても10でしかないので、そのへんからどうにかしたい
  • 行について考えてみると、それぞれの行に対して「削除する/削除しない」を決めた時に、何パターンの行列ができる?
    • 210=10242^{10} = 1024通り
  • 列についても同様に、それぞれの列に対して「削除する/しない」を決めた時は210=10242^{10} = 1024通りの行列ができる。
  • それぞれの操作を組み合わせて考えると、
    • 210×210=10485762^{10} \times 2^{10} = 1048576通りしか結果がないので、全探索で通りますね!
      • 黒ココアさんは判断基準として、10710^7以下なら通るかな、と甘い見積もりしてます…!
  • 後は選ぶ選ばないを全探索したいので、bit全探索…!
  • 詳細なことはググってみて下さい。bit演算子と仲良くなろうね!
python
# 入力
H1, W1 = map(int, input().split())
A = []
for i in range(H1):
    A.append(list(map(int, input().split())))
H2, W2 = map(int, input().split())
B = []
for i in range(H2):
    B.append(list(map(int, input().split())))

# 後々の判定用に行列Bを転置しておきます
T_B = list(list(x) for x in zip(*B))

# Aの行に対して、どれを残す?bit全探索
for i in range(1, 2 ** H1):
    tmp = []
    for j in range(H1):
        if (i >> j) & 1:
            tmp.append(A[j])

    # 行を残したパターンを転置して…
    T_tmp = list(list(x) for x in zip(*tmp))

    # Aの列に対して、どれを残す?
    for j in range(1, 2 ** W1):
        tmp2 = []
        for k in range(W1):
            if (j >> k) & 1:
                tmp2.append(T_tmp[k])

        # もしBと一致したら、終了!
        if T_B == tmp2:
            print('Yes')
            exit()
# 1回も一致しなかったので、ダメでした!!!
print('No')

D - "redocta".swap(i,i+1)

問題要約

atcoderの並べ替えである文字列SSが与えられます。
この文字列SSに対して以下の操作を00回以上行います。
  • SS中の隣接する22文字を選び、入れ替える。
SSatcoderにするために必要な最小の操作回数を求めて下さい。

制約

  • SSatcoderの並べ替えである文字列

考察

  • BFSだったりで求められるらしいですが。
  • とりあえず、atcoder内に同じ文字が2度以上入っていないことを確認して…。
  • a=0,t=1,c=2...のように変換してみて…。
  • 隣り合った数字を入れ替えて、[0,1,2,3,4,5,6][0,1,2,3,4,5,6]の数列にしたい…から…
  • あ、バブルソート…!?!?!?
    • 転倒数とも関係しているらしいので…詳細はお調べ下さい…
      • 転倒数を求めるライブラリを作っておくと幸せになれたりなれなかったりするらしいです
  • 後はバブルソート実装コード拾ってきて…
  • 適当にサンプルケースで試してみて…
  • ちゃんとソートされてるっぽいので、スワップが発生する箇所でカウントして、終わり!!!
python
# 入力
S = input()

# 文字列を、数字に置換して
d = {"a": 0, "t": 1, "c": 2, "o": 3, "d": 4, "e": 5, "r": 6}
L = []
for char in S:
    L.append(d[char])

# カウンター用意!
ans = 0

# 拾ってきたバブルソート関数
def bubble_sort(data):
    global ans # カウンター引っ張ってきて、
    for i in range(len(data)):
        for j in range(len(data) - i - 1):
            if data[j] > data[j + 1]: 
                data[j], data[j + 1] = data[j + 1], data[j]
                ans += 1 # スワップが発生したらカウント記録!!!
    return ans # カウンターの値をそのまま出力!


# 出力して終了!
print(bubble_sort(L))

E - Blackout 2

問題要約

ある国にはNN個の都市とMM個の発電所があります。これらを総称して地点と呼びます。
地点には1,2,,N+M1,2,…,N+Mの番号がつけられており、そのうち都市は1,2,,N1,2,…,Nで、発電所は地点N+1,N+2,,N+MN+1,N+2,…,N+Mです。
この国には電線がEE本あり、電線i(1iE)i(1 \leq i \leq E)は地点UiU_iと地点ViV_iを双方向に結びます。
また、ある都市に電気が通っているとは、ある年から電線をいくつか辿って、少なくとも1つの発電所に辿り着くことが出来る状態を言います。
今、QQ個のイベントが起こります。そのうちi(1iQ)i(1\leq i \leq Q)番目のイベントでは電線XiX_iが切れ、その電線をたどることができなくなります。
一度切れた電線は、その後のイベントにおいても切れたままです。
すべてのイベントについて、そのイベントが終わった直後に電気が通っている都市の数を求めて下さい。

制約

  • 入力はすべて整数
  • 1N,M1 \leq N,M
  • N+M2×105N+M \leq 2\times 10^5
  • 1QE5×1051 \leq Q \leq E \leq 5 \times 10^5
  • 1Ui<ViN+M1\leq U_i < V_i \leq N+M
  • iji\neq jならば、UiUjU_i \neq U_jまたはViVjV_i \neq V_j
  • 1Xi leqE1 \leq X_i \ leq E
  • XiX_iは相違なる

考察

  • 制約量多すぎて困る…とても困る…
  • とりあえず、発電所の数+街の数をあわせて2×1052 \times 10^5個以下…
  • 電線の数は…E5×105E \leq 5 \times 10^5以下…
  • 街から発電所への距離自体は無視していいので、BFS/DFSよりも楽にどうにかできそうですねぇ
  • あー…街と道で、繋がっているか/到達可能判定なら、素直にUnionFindで良さそう…
    • この辺りで方針が定まる
  • UnionFindは、接続するのは簡単だけど切断するのはマジで本当無理なので…
    • 「一旦全部切断された状態」からクエリ逆読みで、1本ずつ接続していくことにしよう
  • じゃあ…えー…後は…発電所…が、いっぱいあるのが問題でして…
  • とりあえず入力例1を手書きしてみる
    • 手を動かして書いてみるの、大事。かつっぱ先生の実況に学ぶ。
  • こんな状態で、逆順に接続していくので…
    • 最初(全部切れてる状態)に、電気が来てる街は1つだけ…
    • 6を繋いで、発電所とつながる街が1つ増える。
    • 5を繋いでも、電気が来てる街の数は変わらず…
  • んー…あれ、これ、発電所を区別する意味無くない…???
    • (この辺りで真理の扉が開く)
  • じゃあ、1~N個の街と、1つの発電所(全部を集約したもの)でUnionFindすれば良い…?ね???いけるね???
  • 発電所の番号を0として、1つの発電所+1~NまでのN個の街でUnionFindクエリ逆読みだ…!!!!!!!!
  • この勝負もろたで工藤!!!!!!!!
python
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

# 入力
N, M, E = map(int, input().split())
edge_L = []

# 0~Nの、N+1地点として見る
# 0が発電所なので、N以上の点と繋いでる辺は「発電所と繋いでる」辺として変換
# この時点ではまだ接続せずに、一旦辺リストとして受け取り…。
for i in range(E):
    U, V = map(int, input().split())
    if U > N:
        U = 0
    if V > N:
        V = 0
    edge_L.append([U, V])

# クエリ準備ー!
Q = int(input())
query_L = []
query_s = set()

# イベントのあった辺=とりあえず接続しない辺
# 切断されるからね!一旦全部切断しておこうね!!!
for i in range(Q):
    X = int(input())
    X -= 1
    query_L.append(X)
    query_s.add(X)

# 街の数+発電所1つでUnionFind作るよー
uf = UnionFind(N + 1)

# 辺毎に見ていくよ。
for i in range(E):
    if i in query_s: # もしイベントで切断される辺なら、先に切っておくので繋がず
        continue
    
    u, v = edge_L[i] # そうじゃないならUnion!接続!
    uf.union(u, v)

ans_L = []

# クエリ逆順読みー。
for i in query_L[::-1]:
    # 発電所と繋がってる街の数 - 発電所の数(1個) = 電気の来てる街の数!
    ans_L.append(uf.size(0) - 1)

    # そのイベント発生前として、つなぎ直すよ!
    u, v = edge_L[i]
    uf.union(u, v)

# 逆順に見たので、逆順に出力して終了!!!
for ans in ans_L[::-1]:
    print(ans)

Discussion

コメントにはログインが必要です。