ABC251のA,B,C,D,E問題を、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や拡散していただけると喜びます！

ABC251 まとめ

全提出人数: 8587人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	A-------	100	4分	5881(5678)位
400	A-C-----	400	20分	4746(4546)位
600	ABC-----	600	50分	3807(3614)位
800	ABC-----	600	28分	2920(2728)位
1000	ABC-----	600	16分	2141(1953)位
1200	ABCD----	1000	30分	1520(1334)位
1400	ABC-E---	1100	58分	1055(870)位
1600	ABCDE---	1500	72分	715(539)位
1800	ABCDEF--	2000	100分	446(303)位
2000	ABCDEF--	2000	73分	282(157)位
2200	ABCDEF--	2000	55分	190(78)位
2400	ABCDEF--	2000	42分	125(37)位

色別の正解率

色	人数	A	B	C	D	E	F	G	Ex
灰	2968	98.0 %	50.6 %	44.1 %	1.8 %	2.1 %	0.2 %	0.0 %	0.0 %
茶	1407	98.9 %	91.8 %	91.8 %	6.4 %	7.6 %	0.6 %	0.1 %	0.0 %
緑	1111	98.6 %	96.6 %	96.2 %	18.0 %	30.0 %	3.8 %	0.0 %	0.0 %
水	633	97.8 %	97.0 %	97.2 %	38.4 %	71.4 %	23.4 %	0.5 %	0.0 %
青	369	97.3 %	97.3 %	97.0 %	65.0 %	92.4 %	68.8 %	5.4 %	0.8 %
黄	158	89.9 %	88.6 %	89.9 %	79.8 %	87.3 %	81.0 %	27.2 %	1.9 %
橙	29	86.2 %	86.2 %	86.2 %	79.3 %	82.8 %	89.7 %	41.4 %	6.9 %
赤	21	90.5 %	90.5 %	90.5 %	90.5 %	90.5 %	90.5 %	90.5 %	38.1 %

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

A問題『Six Characters』

問題ページ：A - Six Characters
灰コーダー正解率：98.0 %
茶コーダー正解率：98.9 %
緑コーダー正解率：98.6 %

入力

$S$ : 英小文字からなる長さ $1$ 以上 $3$ 以下の文字列

考察

$S$ を適当に $10$ 回くらい繰り返した文字列を作って、先頭から $6$ 文字だけ出力すればいいです。

コード

S = input()
T = S * 10
print(T[:6])

B問題『At Most 3 (Judge ver.)』

問題ページ：B - At Most 3 (Judge ver.)
灰コーダー正解率：50.6 %
茶コーダー正解率：91.8 %
緑コーダー正解率：96.6 %

入力

$N$ : おもりの数
$W$ : $W$ 以下の正整数で、良い整数が何個あるか答える
$A_i$ : $i$ 番目のおもりの重さは $A_i$

$1\le{N}\le{300}$

考察

$N$ は最大で $300$ です。$300$ 個から $3$ 個おもりを選ぶ方法は、$_{300}\mathrm{ C }_{3}=4455100$ 通りしかないので、三重ループでおもりの選び方を全探索して、作れる良い整数を調べることができます。

選ぶおもりは $3$ 個以下なので、$1$ 個選ぶ場合と $2$ 個選ぶ場合も考えなければなりません。$3$ 種類の処理を書くのは面倒なので、重さが $0$ のおもりが $2$ つあることにします。**すると、重さが $0$ のおもりを $2$ 個選ぶのはおもりを $1$ 個選ぶことに、重さが $0$ のおもりを $1$ 個選ぶのはおもりを $2$ 個選ぶことに対応します。

コード

def solve():
    N, W = map(int, input().split())
    A = list(map(int, input().split())) + [0, 0]
    good = [False] * (W + 1)

    for k in range(N + 2):  # 2個重さ0のおもりを追加したのでN+2です
        for j in range(k):
            for i in range(j):
                w = A[i] + A[j] + A[k]
                if w <= W:
                    good[w] = True
    return good.count(True)


print(solve())

itertoolsモジュールのcombinationsを使うと実装が簡単になります。

from itertools import combinations


def solve():
    N, W = map(int, input().split())
    A = list(map(int, input().split())) + [0, 0]
    good = [False] * (W + 1)

    for x, y, z in combinations(A, 3):
        w = x + y + z
        if w <= W:
            good[w] = True
    return good.count(True)


print(solve())

C問題『Poem Online Judge』

問題ページ：C - Poem Online Judge
灰コーダー正解率：44.1 %
茶コーダー正解率：91.8 %
緑コーダー正解率：96.2 %

入力

$N$ : 提出の個数
$S_i,T_i$ : $i$ 番目の提出は文字列 $S_i$ で、得点は $T_i$

考察

前から順番に見ていって、最優秀賞の番号・得点を更新していくことにします。

