15
Help us understand the problem. What are the problem?

posted at

【AtCoder解説】PythonでABC249のA,B,C,D,E,F問題を制する!

ABC249A,B,C,D,E,F問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

  • シンプル:余計なことを考えずに済む
  • 実装が楽:ミスやバグが減ってうれしい
  • 時間がかからない:パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントツイッターマシュマロ、Discordサーバーまでお気軽にどうぞ!

Twitter: u2dayo
マシュマロ: https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー(質問や記事の感想・リクエストなどどうぞ!) : https://discord.gg/jZ8pkPRRMT
よかったらLGTM拡散していただけると喜びます!

目次

ABC249 まとめ
A問題『Jogging』
B問題『Perfect String』
C問題『Just K』
D問題『Index Trio』
E問題『RLE』
F問題『Ignore Operations』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

  • レート別問題正解率
  • パフォーマンス目安
  • 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC249 まとめ

全提出人数: 8309人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 -B------ 200 11分 5776(5534)位
400 AB------ 300 40分 4624(4383)位
600 AB------ 300 11分 3779(3539)位
800 ABC----- 600 54分 2886(2658)位
1000 ABC----- 600 14分 2143(1918)位
1200 ABCD---- 1000 73分 1537(1316)位
1400 ABCD---- 1000 46分 1079(861)位
1600 ABCD---- 1000 27分 742(531)位
1800 ABCDE--- 1500 91分 490(302)位
2000 ABCDE--- 1500 63分 328(162)位
2200 ABCDEF-- 2000 102分 225(84)位
2400 ABCDEF-- 2000 82分 140(39)位

色別の正解率

人数 A B C D E F G Ex
2770 71.5 % 85.3 % 17.6 % 3.8 % 0.1 % 0.1 % 0.0 % 0.0 %
1400 93.9 % 98.2 % 70.6 % 20.1 % 0.5 % 0.8 % 0.0 % 0.0 %
996 95.8 % 98.0 % 91.6 % 57.6 % 0.6 % 3.0 % 0.1 % 0.0 %
650 97.1 % 98.0 % 96.2 % 88.9 % 9.5 % 20.8 % 0.0 % 0.0 %
367 93.7 % 95.4 % 94.3 % 93.2 % 36.0 % 52.0 % 0.3 % 0.0 %
183 92.9 % 93.4 % 92.3 % 91.8 % 63.9 % 76.5 % 6.0 % 0.0 %
36 86.1 % 86.1 % 83.3 % 83.3 % 77.8 % 77.8 % 47.2 % 2.8 %
24 95.8 % 100.0 % 100.0 % 100.0 % 95.8 % 95.8 % 66.7 % 12.5 %

表示レート、灰に初参加者は含めず

A問題『Jogging』

問題ページA - Jogging
コーダー正解率:71.5 %
コーダー正解率:93.9 %
コーダー正解率:95.8 %

おそらく、歴代のABC-A問題で最も難しい問題です。難しいB問題並の難易度でしょう。

入力

$A,B,C$ : 高橋君は「$A$ 秒間歩き、$C$ 秒間休む」ことを繰り返す。歩く速度は秒速 $B$ メートル。
$D,E,F$ : 青木君は「$D$ 秒間歩き、$F$ 秒間休む」ことを繰り返す。歩く速度は秒速 $E$ メートル。
$X$ : $X$ 秒後に高橋君と青木君のどちらが長い距離を進んだかを判定する。

  • $1\le{X}\le{100}$
  • 入力は全て整数

考察

$X$ が小さいので、高橋君と青木君の動きを $1$ 秒ずつ、$X$ 秒後までシミュレートすれば解けます。

$A+C$ 秒が $1$ 周期であることに注目すると、算数で $O(1)$ で解くこともできます。

コード

シミュレート

t % (p + r) < pという式を使えば、t から t+1 秒の間歩いているか休んでいるかを判定できますが、あえて使わずに単純にしています。 わかる人は使うとコードが短くなります。

def solve():
    def calc(p, q, r):
        """p秒間秒速qメートルで歩き、r秒間休むことを繰り返す人がx秒で進む距離を計算"""
        t = 0  # 経過時間
        dist = 0  # 進んだ距離
        while True:
            # p秒間歩く
            for _ in range(p):
                t += 1
                dist += q
                if t == x:  # x秒経過したら終了
                    return dist
            # r秒間休む
            for _ in range(r):
                t += 1
                if t == x:
                    return dist

    a, b, c, d, e, f, x = map(int, input().split())
    tak = calc(a, b, c)
    aok = calc(d, e, f)
    if tak == aok:
        return "Draw"
    if tak > aok:
        return "Takahashi"
    else:  # tak < aok
        return "Aoki"


