ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

重複組み合わせの考え方

mathtrain.jp

例題1

青,赤,黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。

重複組合せを考えるときは、仕切りを引く方法に置き換えるとわかりやすい。

○ ○ ○ ○ | |
○ ○ ○ | ○ |
○ ○ ○ | | ○ 
...
| | ○ ○ ○ ○

という風に、4つのボールと2つの仕切りを使って、仕切りで分けられた左側を青、真ん中を赤、右側を黒と考える。

この組み合わせの数は、「6個の?のうち、2つを選んで仕切りにする組み合わせの数」と同じ。

? ? ? ? ? ?
↓
? ? ? ? | |

これは  {}_6 C_2 で求まります。

一般化すると、K種類の玉をN個選ぶときの組み合わせの数は、仕切りの数は K-1 になるので、

 {}_{N+K-1} C_{K-1}

になります。

例題2

青,赤,黒の三種類の玉がたくさんある。この中から5つ玉を選ぶときに得られる色のパターンのうち,どの色の玉も一つ以上選ぶものが何通りあるか求めよ。

3種類のどの色の玉も一つ以上選ぶ必要がある場合、先に玉を3個割り振っておきます。

その後、残った 5-3 = 2 個の玉を、重複組み合わせで解けば良いです。

# 残った2個の玉と、2個の仕切りを使って重複組み合わせを解く
○ ○ | |

つまり  {}_4 C_2 で求まります。

PythonでCombination

最後に、Pythonでの組み合わせの数(Combination)の求め方を書きます。

from math import factorial

def combination_formula(n, r):
    return factorial(n) // (factorial(r)*factorial(n-r))

ans = combinatin_formula(6, 2)
print(ans)
# 15

ans = combinatin_formula(4, 2)
print(ans)
# 6

切り捨て除算しているのは、返り値を整数にするためです。

数え上げ問題難しいです><

ABC032: C問題の解説 (Python3)

問題:AtCoder Beginner Contest 032: C - 列

公式解説:https://www.slideshare.net/chokudai/abc032

しゃくとり法の問題です。

公式解説を読むと、「連続する1を圧縮する」という重要なテクニックが書かれていますが、本記事ではそうではない方法で解いています。解法としては少し変わったしゃくとり法です。

しゃくとり法といえば区間の和を効率よく求める方法ですが、今回の問題は区間の積のしゃくとり法といった感じです。

解説

 K = 6
 4 3 1 1 2 2 1 1 1 2

という数列について考えます。

# 初期状態
 4 3 1 1 2 2 1 1 1 2
|_|
 4

# 右端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
|___|
  12

# K=6を超えたので、左端の4で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
  |_|
   3

# 右端の位置を1すすめるという操作を繰り返す(累積がK=6を超えるまで操作を繰り返す)
 4 3 1 1 2 2 1 1 1 2
  |_______|
      6

# 右端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
  |_________|
       12

# K=6を超えたので、左端の3で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
    |_______|
         4

# 右端の位置を1すすめるという操作を繰り返す(累積がK=6を超えるまで操作を繰り返す)...(※)
 4 3 1 1 2 2 1 1 1 2
    |_____________|
          4

# 右端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
    |_______________|
           8

# K=6を超えたので、左端の1で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
      |_____________|
             8

# まだK=6を超えてるので、左端の1で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
        |___________|
             8

# まだK=6を超えてるので、左端の2で割ったあと、左端の位置を1すすめる
 4 3 1 1 2 2 1 1 1 2
          |_________|
               4

# 右端の位置を1すすめるが、これ以上すすめれないので終了
 4 3 1 1 2 2 1 1 1 2
          |_________|
               4

よって答えは、(※)のときの7

上記例の入力は以下になります。

10 6
4
3
1
1
2
2
1
1
1
2

コーナーケース

  • 数列に0が登場したら、全数列の積は必ず0になるので、Nを出力すれば良い。
  • K=0のとき、
    • 数列に0が登場するなら、全数列の積は0になり、これはK以下の制約を満たす。よってNを出力する
    • 数列に0が登場しないなら、どの部分列の積も必ず1以上になるので、これはK以下の制約を満たせない。よって0を出力する

実装

# -*- coding:utf-8 -*-
import sys


