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

AtCoder Beginner Contest 196のA,B,C問題を、Python3でなるべく丁寧に解説していきます。

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

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

ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo

よかったらLGTMしていただけると、私のやる気がでます！

目次

ABC196 まとめ
A問題『Difference Max』
B問題『Round Down』
C問題『Doubled』

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

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

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

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

ABC196 まとめ

全提出人数: 8630人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	15分	6460(6240)位
400	ABC---	600	107分	5299(5080)位
600	ABC---	600	63分	4345(4129)位
800	ABC---	600	38分	3367(3154)位
1000	ABC---	600	20分	2476(2263)位
1200	ABC---	600	6分	1748(1537)位
1400	ABCD--	1000	65分	1202(996)位
1600	ABCD--	1000	24分	809(612)位
1800	ABCDE-	1500	102分	527(352)位
2000	ABCDE-	1500	73分	339(186)位
2200	ABCDE-	1500	47分	211(91)位
2400	ABCDEF	2100	106分	125(41)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3749	97.3 %	84.7 %	42.9 %	1.6 %	0.2 %	0.0 %
茶	1496	99.4 %	98.7 %	85.0 %	9.2 %	0.9 %	0.4 %
緑	1212	99.4 %	99.2 %	92.4 %	30.1 %	7.5 %	0.5 %
水	690	99.6 %	99.4 %	97.2 %	57.2 %	28.3 %	2.2 %
青	388	100.0 %	99.7 %	99.2 %	85.6 %	65.5 %	11.9 %
黄	183	96.7 %	96.7 %	97.3 %	84.7 %	84.7 %	36.1 %
橙	34	97.1 %	97.1 %	100.0 %	100.0 %	100.0 %	70.6 %
赤	6	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %

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

簡易解説

A問題 (8435人AC)『Difference Max』

『引かれる数』を最大にして、『引く数』を最小にすればいいです。

B問題 (7725人AC)『Round Down』

入力を小数で受け取ると壊れます。文字列として受け取って小数点以下を削除して出力しましょう。

C問題 (5503人AC)『Doubled』

制約が大きく全探索ができないように見えますが、問題文のように前半部と後半部で数字を分けると全探索できます。

D問題 (1517人AC)『Hanjo』[この記事では解説しません]

深さ優先探索（DFS）で解けます。
『8クイーン問題』をやったことがあると、この類の問題をDFSで解けることに気づけます。
itertoolsモジュールをうまく使っても解けるようです。

E問題 (765人AC)『Filters』[この記事では解説しません]

答えをグラフにすると単純な形になるので、左端と右端を管理すると良いです（公式解説を見てください）

F問題 (173人AC)『Substring 2』[この記事では解説しません]

問題文を開いてすらいないのですが、畳込みを使うってツイッターでみました。

私（うにだよ）の結果

D問題が得意よりの問題だったので勝ったかと思いましたが、現実はそう甘くありませんでした。

D問題のこの汚物のようなコードを、書き始めてから7分でバグなしで書いてACできたのは結構すごくないですか。（実装が汚すぎるので、参考にはしないでね）

A問題『Difference Max』

問題ページ：A - Difference Max
灰コーダー正解率：97.3 %
茶コーダー正解率：99.4 %
緑コーダー正解率：99.4 %

考察

$x - y$ を最大にしたいです。そのために、$x$ をできるだけ大きく、$y$ をできるだけ小さくしたいです。

$a\le{x}\le{b}$ なので、$x=b$ にします。

$c\le{y}\le{d}$ なので、$y=c$ にします。

つまり、$b-c$ が答えです。

コード

    a, b = map(int, input().split())
    c, d = map(int, input().split())
    print(b - c)

B問題『Round Down』

問題ページ：B - Round Down
灰コーダー正解率：84.7 %
茶コーダー正解率：98.7 %
緑コーダー正解率：99.2 %

考察