オリジナルな提出という条件がなければ、最高得点を更新したとき一緒に提出番号も更新するだけです。ただし、同点は先に出た提出が優先されます。

オリジナルな提出という条件を加えて考えます。 オリジナルな提出とは、文字列が既出ではないということです。 そこで、出てきた文字列を記録しておいて、提出ごとに文字列が既出かどうかを判定しましょう。既出ならばオリジナルではないので最優秀賞にはなりえず、そうでなければ最優秀賞になりえます。他の部分は条件がない場合と同じ手順で判定できます。

既出の文字列の記録には、set型を使います。 この型は、要素の追加・存在確認を $O(1)$ で行えます。list型を使うと、要素の存在確認が要素数 $K$ に対して $O(K)$ と低速なため、TLEになります。

コード

def main():
    N = int(input())
    seen = set()  # 既に出た文字列を管理
    max_t = -1  # 0点の提出が最優秀賞になることもあるので注意
    ans = 0  # 暫定の最優秀賞の提出番号
    for i in range(1, N + 1):
        s, _t = input().split()
        t = int(_t)
        if s in seen:  # 既出なので判定しません
            continue
        seen.add(s)  # 最優秀賞でなくても、既出判定には用いられます
        if max_t < t:  # 同点なら早いほうが最優秀賞ですから、不等号は<です
            max_t = t
            ans = i
    print(ans)


if __name__ == '__main__':
    main()

D問題『At Most 3 (Contestant ver.)』

問題ページ：D - At Most 3 (Contestant ver.)
灰コーダー正解率：1.8 %
茶コーダー正解率：6.4 %
緑コーダー正解率：18.0 %

入力

$W$ : $1$ 以上 $W$ 以下のすべての正整数が良い整数であるおもりの組を、問題文の条件に従って構築する

$1\le{W}\le{10^6}$

考察

10^6の答えだけ求めれば良い

はじめに重要なことを言うと、この問題は最も条件が厳しい $W=10^6$ に対する答えを求める問題です。 なぜなら、$W=10^6$ の答えは、すべての $1\le{W}\lt10^6$ に対する答えにもなるからです。入力を無視して、$W=10^6$ としたときの答えを出力すればいいです。

問題文を要約するとこうなります。

『異なるおもりを最大 $3$ 個まで選び、選んだおもりの重さの和で整数を作ります。この方法で $1$ 以上 $10^6$ 以下のすべての正整数を作ることができるように、最大 $300$ 個の重さが正整数のおもりの組を構築してください。』

使えるおもりは 3個、数字は6桁以下

$10^6$ は唯一の $7$ 桁の数ですが、それ未満の数はすべて $6$ 桁以下の数です。使えるおもりは $3$ つまでですから、おもり $1$ つにつき $2$ 桁を担当させたくなります。

適当な $6$ 桁以下の整数を、$6$ 桁に $0$ 埋めして並べて眺めてみます。

なんとなく$2$ 桁ずつ区切りしたくなるので、してみます。

58|91|65
00|50|40
49|25|30
34|38|18
76|66|41

各ブロックは $00$ ～ $99$ の $100$ 種類の値をとります。$3$ ブロックあって、取りうる値が $100$ 種類ですから、 $300$ 個のおもりで各ブロックの値を表現できそうに思えます。実際は、$00$ はおもりを選ばなければいいので、重さ $0$ のおもりを用意する必要はありません（そもそも重さが正整数の条件に違反するのでWAです）。

つまり、各ブロックを $01～99$ にできる $99\times3=297$ 種類のおもりがあれば、$000001～999999$ の値をすべて作ることができます。

具体的には、$1\le{i}\le{99}$ のすべての整数に対して、重さ $i,100i,10000i$ のおもりを作ればいいです。実際に並べてみると

$1,2,3,\dots,98,99$
$100,200,300,\dots,9800,9900$
$10000,20000,30000,\dots,980000,990000$

となります。

このおもりの組で例えば

$589165=580000+9100+65$
$5040=5000+40$
$492530=490000+2500+30$

などとすれば、$3$ つまでおもりを選んで $999999$ 以下の正整数をすべて作れます。

**ただし、これでは $7$ 桁の $10^6$ を作れません。**あと $3$ 個おもりを追加できるので、$1\le{i}\le{100}$ で $300$ 個おもりを作るのがいいです。いらないおもりもできますが、確実に $100\times{10000}=10^6$ のおもりが作られます。

コード

とくに意味はありませんが、このコードはどのような入力に対しても同じ出力を返すので、手元で出力した答えを文字列として貼り付けて出力してもACできます。

def main():
    W = int(input()) # 使わない
    ans = []
    for i in range(1, 101):
        ans.extend((i, 100 * i, 10000 * i))
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    main()

E問題『Takahashi and Animals』