def solve():
    N, K = list(map(int, sys.stdin.readline().split()))
    Ss = []
    for _ in range(N):
        s = int(input())
        Ss.append(s)

    if K == 0:
        # コーナーケース
        if 0 in Ss:
            print(N)
        else:
            print(0)
        return

    left = 0   # 左端
    ans = 0    # 最終的に出力する答え
    accum = 1  # 累積
    for right in range(N):
        accum *= Ss[right]

        if accum == 0:
            # 0を掛けた場合は例外で、Nを出力して終了
            print(N)
            return

        while accum > K:
            accum //= Ss[left]
            left += 1
        ans = max(ans, right-left+1)
    
    print(ans)


if __name__ == "__main__":
    solve()

計算量は、たとえば K=10、数列が 1 1 1 1 1 1 1 1 1 1 1 99 みたいな最悪ケースを考えると、そのときはwhile accume > K: の合計操作回数がNになるので、最悪計算量が  O(2N) = O(N) だと思います。たぶん。

あるいは、rightは高々N回右に移動するし、leftも高々N回右に移動するので、やっぱり  O(2N) = O(N) だと思います。

while accum > K: のwhileループで左端の位置を右に1だけ移動させる操作を繰り返していますが、実はこの問題の性質上、ループさせなくてもただ1回だけ操作をするだけで良さそうです(そうやって解いてる人もいた)。

Python: 2進数の文字列を、float(64bitの倍精度浮動小数点数)型の数値に変換する

  • bin_to_double() 関数
    • 2進数の文字列を、float(64bitの倍精度浮動小数点数)型の数値に変換する関数
  • double_to_bin() 関数
    • 上の逆関数(float型の数値を、2進数の文字列に変換する関数)

詳細は以下のGistのコードを参照してください。

gist.github.com

参考

Python: 切り捨てはmath.floor()より//演算子を使ったほうが良いかも

環境はPython3.6.5です。

まずは以下の計算結果を見てください。

gist.github.com

なぜ?

float型において、有効数字が16桁以上の値を表現しようとすると誤差が生じてしまう可能性があるからです。

N//3 のような整数同士の切り捨て除算は内部処理的にint型のまま演算されるので(たぶん)、誤差が発生しないのだと思います。

よって、整数同士の切り捨て除算の場合、//演算子を使ったほうが誤差が発生する可能性が低いので、そちらを使ったほうが良いかもしれません。

調査と解説

以下は、詳しい解説になります。

まず、//演算子とmath.floor()の違いというか、それぞれがどんなことをしているかというのを調査し、整理します。

//演算子

公式ドキュメントの二項算術演算の説明によれば、/(除算)および//(切り捨て除算)は次のようなことをしています。

/ (除算: division) および // (切り捨て除算: floor division) は、引数同士の商を与えます。数値引数はまず共通の型に変換されます。整数の除算結果は浮動小数点になりますが、整数の切り捨て除算結果は整数になります; この場合、結果は数学的な除算に 'floor' 関数 を適用したものになります。ゼロによる除算を行うと ZeroDivisionError 例外を送出します。

要約すると、次のようになります。

# 整数の除算結果は浮動小数点数
print(6/2)
# 3.0

