2018-09-15

Python のdecorator についてエキスパートPython プログラミングのメモ

競プロ関係ではないんですが、勉強していてわからないところがあったんでメモしておきます。

エキスパートPythonプログラミングではデコレータ

def some_decorator(function):
  def wrapped(*args, **kargs):
    # 関数を呼び出す前に行う処理
    result = function(*args, **kargs)
    # 呼び出し後に行う処理
    return(result)
  # 引数にとったfunction をデコレートした関数を返す。
  return(wrapped)

@some_decorator
def decorated_function():
  pass

は以下のような関数再定義の構文糖衣であると説明されている。

def decorated_function():
  pass
decorated_function = some_decorator(decorated_function)

ここでパラメータ付きのデコレータ

def repeat(number=3):
  def actual_decorator(function):
    def wrapper(*args, **kargs):
      result = None
      for _ in range(number):
        result = function(*args, **kargs)
      return(result)
    return(wrapper)
  return(actural_decorator)

を考える。repeatそのものはデコレータではなく、パラメータを受け取り、デコレータactual_decorator を返す関数である。このときacutual_decorator はrepeat が受け取るパラメータによって変更されている。

実際のデコレータはrepeat そのものではなくこれが返す関数なのであるから、デコレートされる関数を定義するときは、@repeat ではなく@repeat(x) としなければいけない。デフォルトのパラメータ値を用いるときであっても@repeat() である。

@repeat()
def foo():
  print("foo")

>>> foo()
foo
foo
foo

以下のように() をつけずに作用させるとエラーになる。

# 失敗例
@repeat
def foo():
  print("foo")

>>> foo()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-260-624891b0d01a> in <module>()
----> 1 foo()
TypeError: actual_decorator() missing 1 required positional argument: 'function'

後者の例は以下の関数再定義と同義であるので、foo 自身がデコレータ(関数を受け取って修飾を施す関数)になってしまっている。

foo = repeat(foo) # foo の返り値はacutual_decorator
>>> ?foo
Signature: foo(function)

2017-11-05

解いた問題へのコメント

ABC 062 D問題

よりシンプルな問題に分解してからそれらを組み合わせるといういつもの方針、というか思考の癖がうまくハマった問題だった。その分実装で苦しんだのは残念（一つ前の記事を参照）。

概要

長さ3Nの配列a[3*N]からN個の要素を取り除き、残った長さ2Nの配列を前半と後半に分ける。前半の総和 - 後半の総和が最大になるように取り除く時、この値はいくらか？

考えたこと

前半の配列と後半の配列が独立に決定できれば、「前半の総和 - 後半の総和」は前半の最大化と後半の最大化を行えばよいことになる。前半を最大化することを考えた時、a[0] .. a[2*N-1] の要素をソートして最初のN個を取ってもいいが、ここは貪欲的に考えて以下のように求める。

a[0] .. a[N-1] のうち最小の値a1_min と、a[N] の値の大きさを比べる。
a1_min < a[N] ならa1_min を除く。するとa[N] は前半のN個の要素の中に入る。前半の総和はa[N] - a1_min の分だけ増加する。この総和をa1_sum[N] と書こう。
a_min >= a[N] ならa[N] を除く。前半の総和は変わらない。
同様のことをa[N+1], a[N+2], .. a[2*N-1] まで繰り返す。最終的に得られた前半の総和は、要素の取り除き方に対して最大のものになっている。
ちなみに、a1_sum[i] はa[0] .. a[i] の中からN この要素を選んだ時の総和の最大値になっている。

同様のことを後半の配列に対しても行い、結果をa2_sum に格納する。しかし、前半の配列と後半の配列は独立でなく、前半でa[i] を使ってしまった場合、後半ではj > i なるa[j] しか使えない。

前半でa[i] を使ってしまった場合の前半の総和の最大値はa1_sum[i], j > i だけを使った場合の後半の総和の最小値はa2_sum[i+1] であるから、i = N-1 .. 2*N に対してa1_sum[i] - a2_sum[i+1] を計算すると、これの最大値が答えとなる。

Submission #1746297 - AtCoder Beginner Contest 062 | AtCoder

ABC 075 D問題

これも問題を分解し、他のパーツとの結合を最小限にすることで計算量を抑えるという観点から考えて上手くハマった。とくにダイクストラとの類似が思いついた時は心の中でガッツポーズ。ただしO(N) でやるもっとうまい方法があったみたですね。ちなみに本番では優先度つき待ち行列を実装し終わったくらいでタイムアップです。

概要

1次元上を移動する点の問題。区間に対して制限速度と時間の長さが、全体を通して加速度の制限が与えられており、進んだ距離を最大化する。

考えたこと

