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

posted at

updated at

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

ABC247A,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拡散していただけると喜びます!

目次

ABC247 まとめ
A問題『Move Right』
B問題『Unique Nicknames』
C問題『1 2 1 3 1 2 1』
D問題『Cylinder』
E問題『Max Min』
F問題『Cards』

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

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

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

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

ABC247 まとめ

全提出人数: 9186人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 A------- 100 3分 6319(6113)位
400 ABC----- 600 94分 5039(4842)位
600 A-CD---- 800 103分 4078(3885)位
800 ABCD---- 1000 81分 3142(2952)位
1000 ABCD---- 1000 51分 2316(2127)位
1200 ABCD---- 1000 28分 1670(1482)位
1400 ABCDE--- 1500 79分 1154(973)位
1600 ABCDE--- 1500 50分 793(613)位
1800 ABCDEF-- 2000 86分 523(354)位
2000 ABCDEF-- 2000 62分 337(190)位
2200 ABCDEFG- 2600 127分 214(95)位
2400 ABCDEFG- 2600 85分 134(46)位

色別の正解率

人数 A B C D E F G Ex
3017 96.5 % 51.9 % 62.8 % 23.3 % 1.9 % 0.3 % 0.0 % 0.0 %
1405 98.9 % 85.5 % 94.8 % 75.0 % 7.5 % 1.1 % 0.0 % 0.0 %
1058 97.8 % 92.3 % 96.0 % 91.0 % 26.8 % 4.1 % 0.5 % 0.1 %
728 97.8 % 94.1 % 97.1 % 96.7 % 71.0 % 22.5 % 3.6 % 0.1 %
409 96.8 % 96.8 % 97.1 % 97.6 % 91.9 % 71.4 % 19.1 % 1.0 %
156 88.5 % 85.9 % 87.2 % 87.8 % 85.9 % 84.6 % 53.9 % 9.0 %
32 96.9 % 96.9 % 96.9 % 96.9 % 96.9 % 96.9 % 93.8 % 62.5 %
19 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 94.7 % 94.7 % 89.5 %

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

A問題『Move Right』

問題ページA - Move Right
コーダー正解率:96.5 %
コーダー正解率:98.9 %
コーダー正解率:97.8 %

入力

$S$ : 0,1のみからなる長さ $4$ の文字列

考察

0 + $S$ の $3$ 文字目までを出力すればいいです。

コード

print("0" + S[:3]) でもいいです。下の書き方はfstring(フォーマットストリング)というものを利用しています。使い方を覚えるといろいろと便利なので、気になる方は調べてみてください。

S = input()
print(f"0{S[:3]}")  # fstring

B問題『Unique Nicknames』

問題ページB - Unique Nicknames
コーダー正解率:51.9 %
コーダー正解率:85.5 %
コーダー正解率:92.3 %

入力

$N$ : 人の人数
$s_i,\ t_i$ : 人 $i$ の姓と名

考察

人 $i$ のあだ名の候補は、$s_i$ か $t_i$ です。どちらかを使えるか全探索して、$N$ 人全員にあだ名をつけられるか判定すればいいです。

人 $i$ があだ名 $u$ を使える条件は、自分以外に姓または名が $u$ の人がいないことです。forループで全探索すればいいです。

コード

def judge():
    def judge2(u, idx):
        # 人idxがuをあだ名に使えるか?
        for i in range(N):
            if i == idx: continue  # 自分自身の姓名とは被ってもいいです
            if u in ST[i]:  # u == s or u == tと同じです
                return False
        return True

    N = int(input())
    ST = [input().split() for _ in range(N)]
    for i in range(N):
        si, ti = ST[i]
        if not (judge2(si, i) or judge2(ti, i)):
            return False  # siもtiもあだ名にできなければ、人iにあだ名をつけられないので`No`です
    return True  # 全員にあだ名をつけられたので、`Yes`です


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

C問題『1 2 1 3 1 2 1』

問題ページC - 1 2 1 3 1 2 1
コーダー正解率:62.8 %
コーダー正解率:94.8 %
コーダー正解率:96.0 %

