2

ABC218 茶色コーダーが解けた所まで+あと1問

7 min read

AtCoder Beginner Contest 218

https://atcoder.jp/contests/abc218

ABC218の問題を、本番で自分が解けた所+1問の解説です。
初めて色がついたので投稿してみました。
茶色を維持しつつ、次は水色を目指したい。

A - Weather Forecast

https://atcoder.jp/contests/abc218/tasks/abc218_a

文字列のスライス

  • S[i]S[i]で、i+1i+1文字目が抽出できる
  • 0indexなので注意
  • 後はif文で条件に従ってあげる。
N = int(input())
S = input()
 
if S[N-1] == 'o':
    print('Yes')
else:
    print('No')

B - qwerty

https://atcoder.jp/contests/abc218/tasks/abc218_b

chr関数

  • 数字→文字列はchr関数でこなすとお洒落
#before
L = list(map(int,input().split()))
 
base_l = ['a']
base_l.append('b')
base_l.append('c')
base_l.append('d')
base_l.append('e')
base_l.append('f')
base_l.append('g')
base_l.append('h')
base_l.append('i')
base_l.append('j')
base_l.append('k')
base_l.append('l')
base_l.append('m')
base_l.append('n')
base_l.append('o')
base_l.append('p')
base_l.append('q')
base_l.append('r')
base_l.append('s')
base_l.append('t')
base_l.append('u')
base_l.append('v')
base_l.append('w')
base_l.append('x')
base_l.append('y')
base_l.append('z')
ans = ''
for i in L:
    ans += base_l[i-1]
print(ans)
# after
L = list(map(int,input().split()))
ans = ''
for i in L:
    ans += chr(96 + i)
print(ans)

C - Shapes

https://atcoder.jp/contests/abc218/tasks/abc218_c

平行移動の話

  • 回転が不要な状態で、図形Sを平行移動を繰り返した時に図形Tと一致するか否かを考える
  • 縦横に並行移動する必要がある?
    • グリッド上にあるS、Tの場所がズレているなら、平行移動する必要がある
      • 場所がズレている=図形S、Tの上下左右に存在する、'#'の含まれていない行の数が異なっている
    • つまり、図形S、Tの上下左右に存在する、'#'の含まれていない行を全て削れば図形は一致する筈

回転の話

  • numpyのrot90でかんたんに90度回転できる
import numpy as np

# 入力
N = int(input())

# Sの入力
S_l = []
for i in range(N):
    tmp = input()
    S_l.append(list(tmp))
S_array = np.array(S_l)

# Tの入力
T_l = []
for i in range(N):
    tmp = input()
    T_l.append(list(tmp))
T_array = np.array(T_l)

# S,Tどちらも上から使ってない行を削除する。削除が終わったら90度回転して、また上から削除。
for i in range(4):
    for i in range(N):  # S削除パート
        if '#' in S_array[0]:
            break
        S_array = np.delete(S_array, 0, 0)
    S_array = np.rot90(S_array)  # Sを90度回転
    for i in range(N):  # T削除パート
        if '#' in T_array[0]:
            break
        T_array = np.delete(T_array, 0, 0)
    T_array = np.rot90(T_array)  # Tを90度回転

# 最終的にSとTを一番小さくした形(使ってない行、列を削りきった状態)で、片方を回転させて同じ形か確かめる
for i in range(4):
    if S_array.shape == T_array.shape:  # もし行、列の数が一緒で…
        if (S_array == T_array).all():  # 同じ形なら終わり
            print('Yes')
            exit()
    S_array = np.rot90(S_array)  # 違うなら回転させてみる

print('No')  # ダメでした!

D - Rectangles

https://atcoder.jp/contests/abc218/tasks/abc218_d

長方形を一意に定めるには

  • 左下の頂点と、右下の頂点を決めると長方形が一意に定まる。
  • 条件より、2000個のうちから2つの組み合わせで全探索
# 入力部
N = int(input())
L = []
S = set()
ans = 0

for i in range(N):
    x, y = map(int, input().split())
    L.append([x, y])
    S.add((x, y)) # 点が存在するか否かの確認用にsetを作る

for i in range(N-1):
    for j in range(i+1, N):
        x1, y1 = L[i]
        x2, y2 = L[j]

        if x1 != x2 and y1 != y2: # 選択した2点が水平or垂直に並んでる場合、長方形はできないのでパス
            point3 = (x1, y2)
            point4 = (x2, y1)
            if (point3 in S) and (point4 in S):
                ans += 1

print(int(ans/2)) # 左下と右上で長方形を確定させるパターンと、左上と右下で長方形を確定させるパターンが存在するため最終結果を2で割る

E - Destruction

https://atcoder.jp/contests/abc218/tasks/abc218_e

考え方

  1. 先に道を全部外してプラスの報酬を全て受け取る
  2. 報酬がマイナスの道に関してはとりあえず繋ぐ
  3. 報酬がプラスの道を、報酬が小さい順(昇順)に並び替える
  4. まだ繋いでない(報酬がプラス)道の、一番報酬が小さい道を取り上げる。
    • Q:道の両端の地点は既に繋がっている?
      • 繋がっている場合→繋ぐ必要が無いので、報酬はそのまま(貰ったまま)
      • 繋がっていない場合→繋ぐ必要があるので、報酬を返却して道を繋ぐ

UnionFind木

https://www.slideshare.net/chokudai/union-find-49066733/1

  • 行程4の、「グラフの2点が繋がっているか?」の判定と、「グラフの2点を繋ぐ」を速く行うためのデータ構造
  • O(log n)らしい。
N, M = map(int, input().split())
L = []
ans = 0
for i in range(M):
    A, B, C = map(int, input().split())
    L.append([C, A, B])
    if C > 0:
        ans += C
 
 
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent_size = [-1]*n
 
    def leader(self, a):
        if self.parent_size[a] < 0:
            return a
        self.parent_size[a] = self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self, a, b):
        x, y = self.leader(a), self.leader(b)
        if x == y:
            return
        if abs(self.parent_size[x]) < abs(self.parent_size[y]):
            x, y = y, x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y] = x
        return
 
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
 
    def size(self, a):
        return abs(self.parent_size[self.leader(a)])
 
    def groups(self):
        result = [[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]
 
 
L.sort()
 
uf = UnionFind(N+1)
 
for c, a, b in L:
    if c <= 0:
        uf.merge(a, b)
        continue
 
    if not uf.same(a, b):
        ans -= c
        uf.merge(a,b)
 
print(ans)

Discussion

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