LoginSignup
0
1

More than 3 years have passed since last update.

@Natsuserina

AtCoder Problems Hard No.61~70解説

Posted at

Hard No.61 : C - 次のアルファベット

C - 次のアルファベット

発想

アルファベットに割り当てられているアスキーコードを使うのが良さそうです。アルファベットのアスキーコードは$a$の97から$z$の122まで1ずつ増えていきます。文字列$s$を前から見ていって、その文字を$a$に変えられるか毎回判断していきます。

実装

アルファベットからアスキーコードへの変換はord()関数、逆向きの変換はchr()関数を使います。
操作は$K$回やり切らなければならないこと、そのとき変える文字は最後の1文字だけで良いことに気をつけます。

S = list(input())
K = int(input())

ans = ''
#最後の1文字を除いて'a'に変換できるか見ていく
for i in range(len(S)-1):
    if S[i] == 'a':
        ans += 'a'
    else:
        if K >= 123 - ord(S[i]):
            ans += 'a'
            K -= 123 - ord(S[i])
        else:
            ans += S[i]

#Kは大量に残っている可能性があるので26で割ったあまりを考える
K %= 26
ans += chr((ord(S[-1])-97+K)%26+97)

print(ans)

Hard No.62 : D - Lamp

D - Lamp

発想

現在地から4方向にマスが照らされるので、4方向を分けて計算して、最後にその和を取る方針にします。

実装

端の処理をしておく必要があります。現在地は重複して数えていますので、その分を引きます。

H, W = map(int, input().split())
S = []
for i in range(H):
    s = input()
    S.append(s)

#左側に照らせるマスの個数
L = []
for i in range(H):
    L.append([0]*W)
#右側に照らせるマスの個数
R = []
for i in range(H):
    R.append([0]*W)
#上側に照らせるマスの個数
U = []
for i in range(H):
    U.append([0]*W)
#下側に照らせるマスの個数
D = []
for i in range(H):
    D.append([0]*W)

for i in range(H):
    for j in range(W):
        #壁マスは問答無用で0
        if S[i][j] == '#':
            L[i][j] = 0
            R[i][j] = 0
            U[i][j] = 0
            D[i][j] = 0
        #端のマスの値を入れておく
        else:
            if j == 0:
                L[i][j] = 1
            if j == W-1:
                R[i][j] = 1
            if i == 0:
                U[i][j] = 1
            if i == H-1:
                D[i][j] = 1

#端以外のマスに値を入れていく
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if j > 0:
                L[i][j] = L[i][j-1] + 1
            if i > 0:
                U[i][j] = U[i-1][j] + 1
#端以外のマスに値を入れていく
for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        if S[i][j] == '.':
            if j < W-1:
                R[i][j] = R[i][j+1] + 1
            if i < H-1:
                D[i][j] = D[i+1][j] + 1

Ans = []
for i in range(H):
    Ans.append([0]*W)

for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            #4方向のマスの値の和から重複して数えた現在地の分を引く
            tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        else:
            tmp = 0
        Ans[i][j] = tmp

ans = 0
for i in range(H):
    ans = max(ans, max(Ans[i]))
print(ans)

Hard No.63 : C - こだわり者いろはちゃん

C - こだわり者いろはちゃん

発想

$N$が10000未満です。支払う金額の最大値は99999です。$N$から99999まで順番に調べて初めて条件を満たす数字を答えとすれば良いです。

実装

import collections

N, K = map(int, input().split())
D = list(map(int, input().split()))
C = collections.Counter(D)

for n in range(N, 10000):
    n = list(str(n))
    for i in n:
        if C[int(i)] >= 1:
            break
    else:
        print(''.join(n))
        exit()

Hard No.64 : C - Bridge

C - Bridge

発想

通らない辺を1つ決めた状態で深さ優先探索をして、到達不可の頂点があれば、その辺は橋です。これを$M$回実行すれば良いです。

実装

N, M = map(int, input().split())
G = []
for i in range(N):
    G.append([])
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

visited = [False]*N

def dfs(k, i, j):

    visited[k] = True

    for l in G[k]:
        #通らないと決めた辺
        if i == k and j == l:
            continue
        if not visited[l]:
            dfs(l, i, j)

ans = 0
for i in range(N):
    for j in G[i]:
        #通らない辺i--jを決めた状態で深さ優先探索をする
        dfs(0, i, j)

        for m in range(N):
            #1つでも訪れなかった頂点があれば答えに1を足す
            if not visited[m]:
                ans += 1
                break
        #visitedを初期化
        visited = [False]*N

print(ans)

Hard No.65 : D - Card Eater

D - Card Eater

発想

同じ整数が描かれたカードが2枚以上あってはいけないです。答えの最大値は整数の種類の数になります。食べなければならないカードの枚数が偶数の時は、全ての整数が1枚ずつ残り答えは最大値を取ります。奇数の時は1種類の整数が絶滅するので答えは最大値から1引いた数になります。

実装

import collections
N = int(input())
A = list(map(int, input().split()))
C = collections.Counter(A)

tmp = 0
ans = 0
for c in C:
    if C[c] >= 2:
        tmp += C[c]-1
    if C[c] >= 1:
        ans += 1

