ABC247のA,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 まとめ

全提出人数: 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 * cnt （num が書かれたボールを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] -= c（deqの一番左の今見ている塊の、ボールの個数を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()

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

目次

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