入力

$N$ : $1$ 以上 $16$ 以下の整数

考察

書いているとおりに実装するだけです。

数列のすべてを出力させられる時点で、$N=16$でも数列の長さはそれほど長くなりません。無駄に計算時間がかかる方法でなければなんでもいいので、$S_1={1}$ から順に $S_i$ を求めて、$S_N$ を出力すればいけばいいです。

どうでもいいですが、$S_N$ の長さは $2^{N}-1$ です。($a_{n+1}=2a_{n}+1$ の一般項を求めればわかります)つまり、$S_{16}$ でも長さは $2^{16}-1=65535$ しかありません。

コード

def solve():
    N = int(input())
    S = [[], [1]]

    for i in range(2, N + 1):
        S.append(S[i - 1] + [i] + S[i - 1])
    return S[N]


print(*solve())

D問題『Cylinder』

問題ページD - Cylinder
コーダー正解率:23.3 %
コーダー正解率:75.0 %
コーダー正解率:91.0 %

入力

$Q$ : クエリの数

考察

まず、筒の右からボールを入れ、左からボールを出すので、両端キューdequeを使うべきだとわかります。

ボールを出し入れする数は $1$ クエリあたり最大で $10^9$ 個で、クエリは最大 $2\times{10^5}$ 回ありますから、ボールを $1$ 個ずつ処理していてはとても $2$ 秒以内に解くことはできません。

そこで、$(ボールに書いてある数字,\ ボールの個数)$ のリストをdequeに入れて、塊ごとまとめて処理します。 このアルゴリズムをランレングス圧縮といいます。(ランレングスとは、Run Lengthのことです。そのままですね。日本語では連長圧縮といいます)

クエリ1: ボールを右から筒に入れる

deq.append([x, c])

すればいいです。クエリ $2$ で $c$ (個数)を減らす場合があるので、値を変更できないタプルではなく、変更できるリストで入れましょう。

クエリ2: ボールを筒から取り出す

$c$ 個ボールを取り出すまで、筒からボールを取り出す処理を続けます。必要な変数は以下の $2$ つです。

  • c :あと何個ボールを取り出せばいいか、$0$ になったら終了(クエリの入力で与えられます)
  • sm = 0:取り出したボールに書かれた数の合計、クエリの終了時に出力

まず、deqの一番左にあるボールの塊の情報を得ます。

num, cnt = deq[0]

筒の一番左に、numが書かれたボールがcnt個連続で入っているという意味です。

c >= cnt かどうかで処理が変わります。

c >= cnt の場合

c >= cnt であれば、この塊のボールを全て取り出すことになります。c - cnt >= 0 なので、全て取り出してもボールを取り出しすぎることはないからです。

変数の操作は以下の $2$ つです。

  • sm += num * cntnum が書かれたボールをcnt個取り出すと、num * cnt だけ合計が増えます)
  • c -= cnt

さらに、この塊のボールの個数が $0$ 個になったのですから、deqから削除します。numが書かれたボールが $0$ 個ある』という情報は邪魔なだけです。

具体的には、deq.popleft()を行って、deqの一番左の要素を削除します。

c < cntの場合

c < cnt であれば、この塊のボールを全て取り出す前に、c = 0になります。

ボールを取り出す数は、もちろん c 個です。

  • sm += num * c
  • deq[0][1] -= cdeqの一番左の今見ている塊の、ボールの個数をc個減らします。cnt -= cでは、deqの中身のリストの値は書き変わらないので気をつけてください
  • c = 0

計算量について

クエリ $1$ :deq.append() の計算量は $O(1)$ です。したがって、全体では $O(Q)$ です。
クエリ $2$ の塊削除 : 塊が deq から削除される回数は、最大でもクエリ $1$ で塊をdeqに入れた回数と同じです。当然ですが、入れたものしか出すことはできないからです。これも全体で $O(Q)$ です。
クエリ $2$ の個数書き換え : deqから削除せずに deq[0][1](個数)を書き換える回数は、最大でクエリ $2$ の回数と同じです。この処理が起きたということは、ボールを $c$ 個取り出し終わったということです。つまり、クエリ $2$ ごとに最大で $1$ 回しか起きません。やはり $O(Q)$ です。