print(solve())

算数

calc関数以外は上のコードと同じなので省略します。

def calc(p, q, r):
    """p秒間秒速qメートルで歩き、r秒間休むことを繰り返す人がx秒で進む距離を計算"""
    return p * q * (x // (p + r)) + q * min(p, x % (p + r))

B問題『Perfect String』

問題ページB - Perfect String
コーダー正解率:85.3 %
コーダー正解率:98.2 %
コーダー正解率:98.0 %

入力

$S$ : 長さ $1$ 以上 $100$ 以下で、英大文字と英小文字からなる文字列

考察

$3$ つの条件を別々に判定して、すべて満たすかを調べればいいです。

以下の方法が簡単ですが、思いつかなくてもforループで $1$ 文字ずつ調べればいいです。

英大文字が文字列の中に現れる

制約より、$S$ に英大文字、英小文字以外の文字は出現しません。$S$ に英大文字がないとしたら、$S$ はすべて英小文字です。

すべて英小文字の文字列とは atcoder, fffff, x などで、英大文字はありません。反対に、この問題においてすべて英小文字でない文字列とはAtCoder, A, Perfect などで、英大文字が含まれます。

文字列 Sすべて英小文字からなるかを判定するのには、S.islower() が使えます。英大文字が含まれるかどうかは、 not S.islower() で判定できます。

英小文字が文字列の中に現れる

英大文字の場合と同様に、not S.isupper() で判定できます。

すべての文字が相違なる

すべての文字が異なるならば、『文字列 S に現れる文字の種類数』と『文字列Sの長さ』は等しいです。

文字列 S に現れる文字の種類数は、len(set(S)) で求められます。(set型に変換して重複を省いて要素数を調べています)

len(S) == len(set(S)) で判定できます。

コード

def judge():
    S = input()
    b1 = not S.islower()
    b2 = not S.isupper()
    b3 = len(S) == len(set(S))
    return b1 and b2 and b3


print("Yes" if judge() else "No")

C問題『Just K』

問題ページC - Just K
コーダー正解率:17.6 %
コーダー正解率:70.6 %
コーダー正解率:91.6 %

入力

$N$ : 文字列の個数
$S_i$ : $i$ 番目の文字列(英小文字からなり、同じ文字は $2$ 個以上含まれない)
$K$ : 「選んだ文字列の中でちょうど $K$ 個の文字列に登場する英小文字」の種類数の最大値を求める

  • $1\le{N}\le{15}$
  • $S_i$ の長さは $26$ 以下(同じ文字が $2$ 個以上含まれないため)

考察

**ありえる文字列の選び方を全て試して、最大の値を求めればいいです。**文字列の選び方は $2^N$ 通りなので、最大でも $2^{15}=32768$ 通りだけしかありません。

ある $1$ つの選び方に対する種類数の答えは、そのまま選んだ文字列に 各英小文字が出てくる回数をカウントして、ちょうど $K$ 回出てくるものを求めればいいです。

ありえる選び方をすべて試すのには、いわゆるbit全探索というアルゴリズムを使います。名前は強そうですが、ただの全探索です。知らない方は、下の記事を読んでみてください。

こわくないbit全探索1 入門編: bit全探索ってなに?【競プロ解説】

コード

from collections import Counter
from itertools import product


def solve():
    def calc(pro):
        """選び方 pro に対する答えを求める"""
        C = Counter()  # 空のカウンターを用意する
        for i in range(N):
            if pro[i]:
                # S[i]を選ぶ場合、S[i]に含まれる文字のカウントにそれぞれ1足す C.update(S[i])なら1行
                for ch in S[i]:
                    C[ch] += 1
        score = 0
        for ch, cnt in C.items():
            if cnt == K:  # K回"ちょうど"の種類数です
                score += 1
        return score

    N, K = map(int, input().split())
    S = [input() for _ in range(N)]
    ans = 0
    for pro in product((True, False), repeat=N):
        ans = max(ans, calc(pro))
    return ans


print(solve())

D問題『Index Trio』

問題ページD - Index Trio
コーダー正解率:3.8 %
コーダー正解率:20.1 %
コーダー正解率:57.6 %

入力

$N$ : 整数列の長さ
$A_i$ : 数列の $i$ 番目の要素は $A_i$

  • $1\le{A_i}\le2\times{10^5}$

考察

全探索解法

$(i,j,k)$ の組として考えられる組み合わせは $N^3$ 組あるので、$3$ つの数字の選び方を全探索はできません。高速に数えられないか考えてみます。

$\dfrac{A_i}{A_j}=A_k$

右辺の $A_k$ は正の整数ですから、左辺の $\dfrac{A_i}{A_j}$ は正の整数でなければいけません。

$A_i, A_j$ も正の整数ですから、$\dfrac{A_i}{A_j}$ が正の整数になるには、分子の $A_i$ が分母の $A_j$ で割り切れる必要があります。つまり、$A_i$ は $A_j$ の倍数である必要があります。

$A$ の要素の値が最大で $2\times10^5$ までと比較的小さいことを利用して、左辺の分母・分子の値を $1$ から $2\times{10^5}$ まで全探索します。

ただし、普通に二重ループを書くと $4\times{10^{10}}$ 組調べることになります。そこで、分母を先に決めてから、分子はその倍数だけを調べることで、左辺が整数にならない組を調べないようにします。

一見調べる組み合わせ数が大きく減りそうには思えませんが、**実はそのような組は、分母・分子の最大値を $K$ とすると、 $O(K\log{K})$ 組であることが知られています。**具体的には、 $K=2\times{10^5}$ とした場合、$2472113$ 組しかありません。(証明は公式解説にあります)

左辺の分母・分子が決まれば右辺の値も決まりますから、あらかじめ $A$ に 整数 $x$ が現れる回数を数えておけば、各値が $A$ に出てくる回数を掛けることで、その値の組み合わせを取る選び方が何組あるかわかります。

計算量は $K=2\times{10^5}$ として、 $O(N\log{K})$ です。

約数列挙解法

左辺の分子 $A_i$ を決めたとき、分母としてありえるのは $A_i$ を割り切る値だけです。$A_i$ を割り切る値を高速に全列挙すればいいです。**ある正の整数 $x$ を割り切る正の整数 $y$ のことを、$x$ の約数と呼びます。**約数列挙の計算量は、整数 $L$ に対して$O(\sqrt{L})$ ですから、十分高速です。

計算量は $K=2\times{10^5}$ として、 $O(N\sqrt{K})$ です。全探索解法と同様のアルゴリズムで約数を前計算しておけば、$O(N\log{K})$ になります。

コード

全探索

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    ans = 0
    A_max = 2 * 10 ** 5
    for den in range(1, A_max + 1):
        for num in range(den, A_max + 1, den):
            k = num // den
            ans += C[den] * C[num] * C[k]
    print(ans)


if __name__ == '__main__':
    main()

約数列挙

PyPyで提出してください。

from collections import Counter


def enum_divisors(n):
    """約数列挙 O(√N)"""

    divs_smaller = []
    divs_larger = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            divs_smaller.append(i)
            divs_larger.append(n // i)
        i += 1

    if divs_smaller[-1] == divs_larger[-1]:
        divs_smaller.pop()

    divisors = divs_smaller + divs_larger[::-1]

    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    ans = 0
    for num, cnt in C.items():
        divs = enum_divisors(num)
        for den in divs:
            k = num // den
            ans += cnt * C[den] * C[k]
    print(ans)


if __name__ == '__main__':
    main()

E問題『RLE』

問題ページE - RLE
コーダー正解率:0.1 %
コーダー正解率:0.5 %
コーダー正解率:0.6 %

入力

(省略)

  • $N\le{3000}$
  • 素数 $P$ で割った余りを求める

考察

動的計画法で解けそうです。まずは、単純なDPを考えてみます。

状態

$\mathrm{dp}[i][j]$ : $T$ としては $i$ 文字で、 $S$ としては $j$ 文字である文字列の個数

初期値

$\mathrm{dp}[0][0]=1$

遷移

$T$ に英小文字 $char$、個数 $num$ からなる文字列 $Y$ を追加します。$num$ の $10$ 進表記での桁数を $d$ とすると

  • $T$ としては $d+1$ 文字増える
  • $S$ としては $num$ 文字増える

ことになります。したがって、遷移は $char$ として使える英小文字の種類数を $c$ として

  • $\mathrm{dp}[i+d+1][j+num]+=c\times{\mathrm{dp}[i][j]}$

です。

$c$ は $i=0$ のとき $26$ 、それ以外のとき $25$ です。(直前に使った英小文字と同じ文字は使えないため)

遷移を高速化する

このDPは状態数が $O(N^2)$、遷移が $O(N)$ ですから、計算量が $O(N^3)$ となり間に合いません。

**ある $i,j$ から遷移するとき、桁数 $i+d+1$ が同じで、$j+num$ が連続する区間に同じ値を足していることに着目すると、遷移を高速化できそうです。**具体的には、累積和(いもす法)を使えば、$O(1)$ で区間への一律加算ができます。$d$ は $O(\log{N})$ 通りですから、遷移を $O(\log{N})$ に高速化でき、この問題を解くことができます。

全体の計算量は $O(N^2\log{N})$ です。

コード

def solve():
    N, P = map(int, input().split())
    dp = [[0] * 4100 for _ in range(3100)]
    dp[0][0] = 1
    dp[0][1] = -1
    for i in range(N):
        for j in range(N + 1):
            dp[i][j] += dp[i][j - 1]
            dp[i][j] %= P
        c = 26 if i == 0 else 25
        for j in range(N + 1):
            x = dp[i][j]
            dp[i + 2][j + 1] += c * x
            dp[i + 2][j + 10] -= c * x
            dp[i + 3][j + 10] += c * x
            dp[i + 3][j + 100] -= c * x
            dp[i + 4][j + 100] += c * x
            dp[i + 4][j + 1000] -= c * x
            dp[i + 5][j + 1000] += c * x

    ans = 0
    for i in range(N):
        ans += dp[i][N]
        ans %= P
    return ans


print(solve())

F問題『Ignore Operations』

問題ページF - Ignore Operations
コーダー正解率:0.1 %
コーダー正解率:0.8 %
コーダー正解率:3.0 %

考察

操作 $1$ を行うと、それ以前に行った操作は一切その後に影響を及ぼしません。ある操作 $1$ を無視せず行うのなら、それ以前の操作を無視するのは回数の無駄なので、一切しないべきです。

最後に行う操作 $1$ を採用する操作 $1$ と呼ぶことにします。採用する操作 $1$ を後ろから全探索し、それぞれについて $x$ の最大値を求めればいいです。

まず、採用する操作 $1$ 以降の操作 $1$ はすべて無視しなければいけません。採用する操作 $1$ 以降に操作 $1$ が出現する回数を $m$ とすると、$i$ 回目以降に出現する操作 $2$ のうち、最大で $K-m$ 個を無視できます。

どの操作 $2$ を無視すべきか考えます。

  • $y_i\ge{0}$ は無条件で採用すべき
  • $y_i\lt{0}$ のうち、絶対値が大きいものから優先して無視するのが最適

**無視した操作 $2$ の値を、優先度付きキューを使って絶対値が小さい順に管理します。**符号が負の操作 $2$ はすべて優先度付きキューに入れます。ただし、無視できる回数を超えた場合、キューから一番絶対値の小さい値を取り出して、無視せずに使ったことにします。

コード

from heapq import heappop, heappush

INF = (1 << 62) - 1


def main():
    def solve():
        N, K = map(int, input().split())
        A = [0] * (N + 1)
        flag = [False] * (N + 1)  # i回目の操作が操作1ならTrue
        flag[0] = True  # 0回目にt=1, y=0があることにします
        for i in range(1, N + 1):
            t, y = map(int, input().split())
            A[i] = y
            flag[i] = (t == 1)
        pq = []
        ans = -INF  # 答えの初期値は十分に絶対値の大きい負の値にします(答えは負になる場合もあります)
        s = 0  # ここまで無視しなかった操作2の値の総和
        for i in reversed(range(N + 1)):
            if len(pq) > K:
                s -= heappop(pq)  # 負の値の絶対値を入れたので、無視を取り消した場合は引きます
            if flag[i]:
                ans = max(ans, A[i] + s)
                K -= 1   # この操作1は無視します
                if K < 0:  # 無視できる操作1は最大K個までです
                    break
            else:
                if A[i] < 0:
                    heappush(pq, -A[i])  # 負の値の絶対値、-A[i]をpqに入れます
                else:
                    s += A[i]  # 無視しないほうが良いので、足します
        return ans

    print(solve())


if __name__ == '__main__':
    main()

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
15
Help us understand the problem. What are the problem?