問題ページ：E - Takahashi and Animals
灰コーダー正解率：2.1 %
茶コーダー正解率：7.6 %
緑コーダー正解率：30.0 %

入力

（省略）

考察

同じ動物には $1$ 度だけ餌をやればいいので、同じ行動を $2$ 回以上する意味はありません。

動的計画法（DP) で解けそうですが、問題がループ構造になっていて扱いづらいです。なんとかしてループを解消しましょう。

動物 $1$ に着目します。動物 $1$ に餌をあげられる行動は、行動 $1$ と行動 $N$ の $2$ つだけです。このうち、少なくとも片方はしないといけません。

そこで、

行動 $1$ を必ず行う場合
行動 $N$ を必ず行う場合

の $2$ パターンに分けて考えます。すると、各パターンの答えは以下のループ構造が消滅した問題を解けばわかります。

行動 $2$ ～行動 $N$ を使えて、動物 $3$ ～動物 $N$ すべてに餌をあげる（行動 $2$ は動物 $3$、行動 $N$ は動物 $N$ のみに餌をあげる）
行動 $1$ ～行動 $N-1$ を使えて、動物 $2$ ～動物 $N-1$ すべてに餌をあげる（行動 $1$ は動物 $2$、行動 $N-1$ は動物 $N-1$ のみに餌をあげる）

dp

$\mathrm{dp}[i]$ : 動物 $1$ ～ $i$ すべての動物に餌をあげたときにかかる費用の合計の最小値（$i+1$ に餌をあげているかは考慮しない）

初期値

パターン $1$ : $\mathrm{dp}[1]=\mathrm{dp}[2]=A[1]$
パターン $2$ : $\mathrm{dp}[0]=\mathrm{dp}[1]=A[N]$（動物 $2$ の $2$ 匹前が初期値でないと、行動 $1$ で遷移できないため）

遷移

$\mathrm{dp}[i]=\mathrm{min}(\mathrm{dp}[i-2]+A[i-1],\mathrm{dp}[i-1]+A[i])$

行動 $i-1$ は動物 $i-1$ と $i$ に餌をやるので、 $i-2$ から
行動 $i$ は動物 $i$ と $i+1$ に餌をやるので、$i-1$ から（$i+1$ に餌をやった情報は消えますが、必要なら次の $\mathrm{dp}[i+1]$ の更新で考慮されます）

コード

INF = (1 << 62) - 1


def main():
    def solve1():
        dp = [INF] * (N + 1)
        dp[1], dp[2] = A[1], A[1]
        for i in range(3, N + 1):
            dp[i] = min(dp[i - 2] + A[i - 1], dp[i - 1] + A[i])
        return dp[N]

    def solve2():
        dp = [INF] * (N + 1)
        dp[0], dp[1] = A[N], A[N]
        for i in range(2, N):
            dp[i] = min(dp[i - 2] + A[i - 1], dp[i - 1] + A[i])
        return dp[N - 1]

    N = int(input())
    A = [INF] + list(map(int, input().split()))
    print(min(solve1(), solve2()))


if __name__ == '__main__':
    main()

おまけ: 牛ゲー

この問題は動物を頂点、行動を辺としたグラフの最短経路問題として解くこともできます。

通称『牛ゲー』と呼ばれるテクニックです。ABC-Gレベルの題材ですが、興味のある方は調べてみてください。（蟻本に載っている牛の問題が名前の由来です）

INF = (1 << 62) - 1

from heapq import heappop, heappush


def dijkstra(G, start):
    N = len(G)
    dist = [INF] * N
    dist[0] = 0
    pq = [(0, start)]
    while pq:
        cost, u = heappop(pq)
        if dist[u] < cost:
            continue
        for v, d in G[u]:
            new_cost = cost + d
            if dist[v] > new_cost:
                dist[v] = new_cost
                heappush(pq, (new_cost, v))
    return dist


def main():
    def solve(A):
        G = [[] for _ in range(N + 10)]  # 行動NのN-1->N+1に注意
        for i, x in enumerate(A):
            G[i].append((i + 2, x))  # 2つ先の頂点までコストxで行ける
        for i in range(N + 9):
            G[i + 1].append((i, 0))  # 戻るのは無料（行動1,2を使うとき、頂点0->2->1->3と戻る必要がある）
        dist = dijkstra(G, 0)  # 何の工夫もないただのダイクストラです
        return dist[N]  # 0 -> Nのコストが答え

    N = int(input())
    A = list(map(int, input().split()))  # 初動は行動1
    B = A[1:] + A[:1]  # 初動を行動Nにするため、行動Nを先頭に移す
    print(min(solve(A), solve(B)))  # 行動1を必ず使う場合と、行動Nを必ず使う場合で小さいほうが答え


if __name__ == '__main__':
    main()

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

目次

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