ABC165 D - Floor Function

問題: N以下の非負整数 xに対する floor(Ax/B) - A•floor(x/B) の最大値を求めてください。

input: A, B, N

  • 1<= A <= 106
  • 1<= B <= 1012
  • 1<= N <= 1012

解法

f:id:keroid0:20210223173538p:plain
よって x/B の少数部分を最大化することがf(x)の最大化であることがわかった。
x/Bを最大化するにはxにB-1を代入する。B-1がNより大きい場合はNを代入する。
つまりf(min(B-1, N))が答え。

ARC037 バウムテスト をPythonで解く

atcoder.jp

キーワード

深さ優先探索再帰関数を使わない
・サイクル検出

DFS(深さ優先探索)で無向グラフを探索し、サイクル検出をします。 f:id:keroid0:20200523145852p:plain
問題文では「木」の数を出力せよとあるのでこの画像だと左側がサイクルが無いので木です。右側はあるので木ではありません。よって答えは1です。
深さ優先探索の説明は: 【Python】深さ優先探索と幅優先探索 - Qiita

実装

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    p, q = map(int, input().split())
    graph[p-1].append(q-1)
    graph[q-1].append(p-1)
vertex = [False for _ in range(n)]
# print(graph) #グラフを確認

def dfs(i):
    flag = True
    stack = [i]
    while stack:
        now = stack.pop()
        vertex[now] = True # 今居る場所を訪問済みにする。
        for i in graph[now]:
            if vertex[i]:
                continue # 頂点i がすでに訪問済みであればcontinueする。
            if i in stack:
                flag = False # スタックの中にこれから訪れようとしている頂点があればサイクルなのでフラグを立てる。
                continue # スタックにアペンドせずにcontinueする。
            stack.append(i) # 上2つのフィルターにかからなかったらスタックにアペンドする。

    # サイクルが無ければ木なので1、あったら木ではないので0を返す。
    if flag:
        return 1
    else:
        return 0

ans = 0
for i in range(n):
    if vertex[i] is False:
        ans += dfs(i) # 訪問していない頂点であれば探索し、サイクルが無ければ+1する。
print(ans)

サイクル検出

・今居る頂点は訪問済みにする
・これから訪れる(スタックにアペンドする)頂点は訪問済みではない、かつスタックの中に存在しないことが条件
・スタックの中に存在したらそれはサイクル

個人的に再帰関数が苦手なのに回答例の多くが再帰関数で実装されていて苦しかったため、なんとか再帰関数を使わずに済むように実装しました。

AtCoder ABC164 D問題 (Python)

競プロ勢からすると典型的な問題らしいですが、僕はよく分からなかったので解決までの道のりを記録します。

問題文と制約

1 から 9 までの数字のみからなる文字列 S が与えられます。
次のような条件を満たす整数の組 (i,j) (1≤i≤j≤|S|) の総数を求めてください。

条件: S の i 文字目から j 文字目までを 10 進法の整数としてみると、この整数は 2019 の倍数である。

制約
1≤|S|≤200000
S は 1 から 9 までの数字のみからなる文字列


最初に思いつく解法

s = input()
n = len(s)
ans = 0
for i in range(4, n):
    for j in range(n-i+1):
        if int(s[j:j+i])%2019 == 0:
            ans += 1
print(ans)

これは当然というかまぁ、TLEでしたね。

正しい解法

最初の解法以外全く思いつかなかったので解説を見ますが、それもすぐには理解できなかったので解説を易しい言葉に噛み砕く事を意識します。 公式解説https://img.atcoder.jp/abc164/editorial.pdf

s = 1817181712114 として順を追って解説していきます。

(1) 2019 と 10 は互いに素である

2019 は 2 でも 5 でも割り切れないので 10 の逆元が存在する。 f:id:keroid0:20200427165439p:plain (i,j は左から数えている)

(2) 10**(n-j)*(A - B) % 2019 == 0となるペアを探す。

f:id:keroid0:20200427170627p:plain

あとは s の右端から2019で割った余りをメモしていけば(i, j)ペアを発見できる。

(3) 2019で割った余りの値が同じモノの個数=k としたら (i, j)の組み合わせの個数はkC2

余り= 1 が 3 つあるとしたら3つの中から2つ選ぶ組み合わせの数なので3C2 = 3 * (3 - 1) / 2

(4) 完成

s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i = (i*10)%2019

ans = sum([i*(i-1)/2 for i in dp])
print(int(ans))

ここでfor文の中で毎回nowとiを2019で割った余りにしています。この操作をしないでも正しい結果は得られますが、この操作をしないと計算時間が間に合わなくなるため行なっています。
この操作をしないとnowやiの値が膨大な数値になってしまい、for文が一回回るだけでもかなり時間を食う(これしないとTLEになるから多分そうなんじゃないかと思う。。。)

【Python】ナップサック問題を動的計画法を用いて解く

有名なナップサック問題Pythonを使いAOJで解いてみたので記録として。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp

 

ナップサック問題

(例)「容量Wのナップサックとn個のアイテムがある。n個のアイテムはそれぞれ価値viと重さwiを持っている。n個のアイテムの中から容量Wを超えない範囲で価値の総和を最大化する」

といった整数計画問題である。同じ種類の品物を1つまでしか入れられない場合や、同じ品物をいくつでも入れてよい場合など、いくつかのバリエーションが存在する。

 

解法 例

問題を解いてみる。AOJ問題そのまま。

価値が vi 重さが wi であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます。

- 選んだ品物の価値の合計をできるだけ高くする。
- 選んだ品物の重さの総和は W を超えない。

価値の合計の最大値を求めてください。

 

