ABC159 A問題 B問題 C問題 D問題
今回はABC159からA、B、C、D問題に関して綴らせていただきます。
まずA問題から、これA問題にしては少し難しくないですか？少しだけうろたえてしまった自分がいます。
問題文は以下の通り。N + M個のボールがあって、N個のボールには偶数の番号が記入されていて、M個のボールには奇数の番号が記入されています。
これらのボールから２つ選んでボールをとったとき、その２つのボールに記入されている番号の合計が偶数になるような組み合わせは何通りあるか？
みたいな感じだと思います。
例えば偶数のボールが２個、奇数のボールが１個(N=2, M=1)のときは、偶数のボールを２つ選んだときの一通りしかないので、"1" という数字を出力します。
ということで早速僕のコードを晒しますね。
def nC2(N):
c = 1
for i in range(N-1,N+1):
c *= i
c //= 2
return c
N, M = map(int, input().split())
c1, c2 = nC2(N),nC2(M)
print(c1+c2)今回は組み合わせの式を用いました。5C2 = 5*4/2*1 みたいな感じのやつです。
nC2関数では引数にボールの個数をとり、それを用いて組み合わせの式で計算した数値を返り値にしています。
偶数ボールの個数をNとして、奇数ボールの個数をMとしてます。
２つの数を足し合わせたときに偶数になる組み合わせは、偶数+偶数と奇数+奇数しかないので、N個の中から２つのボールを選んだときの組み合わせの数とM個の中から２つのボールを選んだときの組み合わせ数の合計が今回求められている値です。
そのため、c1、c2の変数にそれぞれ偶数の時、奇数の時のときの組み合わせの数を代入して、最後にそれの合計を出力しています。
お次はB問題いきます
長さが奇数の文字列Sが与えられる。そのSが「強い回文」であるとき"Yes"と出力し、そうでないとき"No"と出力する。
「強い回文」は以下の条件を満たす。
・文字列Sが回文である
・文字列Sの真ん中の一文字を除く半分が回文である
例を挙げると、文字列Sの長さが奇数なので、長さ７の文字列"abcdefg"があると、"abcdefg"が回文、かつ、"abc"が回文、かつ"efg"が回文であれば、強い文字列といえる。この例ではどれも回文ではないので出力は"No"となる。
こちらの早速コードを紹介させていただきます。
S = input().rstrip()
N = len(S)
s1 ,s2= S[:(N-1)//2] , S[(N+3)//2-1:]
if s1 == s2:
print("Yes")
else:
print("No")これは普通の回文を求めるよりも楽でした。なぜなら、Sが回文であること以外に、Sの半分の文字列も回文であることが要求されるからですね。
普通の回文を求めるときは、半分の文字列のどちらか一方を反転させて同じであるかを確かめていました。
例えば、"bkgagkb"という文があるとします。これが普通の回文であるかを確かめるには、"bkg"と"gkb"をとってきて、"gkb"を"bkg"にしていました。
しかし、「強い回文」では反転作業が必要ありません。例えば、"akasaka"という文字列は「強い回文」ですが、"aka"も"aka"もどちらも回文なので反転させずとも一致します。そして、これが一致するということは文字列S全体も回文であるのです。
なのでコードを見てもらうと分かるようにSの文字列から前半半分の文字列をs1として、後半半分の文字列をs2として抜き出していますが、抜き出した直後で即 if 文を通しています。「強い回文」さんマジ半端ないです！！
お次はC問題。
問題：正の整数Lが与えられます。縦、横、高さの長さの合計がLの直方体としてありうる体積の最大値を求めてください。縦、横、高さはそれぞれ整数でなくとも構いません。
という感じの問題です。
こちらも早速コード紹介。
L = int(input())
print((L/3)**3)たった二行ですね。一行目に縦横高さの合計Lを受け取って、Lを3で割った値に3乗している値を出力しているだけですね。
僕の場合は９という数字を適当に三分割して分割した数字を掛け合わせていたら、９を綺麗に三等分したときの数字を掛け合わせたら一番でかい数になるくね？みたいなノリで見つけたので、この式が正しいのかはイマイチ自信ないです。
この問題の出力例入力例を見ても、入力された値を３で割って３乗した値が出力として出ていたので、証明という証明があれば見てみたいです。
解説出来ていなくて申し訳ありませぬ。
続いてD問題いくです
問題： N個のボールに適当な整数が書かれています。N個から１つだけボールを取り除いたとき、残りのボールから２つのボールをとると、選んだ２つのボールに書かれている数字が等しくなるような通り数はいくつあるでしょうか？選ぶ順序は考慮しないものとします。
といった問題だと思います。
入力としては１行目にボールの個数Nが与えられて、２行目に複数のボールに書かれた番号が与えられます。
出力はN個のボールの先頭から始まって最後のボールまで、ボールを１つ取り除いて残ったボールの中から同じ番号のボールを選ぶ通り数を出力します。なのでボールの個数が５個ある場合は５個の出力があります。
解法としては、組み合わせの数を使います。まず僕が最初に考えた方法は次のような感じです。
ボールを一つ取り除いて、残ったボールからボール番号ごとにカウントしていく。その後、カウントした情報を基に組み合わせの式を用いて、ある番号において同じ数を引いてしまう通り数を求め、それを足し合わせた結果を出力するというやり方です。
例を挙げます。
[2, 3 , 2, 3, 2, 3] みたいな感じで番号が振られたボールが６個あるとします。
これらの一つを除きます。
そうすると、[3, 2, 3, 2, 3]みたいに５個の番号になります。そして重複している要素をカウントすると、３の番号が書かれたボールが３つ、２の番号が書かれたボールが２つあるという状態です。
この例で２つボールをとったとき、２つのボール番号が等しくなる通り数は以下のようになります。
３つあるボールから２つとったときの組み合わせ +
２つあるボールから２つとったときの組み合わせ = 答え
よって3C2 + 2C2 = 3+1 = 4 となります。
この解法でやったときのコードを載せます。
def nC2(N):
c = 1
for i in range(N-1, N+1):
c*= i
c//=2
return c
N = int(input())
ballList = list(map(int, input().split()))
for i in range(N):
ballListTmp = ballList
ballListTmp = ballListTmp[:i] + ballListTmp[(i+1):]
maxNumber = max(ballListTmp)
#countした値を格納する配列、countListのインデックスはボールナンバーに紐づいている
countList = [0 for _ in range(maxNumber+1)]
#それぞれの数字が書かれたボールの個数をカウントする
for ballNum in ballListTmp:
countList[ballNum] += 1
samePattern = 0
for count in countList:
samePattern += nC2(count)
print(samePattern)見づらくてごめん...
nC2関数が組み合わせの数を出力する関数です。
Nがボールの数、ballListが複数のボール番号が格納されています。
次のfor文からは、ballListTmpにインデックス i 番目にあるballListの要素を除いた、N-1個の配列を格納しています。
maxNumberにはballListTmpに入っている数字の中で最も大きい数を格納。
countList 変数を定義して、maxNumber+1だけ0で初期化します。countListはインデックスにボール番号、要素にそのボール番号が書かれたボールの個数が入ります。
次のfor文でボールをカウントして、また次のfor文でカウントした値を基に組み合わせの数を計算して足し合わせ答えを出します。
それらの処理をボールの個数だけ繰り返します。
こういった流れでやったはいいのですが......
TLEキターーーー！！
pythonでダメならpypyと思ったのですがこれもダメ。
そうなのです。繰り返し文の中で繰り返し文を回すと、処理回数が指数関数的に多くなるので、往々にしてTLEが起こります。
今回私はfor i in range(N)の中でfor count in countList として、さらにこの中の関数nC2の中でもfor文を用いているので、繰り返し文が３重になっていたわけです。そりゃTLEになりますわｗ
ということで少し考え方を変えました。
次に用いた解法についてお話しします。
先ほどは、ボールを一つ除いては個数をカウントして通り数を計算する、という処理を繰り返していました。
次にやる解法としては、まずN個あるボールを全てボールの番号ごとにカウントして、同じ番号のボールを２つとる通り数を求め合算します。
これで、まずN個のボールから同じ番号のボールを２つとる通り数が求められます。
その後、ある番号のボールを１つ除くとき、除いたボールの番号をcountした値から一つ引いてあげて、２つのその番号書かれた通り数を先ほどの全体の通り数に足して、１つ除く前の通り数を引いてあげると求めていた答えが出ます。
非常に分かりにくいのでこれまた例を用います。
先ほど同様[2,3,2,3,2,3]という番号が振られた６つのボールがあります。
これの全体の個数は２が３つ、３が３つです。なので、同じ番号を２つとる通り数は、全体で 3C2 + 3C2= 6です。
その後、先頭の２という数字が書かれたボールを除くとします。
すると、[3,2,3,2,3]となります。この通り数は2C2+3C2=4となりますね。先ほどは２という数が３つありましたが、今は２つしかありません。よって、全体で3C2+3C2だった値から3C2を引いて、2C2を足せばいいわけです。
式にするとこんな感じ
(3C2 + 3C2) - 3C2 + 2C2 = 2C2+ 3C2=4となります。
こんな感じでやります。
早速コード紹介いってみよ
def nC2(N):
c = 1
for i in range(N-1, N+1):
c*= i
c//=2
return c
N = int(input())
ballList = list(map(int, input().split()))
#それぞれのボール番号ごとにボール個数を格納する辞書( key = ボール番号、 value = ボールの個数)
countDic = {}
#それぞれのボールの個数を数え、countDicに格納
for ballNum in ballList:
if not ballNum in countDic:
countDic[ballNum] = 0
countDic[ballNum] += 1
#すべての組み合わせ個数を合算する変数
sameCombi = 0
for count in countDic.values():
sameCombi += nC2(count)
#ボールを取り出して、ボール番号ごとにsameCombiから足したり引いたりして組み合わせ個数を計算する
for ballNum in ballList:
sameCombiResult = sameCombi + nC2(countDic[ballNum]-1) - nC2(countDic[ballNum])
print(sameCombiResult)少し長いので分割して説明しまね
def nC2(N):
c = 1
for i in range(N-1, N+1):
c*= i
c//=2
return c最初の関数はAの問題にも出てきた組み合わせの数を求める関数です。
N = int(input())
ballList = list(map(int, input().split()))
#それぞれのボール番号ごとにボール個数を格納する辞書( key = ボール番号、 value = ボールの個数)
countDic = {}
#それぞれのボールの個数を数え、countDicに格納
for ballNum in ballList:
if not ballNum in countDic:
countDic[ballNum] = 0
countDic[ballNum] += 1
#すべての組み合わせ個数を合算する変数
sameCombi = 0
for count in countDic.values():
sameCombi += nC2(count)入力は割愛。
countDicは辞書型の変数です。この変数は、keyとしてボール番号、valueとしてボールの個数をとります。先ほどは配列にしていたのですが、これだとボール番号の値が両極端だったときに機能しないインデックスがめちゃくちゃ多くなると思ったので辞書型にしました。いいアドバイスあれば待ってます！！
次のfor文ではcountDicを用いて、それぞれの番号のボールの個数をカウントしています。もし、countDicにボール番号がまだ存在しないようなら、そのボール番号をkeyとして0で初期化をしています。
sameCombi変数には、N個のボールから２個同じ番号をひくときの通り数を格納する予定です。まず０で初期化処理をした後、for文でカウントした値を基に全体の通り数を合算しています。
#ボールを取り出して、ボール番号ごとにsameCombiから足したり引いたりして組み合わせ個数を計算する
for ballNum in ballList:
sameCombiResult = sameCombi + nC2(countDic[ballNum]-1) - nC2(countDic[ballNum])
print(sameCombiResult)ボールの番号を先頭から見ていって、先ほどの全体の通り数にあるボール番号のボールを一つ除いた時の通り数を足して、除かなかったときの通り数を引いています。
最後にそれを出力してファイナルアンサーです。
今回のプログラムは１か所を除き基本的に２重の繰り返し文がなく、処理数も大幅に削ることが出来たと思います。
pypyですら処理できなかったコードをpythonで処理できるようになったのも嬉しみが深みポイントです。
こんなクソ長い文を読んでくれた貴方は最高です！
この記事が気に入ったらサポートをしてみませんか？