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

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

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

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

D,E問題はこちら：【AtCoder解説】PythonでABC171のD,E問題を制する！

目次

AtCoder Beginner Contest 171 まとめ
A問題 『αlphabet』
B問題 『Mix Juice』
C問題 『One Quadrillion and One Dalmatians』

AtCoder Beginner Contest 171 まとめ

全提出人数: 10526人

パフォ	AC	点数	時間	順位	目安
400	ABC---	600	89分	6654位	茶パフォ
600	AB-D--	700	51分	5424位	8回で茶レート
800	AB-DE-	1200	107分	4153位	緑パフォ
1000	ABCDE-	1500	87分	2992位	8回で緑レート
1200	ABCDE-	1500	57分	2059位	水パフォ

(参考)私：2842位 パフォ1029 寝起きで出たらえらいことになりました

A問題 (10416人AC) 『αlphabet』

PAST3の1問目で、似たような問題が出ました。

B問題 (10164人AC) 『Mix Juice』

ソートして足せばいいです。

C問題 (5522人AC) 『One Quadrillion and One Dalmatians』

26進数をちょっとひねった問題です。

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

数列にどの数字が何個あるか、Counterで管理するといいです。

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

どんな数字も自分自身とXORを取ると0になることを知っていると、解けます。

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

入力の右端1文字の位置を固定すると組み合わせ数が計算できるので、右端1文字のすべての位置について計算して、足し合わせます。

A問題 『αlphabet』

問題ページ：A - αlphabet
むずかしさ：★☆☆☆☆
ポイント：文字列の扱い

大文字にして比較すると楽です。

解き方

1. 実装を考える

ステップ1：実装を考える

if s in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':なら'A'としてもいいですが、めんどくさいです。

「入力」と「入力を大文字にしたもの」が同じなら'A'で、違うなら'a'とすれば楽です。

コード

s = input()

if s == s.upper():
    print("A")
else:
    print("a")

B問題 『Mix Juice』

問題ページ：B - Mix Juice
むずかしさ：★★☆☆☆
ポイント：Pythonの文法

ソートすれば小さい順になります。

解き方

1. 解法を考える

ステップ1： 解法を考える

1個ずつ買うので、最小の金額は、安いものから順に$K$ 個買う場合です。

つまり、入力を昇順（安い順）にソートして、先頭の$K$個の合計が答えです。

コード

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
ans = sum(a[:k])
print(ans)

C問題 『One Quadrillion and One Dalmatians』

問題ページ：C - One Quadrillion and One Dalmatians
むずかしさ：★★★★★
ポイント：n進数の求め方

基本的には数字を『26進数』で表す問題ですが、$0$に対応する文字がありません。

解き方

1. 数式で表してみる
2. 0桁目を求める
3. 次の桁を求める
4. 繰り返して一番上の桁まで求める
5. まとめ

ステップ1：数式で表してみる

一番下の桁は『0桁目』としたほうがわかりやすいので、『0桁目』とすることにします。

$0$に対応する文字があれば、$26$で割った余りを求めていけば解けます。（もし知らなければ、「n進数 変換」など検索してみてください）

しかし、$0$がないので、単純に$26$で割っていくだけでは求められません。

やりたいことを数式で表してみる

方針を立てるために、やりたいことを数式で表してみます。しっかり理解しなくとも、なんとなくこんな感じだな、くらいの理解で十分です。

この問題の出力の形式で数字を表したときの桁数を、適当に $l+1$ 桁とします。実際に何桁か意識する必要は一切ないです。

$1\le{x_i}\le{26}$（a～zに対応します）としたとき、

$n = 26^l\times{x_l} + 26^{l-1}\times{x_{l-1}}+\cdots+26^{2}\times{x_2}+26\times{x_1}+x_0$

の、各 $x_i$ を全て求めたいです。

これだけだとよくわからないので、例をあげてみます。

例1：b = 2

$2 = 2$

bです。

例2: aa = 27

$27 = 26\times1+1$

aaです。

例3：jjddja = 123456789

$123456789=26^{5}\times10+26^{4}\times10+26^{3}\times4+26^{2}\times4+26\times10+1$

