【Python】Atcoder Beginner Contest 150の復習

AtCoder

Atcoder Beginner Contest 150の復習です。問題C、Dについてまとめています。

問題C

問題はこちらです。

数列P、Qはそれぞれ辞書順で何番目かを求め、順位の差を出力します。

P=[1, 3, 2], Q=[3, 1, 2](入力例1)の場合で、それぞれの数列が辞書順で何番目になるか考えてみます。

N=3の時の順列は6個あります。このうち、Pは辞書順で2番目、Qは辞書順で5番目に該当します。

辞書順で何番目にあるかは、P、Qそれぞれの前にいくつの数列があるか数えることで求めることができます。

例えば、Qの場合は以下のような流れ数えていきます。

これらの総和は 2*2! + 0*1! + 0*0! = 4となり、Qの前には4つの数列があることがわかります。Pも同様に求めます。

問題D

問題はこちらです。

\(X=a_k*(p+0.5)\)

上の式を下のように変換します。

\(X=\frac{a_k}{2}*(2p+1)\)

こうすると、Xは「(ak/2)の奇数倍」であることがわかります。この時、Xが2で割れる回数と、(ak/2)が2で割れる回数は等しくなります。

したがって、「全てのkに対して(ak/2)が2で割れる回数は等しい」という条件を満たしているか確認する必要があります。

上の条件を満たす時、M以下で、「リストの要素の最小公倍数の奇数倍」となるXの個数を数えれば良いです。

最小公倍数を求める

pythonで最小公倍数を求める方法は以下の記事が参考になります。

Pythonで最大公約数と最小公倍数を算出・取得

※注意点

現在のAtCoderのpythonはバージョン3.4.3なので、gcd()関数はfractionsモジュールにあるそうです。

2で割り切れる回数を求める

ある数字の2で割り切れる回数を求める方法は以下の記事が参考になります。

ある整数が2で割り切れる回数を求める方法

数字を2進数に変換することで、for文を使わずに、回数をカウントする方法が紹介されていました。

タイトルとURLをコピーしました