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

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

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

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

ABC192 まとめ

全提出人数: 8699人

下の表のデータを見られるアプリ AtCoder Facts を作りました。使ってくれたらよろこびます。

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	ABC---	600	89分	6713(6439)位
400	ABC---	600	49分	5587(5314)位
600	ABC---	600	33分	4641(4369)位
800	ABC---	600	22分	3648(3377)位
1000	ABC---	600	13分	2722(2452)位
1200	ABC-E-	1100	91分	1954(1692)位
1400	ABC-E-	1100	46分	1368(1111)位
1600	ABCDE-	1500	99分	938(688)位
1800	ABC-EF	1700	109分	634(397)位
2000	ABCDEF	2100	107分	412(210)位
2200	ABCDEF	2100	83分	268(102)位
2400	ABCDEF	2100	73分	185(46)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3548	98.2 %	91.2 %	66.0 %	1.2 %	2.1 %	0.3 %
茶	1525	99.5 %	99.4 %	94.3 %	6.4 %	11.8 %	0.9 %
緑	1316	99.5 %	99.5 %	98.1 %	19.8 %	40.4 %	2.7 %
水	753	99.5 %	99.2 %	98.9 %	45.3 %	83.4 %	14.5 %
青	415	100.0 %	100.0 %	99.8 %	74.5 %	95.4 %	59.8 %
黄	206	96.1 %	96.1 %	96.6 %	89.8 %	94.7 %	88.3 %
橙	50	100.0 %	100.0 %	100.0 %	94.0 %	96.0 %	94.0 %
赤	19	100.0 %	100.0 %	100.0 %	94.7 %	94.7 %	94.7 %

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

簡易解説

A問題 (8571人AC)『Star』

$100$ から $X$ を $100$ で割った余りを引いた数です。

B問題 (8193人AC)『uNrEaDaBlE sTrInG』

isupper()メソッドとislower()メソッドを使うといいです。

C問題 (6985人AC)『Kaprekar Number』

$K$ は最大 $10^5$ なので、書かれている通り $a_K$ まで $1$ 項ずつ計算すればいいです。

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

『$n$ 進法表記の数としてみなして得られる値のうち、$M$ 以下であるものは何種類あるでしょうか？』という問題です。

『種類数』 です。

$X$ の長さが $1$ のとき、何進数表記の数としてみなしても同じ値になりますから、答えは $0$ か $1$ 種類です。（$0$ か $∞$ ではありません！）
$X$ の長さが $2$ 以上のとき、$X$ を $n$ 進数表記とみなしたときの値を $f(n)$ とします。
$f(n)$ は狭義単調増加です。（$n$ が増えると、$f(n)$ の値は必ず増加する）
$1$ ずつ増やして答えを調べるとTLEになりますが、単調増加なので二分探索を使うことでACできます。

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

ダイクストラ法で解けます。

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

$1$ ～ $N$ 個すべてについて $3$ 次元DPをすれば、$O(N^4)$ でACできます。（PyPyならギリギリ通ります）

私（うにだよ）の結果

D問題は、誤読を誘うだけのつまらない問題だと思いました（個人の感想）

絶対に自分がおかしいと思いながら10回か20回読んだのに、種類数であることに気づかなかった私が悪いです🥺

A問題『Star』

問題ページ：A - Star
灰コーダー正解率：98.2 %
茶コーダー正解率：99.5 %
緑コーダー正解率：99.5 %

考察

$100$ 枚コインを集めると1UPするゲームで、あと何枚で1UPするか求めてください、といっています。

次の $100$ の倍数まであといくつコインが必要か知りたいです。つまり、『$100 - (今のコイン数の下二桁)$』が答えです。

『今のコイン数の下二桁』は、『今のコイン数を$100$ で割った余り』です。

このような問題では、『$X$ がちょうど $100$ の倍数（余りが $0$）』の場合に、答えが特別にならないか注意が必要です。