N(個数) = 5, W(容量) = 10

    A   B   C   D   E 
 v   2   3   2   3   6 
 w   3   4   1   2   3 

 

全てのアイテムに対し、ナップサックに入れる入れないの2択ずつ選択肢があるため愚直に考えると2^n通りのパターンが存在し、それらのパターンの中で最も価値の総和が大きいものを選べば良い。とはいえ、この手法だとnが20を超えたあたりでパターンが100万通りを越して計算量的に現実的ではない。そこで動的計画法である。1度調べたアイテムは2度と調べなおさなくて良いようにメモをすると言う考え方。

 

 ※この記事の存在意義が9割無くなるが以下の記事で考え方は簡単に理解できる。(この記事の残り1割の存在意義はPythonでこのアルゴリズムを実装すること。。。)

病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ

↑の記事で全てわかるが、一応自分でも説明する。

 

 

 

 

<1> まずW(10)+1個テーブルをN(5)+1個用意し、index0に0を代入しておく。

<2> 次にアイテムを順に調べていく。0番目のテーブルはまだナップサックに何もはいいていないため0で次に1番目のテーブルに最初のアイテム(v=2, w=3)の入れた場合と入れなかった場合をメモする。入れなかった場合はテーブル[1][0]は0のままで、入れた場合はテーブル[1][0+3]は2になる。

<3> <2>を繰り返していくことになるが途中で矢印が交わる所では大きい方の値を残すという処理をすることに注意する。例えばテーブル[4][7]ではテーブル[3][5]の5+3=8と、テーブル[3][7]の5を比べて前者の方が大きいためそちらの値を残している。

 

コード

-----------------------------------------------------------------------------------------------------

# knap.py

n, w = map(int, input().split()) # 標準入力
inf = -10**7 # 大きい負の値
items = [] # アイテムを入れておくリスト


for _ in range(n):

    # 値と重さをitemsに格納
    value, weight = map(int, input().split())
    items.append([value, weight])

#(W+1) * (N + 1)のテーブルを作る。

dp = [[0 if i == 0 else inf for i in range(w+1)] for j in range(n+1)]


for i in range(n): # 調べるアイテムの個数(n)回だけテーブルを更新
    for j in range(w+1): # その回のテーブルを全て調べる。
        if dp[i][j] != inf and j+items[i][1] <= w:

            # そのアイテムをナップサックに入れる場合。

            # そのアイテムを入れても容量を超えない場合にのみテーブルを更新
            dp[i+1][j+items[i][1]] = max(dp[i+1][j+items[i][1]], dp[i][j]+items[i][0])

    # そのアイテムをナップサックに入れない場合。
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])

# 最後のテーブルにある最大値を出力

print(max(dp[-1])) 

---------------------------------------------------------------------------------------------------- 

 

 サンプルテスト

-----------------------------------------------------------------------------------------------------

5 10

2 3

3 4

2 1

3 2

6 3 

-----------------------------------------------------------------------------------------------------

$ python knap.py

5 10

2 3

3 4

2 1

3 2

6 3 

14     <---- answer !!

 

【python】listよりdequeの方が早い場合

競技プログラミングにおける処理速度の重要さ

PythonAtCoderなどの競技プログラミングの大会に参加しているとそもそもの処理速度が遅いせいで「C++なら通るけどPythonだと通らない」なんてこともしばしば。(Pythonでも効率的な書き方をすれば1000msを超えることはないように作門されているらしいですが)

とはいえできるなら最初から効率的に書いてるし、できないから小手先のテクニックに頼りたくなるのです。(dequeが小手先というわけではないですが)

ということでこの記事ではスタックキューをlistより高速に扱えるdequeを紹介します。

 

 

dequeの使い方

公式Wikiより

https://docs.python.org/ja/3/library/collections.html#deque-objects

class collections.deque([iterable[maxlen]])

iterable で与えられるデータから、新しい deque オブジェクトを (append() をつかって) 左から右に初期化して返します。 iterable が指定されない場合、新しい deque オブジェクトは空になります。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

 

スタックやキューのようなデータ構造を扱う(popやappendのみを使う)場合に限ってはdequeを使う方が高速だということです。

(普通のリストはメモリの0番目からデータを格納しているからpopやinsertで0番目のデータを移動する時にリスト内の他のデータも全て移動しなくてはならないから遅いのだろうか。。。?そういう風に聞こえる)

 

 

実験

listとdequeを使い、それぞれにpop()してどのくらい時間差が出るか実験してみます。

実行環境はGoogle Colabです。

 

from time import time
from collections import deque

iterations = [10**2, 10**3, 10**4]

for itr in iterations:
    print("#======= " + "itertaion: {}".format(itr) + " =======#")

    LIST = [for i in range(itr)]
    DEQUE = deque([for i in range(itr)])

    t1 = time()
    for i in range(itr):
        LIST.pop(0)
    t2 = time()

    print("list elapsed_time : {}".format(t2-t1))

    t1 = time()
    for i in range(itr):
        DEQUE.popleft()
    t2 = time()

    print("deque elapsed_time : {}".format(t2-t1))
print()

 

 

#======= itertaion: 100 =======#
list elapsed_time : 3.528594970703125e-05
deque elapsed_time : 1.5974044799804688e-05

 

#======= itertaion: 1000 =======#
list elapsed_time : 0.0004069805145263672
deque elapsed_time : 0.00015544891357421875

 

#======= itertaion: 10000 =======#
list elapsed_time : 0.016589879989624023
deque elapsed_time : 0.000986337661743164

 

繰り返し回数が100回の時は約2.2倍、1000回の時は2.6倍、10000回の時は16.8倍となっており繰り返し回数が多いほどdequeの方が圧倒的に速いことがわかりますね!