【AtCoder】ABC277のA,B,C,D,問題をpythonで解説

ABC

ABC277のA,B,C,D問題をpythonで解説していきます。

なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！

A問題

A – ^{-1}

考察

今回、与えられた数列Pにおいて、Xとなる数字のindexを出力すれば良いです。
(※indexは0始まりなので+1するのを忘れずに)

コード

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,X = MI()
P = LI()

for i in range(N):
    if P[i] == X:
        print(i+1)
        exit()

B問題

B – Playing Cards Validation

考察

今回は、Noを出力する場面は、

  1. 文字列がルールを満たしてない
  2. 同じ文字列がある

の２つです。

そこで、
1つ目のルールに関しては、文字列を分割して、それぞれ条件にあっているか確認

2つ目の条件については、すべての入力を受け取ったあとに、set関数を使って、長さが変化したら、同じ要素があったと判断

することとします。

コード

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N = II()
first_list= ["H","D","C","S"]
second_list = ["A" , "2" , "3" , "4" , "5" ,"6" , "7" , "8" , "9" , "T" , "J" , "Q" , "K"]
box = []
for i in range(N):
    s = S()
    box.append(s)

for i in range(N):
    first = box[i][0]
    second = box[i][1]
    if first not in first_list:#文字列の1文字目がH,D,C,Sのどれかか
        print("No")
        exit()
    if str(second) not in  second_list:#文字列の2文字目がA~Kのどれかか
        print("No")
        exit()
    box.append(s)

if len(set(box)) == N:#入力されたときと長さが同じなら、すべての文字列に重複はない
    print("Yes")
else:#文字列の量が変化した場合は、重複があったと判断
    print("No")

C問題

C – Ladder Takahashi

考察

1階から行けるところをdfsするなり、
「1階から行ける→1階と連結することができる」と読み替えてUnionFindすると解けます。(僕はdfsが苦手なのでUnionFindで解きました)

しかし、ここで問題になってくるのは、ビルの高さです。
今回、面倒なのは、ビルの高さが10^9階なので、普通に計算しようとすると、TLEしてしまいます。

Question ではどうするか？

ここで注目したいのは、出てくる階の数です。

今回、はしごは最大でも2*10^5本まで出てこないので、はしごで繋がれる階の数は、最大で2*2*10^5=4*10^5です。

そのため出てくる階の数だけ、nodeを作成し、UnionFindしてあげればできます。

コード

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import bisect

from typing import List

class UnionFind:
    """0-indexed"""

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n
        self.__group_count = n

    def unite(self, x, y) -> bool:
        """xとyをマージ"""
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        self.__group_count -= 1

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

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

        return True

    def is_same(self, x, y) -> bool:
        """xとyが同じ連結成分か判定"""
        return self.root(x) == self.root(y)

    def root(self, x) -> int:
        """xの根を取得"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        """xが属する連結成分のサイズを取得"""
        return -self.parent[self.root(x)]

    def all_sizes(self) -> List[int]:
        """全連結成分のサイズのリストを取得 O(N)
        """
        sizes = []
        for i in range(self.n):
            size = self.parent[i]
            if size < 0:
                sizes.append(-size)
        return sizes

    def groups(self) -> List[List[int]]:
        """全連結成分の内容のリストを取得 O(N・α(N))"""
        groups = dict()
        for i in range(self.n):
            p = self.root(i)
            if not groups.get(p):
                groups[p] = []
            groups[p].append(i)
        return list(groups.values())

    @property
    def group_count(self) -> int:
        """連結成分の数を取得 O(1)"""
        return self.__group_count


N = II()
node_cnt = []
node = []
for i in range(N):
    A,B = MI()
    node_cnt.append(A)
    node_cnt.append(B)
    node.append([A,B])

if 1 not in node_cnt:#そもそも1階とどこかの階にはしごがかかっていなかったら1階から動けないので
    print(1)
    exit()

neo_box = list(set(node_cnt))#出てくる階の数を数えている
neo_box.sort()#bisectを使うので、ソートしておく
uf = UnionFind(len(neo_box))#その階の数だけunionfindのnodeを設ける

for i in range(N):
    A = node[i][0]
    B = node[i][1]
    A_ind = bisect.bisect_left(neo_box,A)#A階は、(ソートされた)出てくる階の中だと何番目のindexを持つのか
    B_ind = bisect.bisect_left(neo_box,B)#A階は、(ソートされた)出てくる階の中だと何番目のindexを持つのか
    uf.unite(A_ind,B_ind)#AのindとBのindをつなげる

for i in range(len(neo_box)-1,0,-1):#後ろから、つまり大きい数字から探索
    if uf.is_same(0,i):#もし、index_0とindex_iが連結されているのなら、
        print(neo_box[i])#そのindexを持つ階には到達可能である
        exit()
#どの階にも到達できなかった場合
print(1)
exit()

D問題

D – Takahashi’s Solitaire

考察

手札に整数 X または整数 (X+1) mod M(X+1) のカードは捨てることができる
→連続したところであれば、場に数字を出し続けることができる
と言い換えることができます。

今回求めたいのは、手札の総和(合計- 連続したところの数列)を最小にしたいので、
連続した数列を最大化して上げる必要があります。

よって、ソートして差が1以下ならその区間は捨てることができ、2以上ならそこが連続して捨てられる数列の切れ目になります。

手順

  1. 連続する区間を取りたいので、ソートします。
  2. もしその数列に切れ目があるのなら、どこの場所でも良いが切れ目から探索します。(M=6で A = [1,2,5,6]ときに、5始まりなら全て消去できるが、1始まりだとすべて消去できないため)
  3. for文を回していき、
    現在地(now)が一つ前の値と同じor連続している場合は、捨てることができ、
    そうではないのなら、現在までに捨てることのできる数字の合計を記憶しておく
  4. 数列の合計値-引くことのできる数字を出力すればOK

コード

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N,M = MI()
A = LI()
B = []
sum_count = sum(A)#Aの合計値を取得
A.sort()

pre = 0
for i in range(N):
    if A[i] - A[i-1] > 1:#連続していない→切れ目の部分なら
        pre = i#切れ目として記憶
        break
minus = 0#場に捨てることのできる数字の和を記憶
tmp = 0#一時的に記憶させておくための変数
for i in range(N):
    now = (pre+i)%N#indexエラーにならないように
    if (A[now]-A[(now-1)]) % M > 1:#現在の数字が一つ前の数字と比べ、差が1以上なら
        minus = max(minus,tmp)#これ以上捨てれる区間は伸びないので、本区間で捨てた数字とこれまでの区間で捨てた最大値を取る
        tmp = 0#一次保存は最初から
    tmp += A[now]#現在の数字からまた捨てる区間を開始

minus = max(minus,tmp)#for文が終わったあとに、tmpとminusを比べ大きい方と取る、
print(sum_count - minus)#全体の合計から場に捨てることのできる最大の数値で引く

まとめ

D問題、時間内に解けなかった・・・悔しい。かつっぱさんのyoutubeみてすぐ復習します！！

コメント

タイトルとURLをコピーしました