if tmp % 2 == 1:
    ans -= 1

print(ans)

Hard No.66 : B - ABC

B - ABC

発想

$s$を左から見ていって、'BC'が現れたら直前まで連続していた'A'を'BC'よりも右側に移動させます。例えば'AAAABC'の場合は4つの'A'を移動させますが、'AABAAABC'の場合は左側の2つの'A'は移動できません。

実装

'BC'があった場合は常に'BC'の塊で考えるので、'BC'を別の文字'D'に置き換えます。

S = input()
S = S.replace('BC', 'D')
ans = 0
ac = 0

for c in S:
    if c == 'A':
        ac += 1
    elif c == 'D':
        ans += ac
    else:
        ac = 0

print(ans)

Hard No.67 : D - Christmas

D - Christmas

発想

レベル$L$のバーガーはレベル$L-1$のバーガーを使って表せるし、レベル$L-1$のバーガーはレベル$L-2$のバーガーを使って表せる。つまり、レベル$N$のバーガーをレベル$N-1$以下のバーガーを使って再帰的に表せる。レベルNのバーガーの厚さ$a_N$は

a_N = 2a_{N-1}+3\\
\therefore a_N = 2^{N+2}-3

となる。
また、パティの枚数$p_N$は

p_N = 2a_{N-1}+1\\
\therefore p_N = 2^{N+1}-1

となる。$X$の位置がバーガーの中心よりも下側か上側かで場合分けしていきます。

実装

N, X = map(int, input().split())
def dp(n, x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    #xがバーガーの中心よりも下側の時
    if x <= 2**(n+1) - 2:
        return dp(n-1, x-1)
    #xがバーガーの中心以上の時
    else:
        return 2**n + dp(n-1, x-2**(n+1)+1)

print(dp(N, X))

Hard No.68 : D - String Equivalence

D - String Equivalence

発想

同型な文字列の中で辞書順最小の文字列が標準形です。同じ長さを持つ標準形の文字列を列挙した時、その中で辞書順最大の文字列に含まれる文字は全て異なります。例えば文字列の長さが3の時は$abc$になります。ということは、文字列の長さが1増えるごとに、文字列に含まれうる文字の種類は1増えます。

実装

文字列の長さが$N$になるまで文字列を長くしていき、$N$になったときに出力すれば良いです。

N = int(input())

def dfs(S):
    if len(S) == N:
        print(S)
    else:
        #文字列を長くするときに追加する文字は'a'から現在の最大値+1の文字まで
        for i in range(97, ord(max(S))+2):
            dfs(S + chr(i))

dfs('a')

Hard No.69 : C - Align

C - Align

発想

値が大きいものと小さいものを交互に並べれば最大値になりそうです。ただ、(大)(小)(大)(小)...と並べた場合と(小)(大)(小)(大)...と並べた場合で、どちらが大きくなるかわからないので、両方計算して大きい方を取ります。

実装

末尾の数字を先頭に持ってきた方が求める値が大きくなる場合があるので、その場合も検証します。

from collections import deque

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

A = sorted(A, reverse=True)
A = deque(A)
B = deque()
for i in range(N):
    B.append(A[i])

Ans1 = deque()
Ans2 = deque()
#大きい値から始めて大きい値と小さい値を交互に並べる
while len(A) > 0:
    up = A.popleft()
    Ans1.append(up)

    if len(A) > 0:
        down = A.pop()
        Ans1.append(down)
#小さい値から始めて大きい値と小さい値を交互に並べる
while len(B) > 0:
    down = B.pop()
    Ans2.append(down)

    if len(B) > 0:
        up = B.popleft()
        Ans2.append(up)

ans1 = 0
for i in range(N-1):
    ans1 += abs(Ans1[i]-Ans1[i+1])
#末尾を先頭に持ってきた場合と比較する
ans1 = max(ans1, ans1 - abs(Ans1[-1]-Ans1[-2]) + abs(Ans1[0]-Ans1[-1]))

ans2 = 0
for i in range(N-1):
    ans2 += abs(Ans2[i]-Ans2[i+1])
#末尾を先頭に持ってきた場合と比較する
ans2 = max(ans2, ans2 - abs(Ans2[-1]-Ans2[-2]) + abs(Ans2[0]-Ans2[-1]))

ans = max(ans1, ans2)
print(ans)

Hard No.70 : C - Snuke Festival

C - Snuke Festival

発想

配列Aに対してBの各要素がどの位置に来るかは二分探索で求められます。同様に配列Cに対してBの各要素がどの位置に来るかを二分探索で求めます。あとはBの各要素に対して（BのAに対する位置）×（$N-$（BのCに対する位置)を順次計算して答えに足していけば良いです。

実装

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A)
B = sorted(B)
C = sorted(C)

#Aに対するB[i]の位置
Ba = []
for i in range(N):
    k = bisect.bisect_left(A, B[i])
    Ba.append(k)
#Cに対するB[i]の位置
Bc = []
for i in range(N):
    k = bisect.bisect_right(C, B[i])
    Bc.append(N-k)

ans = 0
for i in range(N):
    ans += Ba[i]*Bc[i]

print(ans)
0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1