以上より、計算量は $O(Q)$ です。

コード

from collections import deque


def main():
    Q = int(input())
    deq = deque()
    for _ in range(Q):
        q, *_a = map(int, input().split())
        if q == 1:
            x, c = _a
            deq.append([x, c])  # xが書かれたボールを右からc個入れる
        else:
            c = _a[0]  # cが0になるまでボールを取り出し続けます
            sm = 0  # 取り出したボールに書かれた数の合計
            while c > 0:
                num, cnt = deq[0]
                if c >= cnt:
                    sm += num * cnt
                    deq.popleft()  # この塊のボールを全部取り出したので、deqから削除します
                    c -= cnt
                else:
                    sm += num * c
                    deq[0][1] -= c  # cntではなく、deq[0][1] を c個減らしてください(cntは、deq[0][1]の値をコピーした別の実体です)
                    c = 0
            print(sm)  # 忘れずに


if __name__ == '__main__':
    main()

おまけ: 同じ数字の塊が連続していたら、まとめられる

例えば、deq = deque[[5, 10]]($5$ が $10$ 個)とします。

このdeqに、[5, 100]を右から追加してみます。今回の問題の方法では、deq = deque[[5, 10], [5, 100]] になります。

同じ数字のボールの塊が $2$ 連続していますから、この $2$ つの塊はまとめられそうです。 つまり、deq = deque[[5, 110]] にすることができます。

この実装をすると、それなりに高速になります。そもそも、競プロの文脈でランレングス圧縮といったときは、この処理を行うのが普通です。

若干ですが実装が長くなるので、今回はこれをせずに楽をしたほうがいいと思います。この処理が必要な問題もありますから、覚えておいて損はありません。

E問題『Max Min』

問題ページE - Max Min
コーダー正解率:1.9 %
コーダー正解率:7.5 %
コーダー正解率:26.8 %

考察

明らかに、$Y\le{A_i}\le{X}$ を満たさない値が入った部分列は、問題文の条件を満たしません。(最大値または最小値が $X$ や $Y$ になりえなくなります)

そこで、$Y\le{A_i}\le{X}$ を満たす複数の連続部分列に分割し、その連続部分列ごとに答えを求めて、足し合わせて全体の答えを求めます。

入っていてはいけない値のことを考えなくてよくなり、問題が単純化されました。具体的には、『$X,Y$ をそれぞれ $1$ つ以上含む連続部分列の数を数える』問題になります。

分割した部分列に対する答えの求め方

$Y\le{P_i}\le{X}$ である要素のみからなる、連続部分列 $P$ に対する答えを求める方法を考えます。この問題は、尺取法で解くことができます。

管理する変数は以下の $2$ つです。

  • 現在の $(L,\ R)$ に含まれる $X,\ Y$ の個数 cx, cy
  • 区間の右端 $R$($L$ はforループで $1$ ずつ増やしていくので、自分で管理しなくていいです)

L=1に固定したときの答えを求める

はじめに $L=1$ に固定して、$X$ と $Y$ がそれぞれ $1$ 個以上含まれるようになるまで、 $R$ を増やして行きます。

そのような $(1,\ R)$ が見つかったとします。$(1,\ R)$ が条件を満たすなら、右端 $R$ を右側に伸ばした $(1,\ R+1),\ (1, R+2),\ \dots$ も条件を満たします。(伸ばしても最大値、最小値は $X,\ Y$ から変わりません)

つまり、連続部分列 $P$ の長さ $P_{len}$ として、答えに $P_{len}-R + 1$ を足せばいいです。

L=2に固定したときの答えは、P_1を消して同じことをする

次に、$L=2$ に固定したときの答えを求めます。まず、$P_1$ が $X$ または $Y$ であれば、cx, cyを $1$ 減らします。

