AtCoder Beginner Contest (ABC) 221 PythonでC問題解いてみた
前回解いたやつ
こんにちは。メリーです。
眠たいときにやるゲームは反応速度の低下が非常に問題になりますね。ということに気付き始めた今日この頃。
夕方のご飯食べた後にやるvalorantほんとに敵の飛び出しに反応できなくて倒されてました。
あと、最近寒いのでベッドの上でずっとゴロゴロしてます。ブログもベッドでぬくぬくしながら書けるので、割とノートPCおすすめです。
というわけで今日も今日とてAtCoder Beginner Contest (ABC) 221のC問題やっていきます。
前回とは違って、解説見ないとできなかったし、方針も立てられなかったので、ちょっとショック。
言語はPython、提出はPyPyです。
目次
C問題 考える編
問題文
整数Nが与えられて、各桁の数を組み合わせて２つの整数にしてその積を最大にするパターンは何かを求める問題。
とりあえず問題文の通りに実装してみよう！！と思うも、うまく行かず。
主に悩んだ点は次の通り。
各桁の整数を取り出し、２つの整数の組み合わせにしようかと思った時に、相方の数字をどうやって決めるのか。
相方の数字を決める時に、組み合わせを全探索するのはどうやってやるのか。
そもそも、普通にループさせるだけでは全探索厳しいのでは？
という点にぶち当たりました。
例題１を参考に、プログラムに落とし込もうとしても、どうしてもうまく全探索ができませんでした。
また、全探索しないパターンは何かあるかなと考えましたが、問題文自体を考察しても、
大きい数字と大きい数字を掛けたら積も大きくなるよね
くらいにしか考察がのびませんでした。
うーん、これは問題を解くための基礎的な知識が全く足りてないのかな〜？と思い、解説を見ることにしました。
C問題 解説方針理解編
参考にした解説は以下のやつです。
公式解説
Editorial - AtCoder Beginner Contest 221
これの１番最後のやつを自分なりに落とし込んでで書き直したコードがこちら。
n = input()
n2 = sorted(n,reverse=True)
ans = 0
# bit全探索開始
for i in range(2 ** len(n)):
a0 = []
a1 = []
for j in range(len(n)):
if (i >> j) & 1:
a1.append(str(n2[j]))
else:
a0.append(str(n2[j]))
if len(a0) != 0:
a0 = int(''.join(a0))
else:
a0 = 0
if len(a1) != 0:
a1 = int(''.join(a1))
else:
a1 = 0
ans = max(ans,a0*a1)
else:
print(ans)
と、まあ、コードを直接解説する前に方針を。
今回使ったのはbit全探索です。
イメージとしては、各桁の数にそれぞれスイッチがついていて、そのスイッチをオンにすると、整数１にその数が含まれている。
オフなら、整数１にその数が含まれていない、すなわち整数２にその数が含まれていることになります。
入力例１で例にします。
与えられた整数123の各桁のスイッチが左から「オン、オフ、オン」になってたとします。
すると、整数１には1と2が含まれていて、整数2には3が含まれている、ということになります。
そして、求めるのは整数1と整数2の積が最大になるパターンです。
よって、整数1と整数2を可能な限り最大にすれば、12、3で分離したパターンの最大値が出ます。
これのように、13、2で分離したパターンとか、全てのパターン調べれば良いわけです。
そして、このスイッチのオンオフを実際のコードでは0と1で管理しています。
また、整数1、2を最大化するためには、数字を大きい方から順番に並べていけば良いのです。
12より、21の方が大きく、1546よりも6541の方が大きいのです。
というわけでこれらのことをまとめた方針が
1. 与えられた整数を大きい方から並べ直す。
2. bit全探索していく。
3. 探索した結果を元に答えを更新。
4. 答えを出力。
ということになります。
C問題 解説コード理解編
ここからはコードの解説をするので、コードを再掲しておきます。
n = input()
n2 = sorted(n,reverse=True)
ans = 0
# bit全探索開始
for i in range(2 ** len(n)):
a0 = []
a1 = []
for j in range(len(n)):
if (i >> j) & 1:
a1.append(str(n2[j]))
else:
a0.append(str(n2[j]))
if len(a0) != 0:
a0 = int(''.join(a0))
else:
a0 = 0
if len(a1) != 0:
a1 = int(''.join(a1))
else:
a1 = 0
ans = max(ans,a0*a1)
else:
print(ans)
最初のインプット部分や、定義部分は問題ないかと思われます。
n2をわざわざ定義する必要はないんですけど、後々nを更新する場面が出てくるかなと思ったので定義してました。結局必要ありませんでした。
n = sorted(n,reverse=True) で問題ないですね。
で、問題なのはbit全探索のメイン部分のループ部分だと思われます。
bit全探索のここのループ部分はほぼテンプレートです。
初期化する、bitずらす、場合分けの処理する、答えを更新する、最後に答えを出力する、というのを問題に当てはめているだけです。
iのrangeが2**len(n)なのは、スイッチの数がlen(n)個で、それのオンオフがそれぞれ2通りあるので、スイッチのオンオフのパターンは全部で2len(n)通りになるからです。
その後のjのループ部分で各桁のスイッチのオンオフ状況をチェックしています。
例えば、i = 10の場合は二進数にするとi = 1010(2)になります。n = 9876の場合だと、スイッチが「オン、オフ、オン、オフ」となっています。つまり、整数１に97、整数2に86が入っているということになります。
この例でわかるとおり、iは十進数として考えるのではなく、二進数で考えるとループが理解しやすいです。
if len(a0) != 0:
a0 = int(''.join(a0))
else:
a0 = 0
if len(a1) != 0:
a1 = int(''.join(a1))
else:
a1 = 0
a0、a1をlistからintに直しています。
if文はansを更新する時に、どっちかの配列に数字が入っていないとerrorが出る（intとlistだと掛け算できないよ）ので、配列に数字が入っていない場合は片方を0にして、ansの更新が起きないようにしました。
記事を書いてる時に思いましたが、continueを使えばスッキリしましたよね。それか、ループの始まりを1にするか。
ans = max(ans,a0*a1)そしてこれでansを更新してます。ansより大きかったら更新していってます。
最後に出力して終わり！！！
という感じでした。
bit全探索に気がつけなかったのが悔やまれます。
前にbit全探索の問題は１問解いたんだけどな・・・
やっぱり繰り返しが大事ですね。
それでは！！！！
