Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Natsuserina

AtCoder Problems Hard No.41~50解説

Posted at

#Hard No.41 : C - Triangular Relationship
C - Triangular Relationship
##発想
$a,b,c$が全て$K$の倍数であれば、$a+b,b+c,c+a$も全て$K$の倍数になります。次に、$a,b,c$は$K$の倍数ではないが問題の条件を満たす場合はあるかなと考えます。$a,b,c$それぞれを$K$で割った時のあまりがちょうど$K/2$であれば問題の条件を満たします。そしてこの場合、$K$は偶数でなければならないです。
##実装

N, K = map(int, input().split())

#Nまでの整数の中でKの倍数の個数はN//K個、これがa,b,cの3通りある
ans = (N//K)**3
#Kが偶数のとき
if K % 2 == 0:
    tmp = N//K
    if N % K >= K//2:
        tmp += 1
    ans += tmp**3

print(ans)

#Hard No.42 : D – Insertion
D – Insertion
##発想
最初から正しい括弧列になっている部分が邪魔なので、それを初めに消去します。残った括弧列の文字数と同数の’(‘か’)’を追加すれば良いです。
##実装

N = input()
S = T = input()
p = '('
q = ')'
o = '()'
#消去できる括弧列を消去する
while o in S:
    S = S.replace(o, '')

f = S.count
#残ったqと同数のpと残ったpと同数のqを元の括弧列に加える
print(p*f(q) + T + q*f(p))

#Hard No.43 : D – Wall
D – Wall
##発想
0から9までの全ての数字を1に変えます。各数字から1に直接変化させるのに必要な魔力が与えられています。この魔力の値によっては、直接1に変化させるよりも別の数字をいくつか経由して1に変化させた方が必要な魔力は小さい場合があります。このときに必要な魔力の最小値を求めます。これはワーシャルフロイド法そのままの考え方です。つまり$i$から$j$に移動するのに$k$個の数字を経由した時の必要な魔力の最小値です。
##実装

import collections

INF = 1_000_000_000_000_000_000

H, W = map(int, input().split())

dist = []
for i in range(10):
    dist.append([INF]*10)

for i in range(10):
    c = list(map(int, input().split()))
    for j in range(10):
        dist[i][j] = c[j]

for i in range(10):
    dist[i][i] = 0

#ワーシャルフロイド法
for k in range(10):
    for i in range(10):
        for j in range(10):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

A = []
for i in range(H):
    a = list(map(int, input().split()))
    A += a

ans = 0
C = collections.Counter(A)
for c in C:
    if c == 1 or c == -1:
        continue
    #数字cから1に移動するのに必要な魔力×cの個数
    ans += dist[c][1] * C[c]

print(ans)

#Hard No.44 : C - HonestOrUnkind2
C - HonestOrUnkind2
##発想
$N$が15以下であることに注目します。答えも$N$以下になるので誰が正直者なのかを全探索できそうです。ちなみに

log_{10}(2^{29}) ≒ 8.73\\
log_{10}(2^{30}) ≒ 9.03

なので$2^{30}$あたりが競プロでTLEしない限界かと思います。全探索したときに矛盾した発言が1つもない場合を答えとします。
##実装
矛盾した発言があった場合は２重ループを抜けるようにしています。

N = int(input())
D = []
for i in range(N):
    D.append([])
#D[i] : 人iは人xをyと証言した
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        D[i].append([x-1, y])

ans = 0
#誰が正直者かを全探索
for i in range(2**N):
    #true : 正直者
    true = []
    for j in range(N):
        if i>>j&1 == 1:
            true.append(j)
    
    for t in true:
        #正直者tについてtの証言を調べる
        for x, y in D[t]:
            #xが正直者trueの中にいるのにtはxを不親切な人と証言している
            if true.count(x) == 1 and y == 0:
                break
            #xが正直者trueの中にいないのにtはxを正直者だと証言している
            if true.count(x) == 0 and y == 1:
                break
        else:
            continue
        break
    else:
        ans = max(ans, len(true))

print(ans)

#Hard No.45 : D - 2017-like Number
D - 2017-like Number
##発想
クエリごとに毎回”2017に似た数”を数え上げていたらTLEします。$x$は$10^5$までなので、$10^5$までの”2017に似た数”をあらかじめ求めておきます。このように「クエリが与えられたときに、あらかじめ必要な計算をしておくことでTLEしないようにする」という考え方は競プロでたびたび見かけます。クエリが与えられるごとに$l$と$r$の位置を二分探索すれば$O(Qlog(N))$で間に合いそうです。
##実装

import bisect
import collections

A = []
def divisor(n):
    global A
    i = 2
    while i * i <= n:
        if n%i == 0:
            return
        i += 1
    return n
#10^5までの素数をAに入れる
for i in range(2, 10**5 + 1):
    D = divisor(i)
    if not D:
        continue
    A.append(D)
#Bに入るのは"2017に似た数"
B = []
C = collections.Counter(A)
for i in A:
    if i == 2:
        continue
    if C[(i+1)//2] == 1:
        B.append(i)

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    #lの位置cur_l, rの位置cur_r
    cur_l = bisect.bisect_left(B, l)
    cur_r = bisect.bisect_right(B, r)
    print(cur_r - cur_l)

#Hard No.46 : A – String
A - STring
##発想
‘S’と’T’は同じ数だけあります。’S’が現れるごとに答えに2を足し、’T’が現れるごとに2を引けば良いです。
##実装

X = input()
ans = 0
for i in X:
    if i == 'S':
        ans += 2
    elif ans >= 2:
        ans -=2

print(ans)

#Hard No.47 : D - Lunlun Number
D - Lunlun Number
##発想
どの桁の数も隣の桁の数との差の絶対値が1以下です。最初に0~9までの数を答えのリストに入れ、順次桁数を増やした数を追加していく形がいいです。
##実装

K = int(input())
A = [i for i in range(10)]
#length : 桁数
length = 1

while len(A) <= K:

    B = []
    for a in A:
        a = str(a)

        if len(a) < length:
            continue
        #取り出した数aの1桁目の数
        num1 = a[-1]
        #num1より1小さい数
        num2 = ''
        #num1より1大きい数
        num3 = ''

        if int(num1) > 0:
            num2 = str(int(num1) - 1)
        if int(num1) < 9:
            num3 += str(int(num1) + 1)

        Num = num2 + num1 + num3
        #取り出した数aの末尾に1桁数字を加える
        for num in Num:
            B.append(int(a+num))

    A += B
    A = list(set(A))
    length += 1

print(A[K])

#Hard No.48 : E - Crested Ibis vs Monster
E - Crested Ibis vs Monster
##発想
求めるものは必要な魔力の最小値です。モンスターの残り体力によって必要な魔力の値は変わります。状態が刻々と変化しますので、動的計画法を使うと良さそうだなと考えます。$dp$の定義はこんな形にします。
$dp[i]$ : モンスターの体力を$i$減らすのに必要な魔力の最小値
##実装

H, N = map(int, input().split())
#dpの中身は大きな値で初期化
dp = [10**18]*(H+1)
dp[0] = 0

for _ in range(N):
    a, b = map(int, input().split())

    for i in range(H):
        #i+aがHを超える場合があるのでmin(i+a, H)にする
        dp[min(i+a, H)] = min(dp[min(i+a, H)], dp[i] + b)

print(dp[H])

#Hard No.49 : D – Bouquet
D – Bouquet
##発想
異なる$n$個のものから$k$個を選ぶ場合の数は$_nC_k$ですが、この$k$を1から$n$まで動かしたときの和から$k = a, k = b$の場合を引いたものが答えです。この和の部分は二項定理を考えれば$2^n$になることは有名です。$n$個のものそれぞれに対して取る取らないを選択するから$2^n$とも考えられます。よって$_nC_a$, $_nC_b$を求めれば勝ちです。
##実装
Pythonの便利な関数pow()を使います。例えばpow(2, $n$, $m$)は$2^n$を$m$で割ったときの余りを返します。
$_nC_a$, $_nC_b$を計算するときには分数の形が出てきます。分数は扱いたくないです。分数を扱わなくて済むようにフェルマーの小定理を用います。

フェルマーの小定理：$P$が素数のとき、$P$の倍数でない整数$a$について、以下が成り立つ

a^{P-1} ≡ 1 \quad (mod \ M)

今回は$M$が$10^9+7$であり、これは素数なので

a^{(10^9+7)-1} ≡ 1 \quad (mod \ 10^9+7)\\
a^{ \ }・a^{(10^9+7)-2} ≡ 1 \quad (mod \ 10^9+7)

となるので、$a^{(10^9+7)-2}$が$a$の逆元になることがわかる。つまりmodの世界では$a$で割ることと$a^{(10^9+7)-2}$をかけることは等しいとわかる。

import math

n, a, b = map(int, input().split())
mod = 10**9 + 7

ans = pow(2, n, mod) - 1
p = 1
q = 1
for i in range(1, b+1):
    p = (p*(n-i+1)) % mod
    q = (q*i) % mod
    if i == a:
        nCa = p*pow(q, mod-2, mod)
else:
    nCb = p*pow(q, mod-2, mod)

ans = (ans - nCa - nCb) % mod

print(ans)

#Hard No.50 : D - Grid Repainting
D - Grid Repainting
##発想
できるだけたくさんのマスを黒に変えたいです。($(1, 1)$から$(H, W)$までの距離)+1は通ってきた白マスの数に等しいです。白マスの総数から($(1, 1)$から$(H, W)$までの距離)+1を引けば、これが黒に変えられるマスの個数になります。
##実装

from collections import deque

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

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

Q = deque()
Q.append([0, 0])

#(1, 1)から(H, W)までの距離を幅優先探索で求める
while len(Q) > 0:

    i, j = Q.popleft()

    for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        i2 = i + di
        j2 = j + dj
        if not (0 <= i2 < H and 0 <= j2 < W):
            continue
        if S[i2][j2] == '#':
            continue
        if dist[i2][j2] == -1:
            dist[i2][j2] = dist[i][j] + 1
            Q.append([i2, j2])

tmp = 0
#白マスの総数
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1

ans = tmp - dist[H-1][W-1] -1

if dist[H-1][W-1] == -1:
    ans = -1

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

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?