10番目はj、4番目はd、1番目はaなので、jjddjaです。

例4：zz = 702

$702=26\times26+26$

zzです。

ステップ2：0桁目を求める

式を見ていると、0桁目の ${x_0}$ 以外には$26$が掛けられていることがわかります。そこで、

$n = 26^l\times{x_l} + 26^{l-1}\times{x_{l-1}}+\cdots+26^{2}\times{x_2}+26\times{x_1}+x_0$

の右辺を変形して、0桁目以外を$26$でくくってみます。

0桁目以外を26でくくってみる

つまり、

$n=26(26^{l-1}\times{x_l}+26^{l-2}\times{x_{l-1}}+\cdots+x_1)+x_0$

です。目障りなので、$S_{0}=26^{l-1}\times{x_l}+26^{l-2}\times{x_{l-1}}+\cdots+x_1$と置き換えてみます。すると、

$n=26\times{S_0}+x_0$

になりました。

26で割った余りが0桁目

$26\times{S_0}$は、26で割り切れます。ということは、$n$ を $26$で割った余りが、$x_0$ になります。

z = 26の余りは0ということに注意

ただし、$x_0$がz、つまり$26$の場合は、26で割った余りが0になって、$x_0$と26で割った余りが一致しません。

a～yは$1～25$なので、他に余りが$0$になる文字はありません。もし余りが$0$になったら、$x_0=26$と置き換えればいいです。

ステップ3：次の桁を求める

0桁目が求められたので、1桁目の$x_1$も、同じような感じで求めたいです。

x_0を引いてみる

$x_0$（既に求めています）を両辺から引いてみます。つまり、移項します。

$n-x_0=26(26^{l-1}\times{x_l}+26^{l-2}\times{x_{l-1}}+\cdots+x_1)$

26で割り切れるので、割ってみる

$x_0$は、$n$を$26$で割った余りです。ということは、$n-x_0$の余りは$0$です。この考えは頻出なので、もし知らなければ調べてみてください。

つまり、$n-x_0$は、$26$で割り切ることができます。そこで、両辺を$26$で割ってみます。

$\frac{n-x_0}{26}=26^{l-1}\times{x_l}+26^{l-2}\times{x_{l-1}}+\cdots+26\times{x_2}+x_1$

です。これも目障りなので、$n_1=\frac{n-x_0}{26}$とします。

$n_1=26^{l-1}\times{x_l}+26^{l-2}\times{x_{l-1}}+\cdots+26\times{x_2}+x_1$

最初に見た感じの式になりました。

また26でくくってみる

そこで、また$26$でくくってみます。

$n_0=26(26^{l-2}\times{x_l}+26^{l-3}\times{x_{l-1}}+\cdots+26\times{x_{3}}+x_2)+x_1$

$n_0=26\times{S_{1}}+x_1$

同じように、$x_1$は、$n_0$を$26$で割った余りです。

ステップ4：繰り返して一番上の桁まで求める

これを繰り返していると、最終的に、

$n_l=x_l$

になります。両辺から$x_l$を引くと、

$n_l-x_l=0$

と、右辺が$0$になって、求めるものがなくなりました。

つまり、一連の手順を右辺が$0$になるまで繰り返せばいいです。

ステップ5：まとめ

まとめると、こうなります。

1. nを26で割った余りを求める
2. （余りが0なら、26に変える）
3. nから求めた数字を引く
4. もしnが0なら終了
5. nを26で割る
6. 1に戻る

これをコードにすればいいです。

コード

n = int(input())
chars = "Xabcdefghijklmnopqrstuvwxyz"  # x番目がほしいときにchars[x-1]としたくないので、chars[0]は使わないことにします

n_rem = n  # 入力を直接操作すると、もし後々必要になったときに面倒なので
res = ""

while True:
    x = n_rem % 26
    # 余りが0、つまりzの場合は、26にします
    if x == 0:
        x = 26
    res += chars[x]

    # xを引いて、26で割ります
    n_rem -= x

    # 0なら終了します
    if n_rem == 0:
        break

    n_rem //= 26

# 0桁目が先頭で、最後の桁が末尾になっているので、反転させます
print(res[::-1])