$(2,R-1)$ が条件を満たすことはありませんから、$R$ を減らす必要はありません。よって、同様に 条件を満たすまで $R$ を $1$ ずつ増やして、見つかれば答えに足せばいいです。

$L=3$ 以降も同様の手順で解けます。

すべての分割した列に対してこれを行い、足し合わせれば答え

この処理を、分割した部分列すべてに対して行い、答えを足し合わせたものが全体の答えになります。

実装

$X=Y$ の場合もあるので、if文の書き方に注意しましょう。

コード

from itertools import groupby


def main():
    def solve_partial(P):
        ret = 0
        P_len = len(P)
        cx, cy = 0, 0
        r = 0
        for l in range(P_len):
            while r < P_len and cx * cy == 0:  # cxかcyのどちらかが0なら、cx*cy=0です
                num = L[r]
                if num == X: cx += 1
                if num == Y: cy += 1
                r += 1
            if cx * cy > 0:
                ret += P_len - r + 1
            num = L[l]
            if num == X: cx -= 1
            if num == Y: cy -= 1
        return ret

    N, X, Y = map(int, input().split())
    A = list(map(int, input().split()))

    pred = lambda a: Y <= a <= X  # この2行で分割しています。本質的な部分ではないので短い書き方にしましたが
    B = [list(g) for key, g in groupby(A, key=pred) if key]  # forループで普通にやってもいいです

    ans = 0
    for L in B:
        ans += solve_partial(L)
    print(ans)


if __name__ == '__main__':
    main()

F問題『Cards』

問題ページF - Cards
コーダー正解率:0.3 %
コーダー正解率:1.1 %
コーダー正解率:4.1 %

とても長い公式解説の方法と、愚直解プログラムで出てきた数列を検索する、ズルい簡単な方法のふたつを用意しました。

考察

$P_i$ と $Q_i$ 間に無向辺を貼ったグラフを考えます。このグラフは、各連結成分がサイクル(円形のループ)になっています。$P$ と $Q$ に各数字はちょうど $1$回ずつ出ますから、どの頂点もつながっている辺が $2$ つだけになるからです。

連結成分はUnionFindで管理してください。連結成分ごとに組み合わせ数は独立ですから、各連結成分に対して答えを求めて、掛け合わせれば答えになります。

以下、$1$ つの連結成分に対する答えの求め方を考えます。

辺を選ぶ問題に帰着する

はじめ、グラフの全頂点が白く塗られているものとします。『カードを選ぶ』という行為は、『グラフの辺を選んで、繋がっている $2$ つの頂点を黒く塗る』とみなすことができます。

したがって、『うまく辺を選ぶことで、すべての頂点の色を黒くしたいです。そのような辺の選び方は何通りありますか?』という問題を考えればいいです。

全頂点を黒く塗るための条件を考える

ある頂点 $u$ を黒くするには、『つながっている $2$ つの辺のうち、少なくとも片方が選ばれている』必要があります。言い換えると、『連続する $2$ つの辺であって、どちらも選ばれていないことは許されない』ということです。

辺を連番で表して、単純化する

辺を連番で表すことにします。例として $N=4$ の場合を考えてみます。サイクルグラフですから、$4$ の次に $1$ が来ます。

$12341$

すべての連続する $2$ つの数字について、少なくとも片方が選ばれているような、数字の選び方は何通りあるか?』という問題になりました。$N$ 種類の数字に対するこの問題の答えを、 $G(N)$ と呼ぶことにします。

$G(N)$ は、サイズが $N$ の連結成分に対する元の問題の答えそのものです。

場合分けでループ構造を消す

$4$ の次に $1$ が来るような、ループ構造があると大変見通しが悪いです。そこで、『$1$ を選ぶか選ばないか』で場合分けをします。すると、ループ構造がなくなり、単純な数字の連番に対して同じ問題を解けばよくなります。$N$ 個の数字に対するこの問題の答えを、 $F(N)$ と呼ぶことにします。

場合分けした問題の答えがどちらもわかれば、足すことで $G(N)$ が求められます。

1 を選ぶ場合