入力を普通の数字として受け取って、int関数などで切り捨てようとすると壊れます。コンピュータが小数点のある数を扱うときに通常使う浮動小数点数では、桁数の大きい数を正確に表すことができないからです。

壊れる具体例を見てみましょう。

>>> X = 123456789123456789123456789.2738149702983614896234989837148979
>>> int(X)
123456789123456791337762816 # おかしい！

では、どうすれば良いのでしょうか。整数部分というのは小数点の左側の数字のことです。そこで、文字列として受け取って、split('.')を使って小数点部分で分割し、左側だけ出力すれば良いです。

>>> X = '123.45'
>>> A = X.split('.')
>>> A
['123', '45']  # 要素数2のリストです。
>>> A[0]  # A[0]が整数部分です
'123'

'.'が存在しない場合にsplit('.')をしてもエラーにならないので、if文で分ける必要はありません。

>>> X = '123'
>>> A = X.split('.')
>>> A
['123']  # 要素数1のリストです。このまま出力するとWAです。
>>> A[0]  # A[0]で中身を取り出しましょう。
'123'

コード

    X = input()
    ans = X.split('.')[0]  # splitで返ってくるのはリストなので、最初の要素を取得しましょう。
    print(ans)

オーバーキル感はありますが、Decimalを使っても解けます。このとき、文字列として受け取ったものを直接Decimalに変換するようにしてください。浮動小数点数として受け取ってからDecimalにすると、既に誤差のある数字がDecimal型になってしまうので意味がありません。

from decimal import Decimal
X = Decimal(input())
print(int(X))

C問題『Doubled』

問題ページ：C - Doubled
灰コーダー正解率：42.9 %
茶コーダー正解率：85.0 %
緑コーダー正解率：92.4 %

考察

問題文を読んでみます。

『以下の条件を満たす $1$ 以上 $N$ 以下の整数 $x$ は何個あるでしょうか？』

『$x$ の十進表記 (先頭に $0$ を付けない) は偶数桁であり、その前半と後半は文字列として等しい。』

上の条件を満たす数とはどのような数か、小さい順にあげてみます。

$11,22,33,44,55,66,77,88,99,1010,1111,1212,1313,1414,....$

つまり ○× | ○× の形になっている数のことです。

$N \lt{10^{12}}$ です。$N$ 以下のすべての数に対して条件を満たすか確認するとTLEになります。

しかし、上に書いたように、条件を満たす数だけを小さい順に列挙することは簡単にできます。$N$ は最大でも $12$ 桁です。$6$ 桁の数を $2$ 回繰り返すと $12$ 桁になります。つまり、最大でも $999,999$ まで全探索すればいいです。これならTLEになりません。

実装

条件を満たす数の作り方は以下のようにすると良いです。

1. 繰り返す数をiとして、s = str(i) * 2 でまず文字列で作る
2. x = int(s)として、整数にし、Nと比較できるようにする

$i=123$ の 場合で具体例を見てみます。

>>> i = 123
>>> s = str(i) * 2
>>> s
'123123'
>>> x = int(s)
>>> x
123123
>>> N = 100000
>>> x <= N:  # 整数同士なので比較できます
False

コード

def solve():
    cnt = 0
    i = 1  # 1からスタートです
    while True:
        s = str(i) * 2
        x = int(s)
        if x <= N:
            cnt += 1
        else:
            break
        i += 1
    return cnt


N = int(input())
print(solve())

forループを使う実装でも良いです。ただし、ケアレスミスをしやすい部分が多いので注意してください。

def solve():
    # rangeはstart=1で、endは10**6以上の適当な数にしましょう。
    # ギリギリちょうどの数にしようとするとケアレスミスの恐れがあります
    # 途中でreturnしてしまうので、無駄でも大きいくらいにしておくといいです。
    for i in range(1, 10 ** 7):
        s = str(i) * 2
        x = int(s)
        if x > N:
            # i番目の候補 x がダメだったので、i-1個が答えです
            return i - 1

N = int(input())
print(solve())