問題文に『$X$ が $100$ の倍数の場合は、コインを累計で $X$ 枚集めたことに対するご褒美はすでにもらったとします』とあります。ですので、$X$ が $100$ の倍数のときの答えは $100$ です。場合分けしなくても大丈夫です。

コード

X = int(input())
print(100 - X % 100)

B問題『uNrEaDaBlE sTrInG』

問題ページ：B - uNrEaDaBlE sTrInG
灰コーダー正解率：91.2 %
茶コーダー正解率：99.4 %
緑コーダー正解率：99.5 %

実装

書かれているとおりに判定すればいいです。

スライスを使って、文字列$S$ を奇数番目の文字列 $A$ と偶数番目の文字列 $B$ に分割します。

$2$ つの文字列に対して、

A.islower()で、奇数番目の文字列がすべて小文字か判定
B.isupper()で、偶数番目の文字列がすべて大文字か判定

します。どちらも True ならば 'Yes' で、そうでなければ 'No'です。

ただし、$S$ が $1$ 文字のとき、$B$ は空文字列になります。空文字列に対してisupper()メソッドを使うと、falseが返ってきます。

これでは $S$ が小文字 $1$ 文字のとき正しい答えにならないので、場合分けする必要があります。（入力例3が合わないので、確かめれば気づけます）

コード

S = input()

if len(S) == 1:
    # 空文字列に対してisupper()メソッドを使うとfalseが返るので正しく判定できません
    if S.islower():
        print("Yes")
    else:
        print("No")

else:
    A = S[::2]  # Sの先頭から奇数番目の文字
    B = S[1::2]  # Sの先頭から偶数番目の文字

    if A.islower() and B.isupper():
        print("Yes")
    else:
        print("No")

C問題『Kaprekar Number』

問題ページ：C - Kaprekar Number
灰コーダー正解率：66.0 %
茶コーダー正解率：94.3 %
緑コーダー正解率：98.1 %

考察

この問題は、書かれているとおりに $K$ 回計算すればACできます。どうやって実装するか考えましょう。

ある数字 $x$ に対する $g_1(x), g_2(x)$　がわかればいいので、$g_1(x), g_2(x)$　を求める関数を実装できればいいです。

実装

この関数を calc(x) とします。

数字 $x$ を str(x) で文字列に変換
sorted()を使って、数字が大きい順、小さい順に並び替えたリストを作る
''.join()を使って、文字列に戻す
int()を使って、数字に戻す
引き算して結果を返す

具体的には以下のコードになります。

def calc(x):
    s = str(x)
    g1 = int("".join(sorted(s, reverse=True)))
    g2 = int("".join(sorted(s)))
    return g1 - g2

具体例

$x = 314$ を例に、順を追ってこのコードを説明します。上のコードではg1とg2を求める部分で複数のことを同時にやっていてわかりづらいので、1ステップごとに分けて説明します。

ans = calc(314) # 314の次、297になります

文字列に変換します。

s = str(x) # str型 '314'

sorted() を使って数字を大きい順、小さい順に並べたリストを作ります。大きい順は reverse=True というキーワード引数を渡すとできます。

l1 = sorted(s, reverse=True) # str型のリスト ['4', '3', '1']
l2 = sorted(s) # str型のリスト ['1', '3', '4']

''.join()を使って、文字列に戻します。

t1 = ''.join(l1)  # str型 '431'
t2 = ''.join(l2)  # str型 '134'

int()を使って整数に変換します。（'0' が含まれている場合でも、g1の先頭の'0'は無視してくれるので問題ありません）

g1 = int(t1)  # int型 431
g2 = int(t2)  # int型 134

あとは引き算をすればいいです。

ret = g1 - g2  # 431-134=297 
return ret

コード

def calc(x):
    s = str(x)
    g1 = int("".join(sorted(s, reverse=True)))
    g2 = int("".join(sorted(s)))
    return g1 - g2

N, K = map(int, input().split())

ans = N
for _ in range(K):
    ans = calc(ans)

print(ans)

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

目次