$234$ の答えがわかればいいです。つまり、$F(3)$ です。

1を選ばない場合

$2$ と $4$ は必ず選ばなければなりません。よって、$3$ の答えがわかればいいです。$F(1)$ です。

G(N)をFの式で表す

まず、$G(1)=1,\ G(2)=3,\ G(3)=4$ です。(これは愚直解プログラムを書くか、手で計算してください)

$N\ge4$ のとき、$G(N)=F(N-1)+F(N-3)$ です。上記の例のように、$1$ を選ぶ場合が $F(N-1)$ 、$1$ を選ばない場合は $3$ 箇所が確定するので、$F(N-3)$ に対応します。

F(N)を求める

肝心の $F(N)$ の答えを考えます。同様に、追加した $N$ を選ぶか選ばないかで場合分けします。$N=4$ で例示します。

$1234$

4を選ぶ場合

$123$ に対する答えがわかればいいので、$F(3)$ です。

4を選ばない場合

$3$ は選ばなければならないので、$12$ に対する答え、$F(2)$ です。

Fの漸化式

まず、$F(1)=2,\ F(2)=3$ です。($1$ の場合、連続する $2$ 数が存在しないので、選んでも選ばなくてもいいです)

そして、上記の例より $F(N)=F(N-1)+F(N-2)$ です。この漸化式より $F(x)$ を前計算で求めれば、$G(N)=F(N-1)+F(N-3)$ の式にしたがって答えが求められます。

コード

from typing import List

MOD = 998244353


def main():
    N = int(input())
    P = [x - 1 for x in map(int, input().split())]
    Q = [x - 1 for x in map(int, input().split())]

    uf = UnionFind(N)

    for p, q in zip(P, Q):
        uf.unite(p, q)

    F = [0] * (N + 5)
    F[1:3] = 2, 3
    for i in range(3, N + 1):
        F[i] = (F[i - 2] + F[i - 1]) % MOD

    G = [0] * (N + 5)
    G[1:4] = 1, 3, 4

    ans = 1
    for i in range(4, N + 1):
        G[i] = (F[i - 3] + F[i - 1]) % MOD

    for sz in uf.all_sizes():
        ans *= G[sz]
        ans %= MOD
    print(ans)


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の根を取得"""
        xc = x
        while self.parent[x] >= 0:
            x = self.parent[x]
        while xc != x:
            self.parent[xc], xc = x, self.parent[xc]
        return 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


if __name__ == '__main__':
    main()

おまけ:ズルい方法

愚直解プログラムを書いてみます。

from itertools import product


def main():
    def calc(x):
        def judge(L):
            for j in range(x):
                if (L[j % x] | L[(j + 1) % x]) == 0:
                    return 0
            return 1

        ret = 0
        for L in product((1, 0), repeat=x):
            ret += judge(L)
        return ret

    N = 10
    ans = [calc(i) for i in range(1, N + 1)]
    print(*ans, sep=",")


if __name__ == '__main__':
    main()

すると、以下の結果が得られます。

1,3,4,7,11,18,29,47,76,123

これを、OEIS(オンライン整数列辞典)で検索してみます。

A000204 Lucas numbers (beginning with 1) と一致することが明らかになりました。(リュカ数といいます)

$L(n)=L(n-1)+L(n-2)$ with $L(1)=1,\ L(2)=3$ とあるので、この通りに実装すると正解できます。

MOD = 998244353


def main():
    N = int(input())
    P = [x - 1 for x in map(int, input().split())]
    Q = [x - 1 for x in map(int, input().split())]

    uf = UnionFind(N)  # ufのコードは省略

    for p, q in zip(P, Q):
        uf.unite(p, q)

    Lucas = [0] * (N + 5)
    Lucas[1:3] = 1, 3
    for i in range(3, N + 1):
        Lucas[i] = (Lucas[i - 1] + Lucas[i - 2]) % MOD
    ans = 1
    for sz in uf.all_sizes():
        ans *= Lucas[sz]
        ans %= MOD
    print(ans)


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?