区間内の制限速度は分かっているので、区間の境界の制限速度を求めることができれば、区間内の速度は簡単にもとまる。境界の制限速度が何によって決まっているかを見極めなければいけない。一見すると隣接する区間の制限だけ分かっていればいいように思える。例えば、制限速度が100 の区間と80 の区間が隣り合っていたら、区間の境界では80 以下になっている必要がある。しかしこれで決まりではない。100, 80, 10 と並んでいて、80の区間がとても短かったら、100 と80 の境界では速度は80よりも大幅に遅くなくてはダメだ。80 と10 の境界でスピードを落としきれず脱線するだろう。

このことをナイーブに考えると、ある区間境界の制限速度を求めるには他の全区間からの影響を調べなければならない。また、ある区間境界の制限速度が更新されることで他の区間境界の制限速度にも影響するため、いたちごっこになってしまう。

ここで、ある区間境界が影響を受けるのはより制限速度が遅い区間境界であることに注目する。最も遅い区間境界から制限速度を確定させていくことで、このいたちごっこを避けることができる。つまりダイクストラの要領である。ダイクストラのように優先度つき待ち行列を使って区間境界の最低値を管理してもよいが、区間を全て走査してO(N²) で解いても間に合う。

Submission #1723275 - AtCoder Beginner Contest 076 | AtCoder

2017-11-05

凡ミス集

ABC 062 D問題

不完全な修正

1 累積和を計算するから

a += x;

と書く。

2 累積和を配列に格納する必要があったため、a[i+1] をa[i] から決定できるように書き換える。その際+= をそのまま残してエンバグする。

a[i+1] += a[i] + x;

もちろん正しくは

a[i+1] = a[i] + x;

バグのある方

abc062.contest.atcoder.jp

修正した方

abc062.contest.atcoder.jp

ARC 084 D問題

値渡し

二分探索にベクターを値渡ししてしまいTLE

値渡しでTLE した方

https://beta.atcoder.jp/contests/arc084/submissions/1745225beta.atcoder.jp

参照渡ししてAC した方

https://beta.atcoder.jp/contests/arc084/submissions/1745350beta.atcoder.jp

ABC 076 D問題

ループ作って値を入れず

ループで配列を走査して最小値を探索したのに、その最小値を変数に代入していなかった（インデックスを格納しただけで気を抜いてしまった）。

バグのある方

abc076.contest.atcoder.jp

修正した方

abc076.contest.atcoder.jp

以上、10月後半から11月前半の凡ミス集でした。

Code Festival qual C D問題

大きなデータはグローバルに

int main(){
    int a[(1<<26)];
}

はSegmentation fault になりますが、

int a[(1<<26)];
int main(){
}

は通ります。ツイッターでは「グローバル変数のスタック」という間違った用語を使ってしまったのですが、一般にグローバル変数が置かれるところは静的領域というんだそうです。具体的なサイズは処理系に依存するんで調べてません。

Submission #1724434 - CODE FESTIVAL 2017 qual C | AtCoder

2017-10-15

CODEFESTIVAL QualB D問題

先週行われたCODEFESTIVAL 2017 QualB D問題が解けなかったのですが、解説を読んでもちょっとわからなかったので、他の人のコードを見ながら自分なりに解法を考えていく過程を文章にしました。参考にしてくださる方がいたらうれしいです。

ちなみに私のコードはこちらです（お恥ずかしい）

Submission #1686548 - CODE FESTIVAL 2017 qual B | AtCoder

また今回の解答を考えるにあたっては、上級者の方のコードを参考にさせていただきましたが、Alex_2oo8 さんのコードが最も勉強になりました。感謝とともにクレジットいたします。

Submission #1666434 - CODE FESTIVAL 2017 qual B | AtCoder

問題文

1と0よりなる数列が与えられる。101 の並びを010 に変換することを繰り返すとき、最大何回この変換を行うことができるか？制約などは各自元ページで確認してください。

D: 101 to 010 - CODE FESTIVAL 2017 qual B | AtCoder

解説

問題を相互に影響しない部分問題に分割する

101 → 010 をここではスコア化と呼ぼう。 2セル以上続く0で隔てられたセルの配列は、一方のスコア化によって他方の配列が影響を受けないので、スコア化の順序を考える際は2つの配列は独立した問題と考えて良い。したがって、まず2セル以上連続する0を用いてセル配列全体をsplit する。split されて得られたパターンの列を $S = \{s_i\}$ と表記する。

部分問題の分析

最初の状態でスコア化できるパターンはどこ？

split された部分配列の要素は0を連続して持たない。つまり、0の両隣は1となり、かならず”101”のパターンを持つ。これは”010”に変換して得点が得られるパターンである(スコア化可能パターンと呼ぶ)。