# 整数の切り捨て除算結果は整数
print(6//2)
# 3

整数の切り捨て除算結果は整数」がミソで、じゃあfloat型の切り捨て除算結果の場合はどうなるかというと、

print(7.0//2)
# 3.0

float型になります。

math.floor()

次はmath.floor()についてですが、公式リファレンスのmath.floor()の説明によると以下のことが書いてあります。

math.floor(x)

x の「床」 (x 以下の最大の整数) を返します。 x が浮動小数点数でなければ、内部的に x._floor_() が実行され、 Integral 値が返されます。

引数 x が浮動小数点数でなければ、Integral値が返されるようです。Integral値についての説明は省くとして(あんまりわからないし)、要約するとint型に変換された値が返ってくると考えます。

ここでも「引数 x が浮動小数点数でなければ」という条件がついています。じゃあ浮動小数点数の場合はどうなるんだよという話ですが、見た目の挙動は触ってみた感じ変わりません(int型に変換されます)。内部的には知らないです。floor()の実装はたぶんここですが、数分ソースを追いかけたあと、眼鏡をクイッして終わりました。

これまでのことをまとめると、処理の流れは次のようになると思います。

  • b//a

    • b が整数ならば、整数が返る
    • b がfloat型ならば、float型が返る
  • floor(x)

float型の有効数字

Pythonのfloat型はC言語でいうところのdouble型(64bitの倍精度浮動小数点数1で、その有効数字は約16桁です(Wikipedia調べ)。

よって、有効数字が16桁以上の値を表現しようとすると誤差が生じてしまう可能性があります。これは演算させるさせないは関係ありません。

a = 9999999999999999.  # 有効数字16桁
print(a)
# 1e+16
print(f"{a:.10f}")
# 10000000000000000.0000000000

また、f-strings(フォーマット済み文字列リテラル)で出力するとき、float型に変換する処理をおこなうと、同様の理由で誤差が出ることがあるので注意しましょう。

a = 100000000000000000000
b = a//3
print(b)
# 33333333333333333333
print(f"{b:.10f}")  # floatに変換するので誤差が発生
# 33333333333333331968.0000000000
print(f"{b:18d}")
# 33333333333333333333

結論とまとめ

というわけで、途中の演算で有効数字が16桁以上のfloat型になると、誤差が生じる可能性が出てきます。

floor(N/3)について解説すると、

c = N/3       # この時点で有効数字16桁以上のfloat型になり、誤差が発生する
b = floor(c)  # 誤差が発生した値を切り捨て除算し、整数部を取り出す
print(b)
# 333333333333333312

N//3について解説すると、

a = N//3  # float()型に変換されることはないので、誤差は発生しない
print(a)
# 333333333333333333

ただし、float型の切り捨て除算は誤差が発生します。

N = 1000000000000000000.  # 10**18のfloat値
a = N//3  # 有効数字16桁以上のfloat型になり、誤差が発生する
print(a)
# 3.333333333333333e+17
print(f"{a:.10f}") 
# 333333333333333312.0000000000

以上の理由で、math.floor()演算子より、//演算子を使ったほうが良いと主張します。おわり。

おまけ1

AtCoder Beginner Contest 131: C - Anti-Divisionで、floor()を使うとWAになり、//演算子を使うとACになったのが調査のきっかけです。

# -*- coding:utf-8 -*-
"""解説
B以下の整数のうち、CでもDでも割り切れないものの個数をCountBとする
A以下の整数のうち、CでもDでも割り切れないものの個数をCountAとする
求める答えは、CountB - CountA
・CountBの求め方
B以下の整数のうち、Cで割り切れるものの個数はCountB_C = B//C
B以下の整数のうち、Dで割り切れるものの個数はCountB_D = B//D
B以下の整数のうち、CでもDでも割り切れるものの個数はCountB_CD = B//lcm(C,D)
CountB = B - (CountB_C + CountB_D - CountB_CD)
"""
from fractions import gcd
from math import floor

def solve():
    A, B, C, D = list(map(int, input().split()))
    def lcm(a, b):
        """ aとbの最小公倍数を返す """
        return a*b // gcd(a, b)

    def f(x):
        """ 1以上x以下の整数のうち、CでもDでも割り切れないものの個数を返す """
        #return x - (floor(x/C) + floor(x/D) - floor(x/lcm(C,D)))  # こっちだとWA
        return x - (x//C + x//D - x//lcm(C,D))  # こっちだとAC

    ans = f(B) - f(A-1)

    print(ans)


if __name__ == "__main__":
    solve()

おまけ2

追記2019/09/02

AtCoder Beginner Contest 139: D - ModSumでも似たような注意が必要です。

問題文と解説は省略しますが、要は 1~N-1 までの和を出力する問題です。

# -*- coding:utf-8 -*-

def solve():
    N = int(input())

    # O(N)じゃ間に合わない

    """
    i   = 1 2 3 4 5 6 7 8
    P_i = 2 3 4 5 6 7 8 1

    ↑これが最大値なのでは?
    つまり、
    ・P_i = i + 1
    ・P_N = 1
    にすると、1 ~ N-1の和が答えになる。
    """
    # N = 10**9-1
    ans = (1+(N-1))*(N-1)//2  # 整数同士の切り捨て除算(//)は浮動小数点数(float型)に変換されることはないので、誤差は発生しない
    # ans = int((1+(N-1))*(N-1)/2)  # 除算(/)の結果はfloat型に変換されるので、誤差が発生しうる(N = 10**9-1で誤差が発生する)
    print(ans)

if __name__ == "__main__":
    solve()

Pythonでいもす法

いもす法とは

いもす法(imos法)とは、長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を、計算量O(N+K)で高速に構築できる方法。

たとえば、「ある連続する区間に、1を足す」という操作を4回したい次の図のようなものを考えた場合、いもす法を使えば最終結果を高速に求めることができます。

f:id:takeg:20190828105337j:plain
いもす法の例

2次元や3次元に拡張できるらしいです(まだ使ったことない)。2次元に拡張バージョンは本家の説明を読むとなるほどなぁとなれます。

いもす法の手順

いもす法の手順は以下の2ステップです。

  • ステップ1: 加算処理
    • 区間 [l, r] に v を加算したいとき、
      • l 番目の値に v を加算する
      • r+1 番目の値に -v を加算する
  • ステップ2: 累積和
    • 最後に累積和をすると、最終結果を得られる

例1

長さ7のリストにおいて、

という3つの操作をしたときの最終結果を得たいとします。

ステップ1: 加算処理

  • 初期状態
i 0 1 2 3 4 5 6
要素の値 0 0 0 0 0 0 0
N = 7
data = [0] * N

区間[1, 3]に2を加算

i 0 1 2 3 4 5 6
要素の値 0 2 0 0 -2 0 0

l = 1, r = 3 なので、

  • data[l] に 2 を加算
  • data[r+1] に -2 を加算

をします。

l, r = 1, 3
v = 2
data[l] += v
if r+1 != N:
    data[r+1] +=-v

区間[3, 3]に3を加算

i 0 1 2 3 4 5 6
要素の値 0 2 0 3 -5 0 0
l, r = 3, 3
v = 3
data[l] += v
if r+1 != N:
    data[r+1] +=-v

区間[0, 5]に1を加算

i 0 1 2 3 4 5 6
要素の値 1 2 0 3 -5 0 -1
l, r = 0, 5
v = 1
data[l] += v
if r+1 != N:
    data[r+1] +=-v

ステップ2: 累積和

最後に、累積和をすると最終結果を得ることができます。

i 0 1 2 3 4 5 6
要素の値 1 2 0 3 -5 0 -1
累積和 1 3 3 6 1 1 0
ruiseki = [0] * N  # 累積和用リスト
ruiseki[0] = data[0]
for i in range(1, N):
    ruiseki[i] = ruiseki[i-1] + data[i]

# 最終結果を出力
print(ruiseki)
# [1, 3, 3, 6, 1, 1, 0]

例2: AtCoder Beginner Contest 035: C - オセロ

黒の面に0、白の面に1が書かれた N 個のオセロの駒が、どの駒も黒の面が上を向くように一列に並べられています。その後、ある区間にある駒を全て裏返すという操作が Q 回だけ行なわれました。 具体的には i 回目の操作においては、左から l_i 番目の駒から r_i 番目の駒までの駒全てが裏返されました。

最終的な盤面を求めてください。

# -*- coding:utf-8 -*-

def solve():
    # 入力処理
    N, Q = list(map(int, input().split()))

    # オセロの駒の初期化(最初はすべて黒)
    s = [0] * (N+1)
 
    # いもす法の加算処理
    for _ in range(Q):
        l, r = list(map(int, input().split()))  # 区間[l, r]の入力を受け取る
        s[l] += 1
        if r+1 != N+1:
            s[r+1] -= 1
    
    # いもす法の累積和(構築処理)
    ruiseki = [0] * (N+1)
    for i in range(1, N+1):
        ruiseki[i] += ruiseki[i-1] + s[i]
        if ruiseki[i]%2 == 0:
            # 裏返した回数が偶数なら、黒のまま
            ruiseki[i] = 0
        else:
            # 裏返した回数が奇数なら、白
            ruiseki[i] = 1
    
    # 答えを出力
    ans = "".join(list(map(str, ruiseki[1:])))
    print(ans)
 
 
if __name__ == "__main__":
    solve()

感想

r+1 に -v を加算することで、累積和したときによしなに調整されるというアイデアアルゴリズムでした。シンプルだけどすごい。

いもす法で解く問題

編集履歴

  • 2020/04/24: 「ステップ1: 加算処理」と「ステップ2: 累積和」を微修正。

Jupyter Notebookをフォルダ右クリックで開けるようにしてくれるstart_jupyter_cm

Jupyter Notebookを起動したあと毎回フォルダ移動するのが面倒くさい。なのでstart_jupyter_cm というリポジトリをインストールします。Windows と GNONE に対応(2019/08/23現在)されています。

github.com

インストール方法はリポジトリのREADMEを読めば書いてあるのですが、一応書くと、私の場合Windowsなので、Powershellまたはコマンドプロンプトを開いて、以下のコマンドを打ちます。

# pipでインストールする場合
$ pip install start_jupyter_cm

# condaでインストールする場合
$ conda install -c conda-forge start_jupyter_cm

# インストール後、下記コマンドを打つ
$ start_jupyter_cm

これで、フォルダを右クリックすると「Jupyter Notebook here」という項目が追加されるようになります。やったね。

アンインストール方法は、

pip uninstall start_jupyter_cm

です。