1が連続した配列に注目すると、スコア化のやりかたが整理できる

解説にもある通り、101111… (101{k})というパターンは、左端の101 をスコア化すると、010111… となり、ちょうどスコア化可能パターンが1つ右隣のセルにずれるようにして再び現れる。これを続けて0000…010 となるまで続けると、ちょうどk点を獲得することができる。これは左右を反転した…11101 (1{k}01)というパターンでも同様である。これを連続スコア化と呼ぶ。いま、 $s_i$ を0 でsplit した配列を考える。得られた配列の要素は1が連続する配列(1-セグメントと呼ぶ)である。左からj番目の1-セグメントを $\{a_{ij}\}$ 、 $a_{ij}$ の配列の長さを要素とする配列を $\{l_{ij}\}$ とし、いまi を固定し $s = s_i$ と考えて、単に $\{a_j\}, \{l_j\}$ と表記する。

いかなるスコア化も行っていない状態では、s 中の全ての1-セグメントの左端もしくは右端はかならずスコア化可能パターンになっており、 $a_j$ を連続スコア化することによって $l_j$ 点を獲得することができる。

しかし、 $a_j$ は左端のスコア化可能パターンを $a_{j-1}$ と、右端のスコア化可能パターンを $a_{j+1}$ とそれぞれ共有しており、 $a_j$ がどのような方法でスコア化を行うかによって、 $a_{j-1}, a_{j+1}$ で可能なスコア化の手法が制限される。

スコア化のやりかたと、隣接する1-セグメントへの影響

いま $a_j$ を起点として考える。

$l_j > 1$ のとき

の左端のスコア化可能パターンをスコア化するとの右端のスコア化可能パターンは消失する。また、の’1’ を1つ消費するので、が1減少する。
1. そのままスコア化を続け、 $l_j$ 回のスコア化を行うと、 $a_j$ の右端と $a_{j+1}$ の境界は…1001… となり、 $a_{j+1}$ の左端のスコア化可能パターンも消失する。
2. $l_j - 1$ 回のスコア化を行うと、 $a_j$ の右端と $a_{j+1}$ の境界は…0101… となり、 $a_{j+1}$ の左端のスコア化可能パターンは温存される。スコア化の回数は $l_j - 1$ 回より少なくても $a_{j+1}$ のスコア化可能パターンの状態は変わらないので、 $l_j - 1$ より少ない回数のスコア化のことは考えなくても良い。
上記1, 2 について左端を右端に、 $a_{j+1}$ を $a_{j-1}$ に置き換えても同様である。
スコア化を行わない場合、両端のスコア化可能パターンが温存される。

$l_j == 1$ のとき

左端のスコア化可能パターンをスコア化すると、常に右端のスコア化パターンも消失する。 $l_{j-1}$ が1減少する。
上記で左端を右端に置き換えても同様である。
スコア化を行わない場合、両端のスコア化可能パターンが温存される。

問題に適用する

いま、s を左から順に、手法を選びながらスコア化し、s全体のスコアを最大化することを考える。

$a_1$

まず、 $a_1$ は左端にスコア化可能パターンを持たないので、

右端のスコア化可能パターンを用いて連続スコア化し、 $l_1$ 点を獲得する（と同時に $l_2$ --）か、
スコア化を行わずに右端のスコア化可能パターンを温存するか

の2択である。

$a_2$

で1 を選んだ場合は
1. 右端のスコア化可能パターンから連続スコア化し、 $l_2$ -1 点を獲得し、 $l_3$ --。
2. スコア化を行わず、右端のスコア化可能パターンを温存する。
で2 を選んだ場合は
1. 右端のスコア化可能パターンから連続スコア化し、 $l_2$ 点を獲得、 $l_3$ --。
2. スコア化を行わず、右端のスコア化可能パターンを温存する。
3. 左端のスコア化可能パターンから連続スコア化し、
  1. $l_2$ 点を獲得し、右端のスコア化可能パターンを失う。
  2. ( $l_2 > 1$ のとき) $l_2$ -1 点を獲得し、右端のスコア化パターンを温存する。

以上のパターンの内、 $a_3$ のスコア化手法に影響があるのは $a_3$ の左端のパターンであり、これで分類すると

$a_3$ の左端にスコア化パターンあり (1.2, 2.2, 2.3.2)
の左端にスコア化パターンがなく
- $l_3$ が減少していない (2.3.1)
- $l_3$ が減少している (1.1, 2.1)

それぞれのカテゴリーで最大になるスコアを保存し、 $a_3, a_4, a_5 ...$ についても同様に計算をしていけば、s全体で得られるスコアの最大値が求められる。