ベスパリブ

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

ABC 115: D問題の解説 (Python3)

問題:AtCoder Beginner Contest 115: D - Christmas

公式解説PDF:https://img.atcoder.jp/abc115/editorial.pdf

公式解説動画:なし

有志解説動画:【競技プログラミング】AtCoder Beginner Contest 115 D問題をJuliaで解く - YouTube

解説

考察問題であり、数学です。

方針としては、「レベルiバーガーの下からX層にあるパティPの総数」を f(i, X) とし、その漸化式を導くことで問題を解きます。


とりあえず各レベルバーガーを書いてみます。わかりやすさのためパティを赤色にしています。

レベル バーガー 層の総数 パティの総数
0 P 1 1
1 BPPPB 5 3
2 BBPPPBPBPPPBB 13 7
3 BBBPPPBPBPPPBBPBBPPPBPBPPPBBB 29 15

レベル L バーガー (L≥1) とは、バン 1 枚、レベル L−1 バーガー、パティ 1 枚、レベル L−1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。という性質が重要で、この性質から、

  • レベル2バーガーにはレベル1バーガーが2つ存在している
  • レベル3バーガーにはレベル2バーガーが2つ存在している
  • レベル4バーガーにはレベル3バーガーが2つ存在している
  • ...

という性質を頭にいれておきます。


レベルNバーガーの層(パティとバン)の総数を a_iとします。 a_iはいくらでしょうか?

レベルNバーガーは、「レベルN-1バーガーを2つ+ 2枚のバン + 1枚のパティ」でできます。よって、

 a_i = 2 a_{i-1} + 3

です。 a_iは奇数であることもわかります。


レベルNバーガーのパティの総数を p_iとします。 p_iはいくらでしょうか?

レベルNバーガーは、「レベルN-1バーガーのパティの数*2 + 1枚のパティ」でできます。よって、

 p_i = 2 p_{i-1} + 1

です。


今、解きたい問題は「ルンルンがレベルNバーガーのX層を下から食べる。食べたパティの枚数はなにか?」です。これは言い換えれば「レベルiバーガーの下からX層にあるパティPの総数」を求めることと同値です。

「レベルiバーガーの下からX層にあるパティPの総数」を f(i, X) とします。

例を列挙すると、

  •  f(0, 0) = 0
  •  f(0, 1) = 1
  •  f(1, 0) = 0
  •  f(1, 1) = 0
  •  f(1, 2) = 1
  •  f(1, 3) = 2
  •  f(1, 4) = 3
  •  f(1, 5) = 3
  • ...

です。


さて、戦略としては f(i,X)の漸化式を立てることです。

レベルNバーガーはその性質上、真ん中にP(パティ)がくることがわかっています。

また、真ん中より右側には「レベルN-1バーガー + バン」ということがわかります。

また、真ん中より左側には「レベルN-1バーガー + バン」ということがわかります。

ということで、3つの場合分けをすればなんかいけそうだとあたりがつきます。

  • Xが真ん中より右側のとき
  • Xが真ん中のとき
  • Xが真ん中より左側のとき

の3パターンで漸化式を立てます。

 a_iは必ず奇数より、真ん中のPは右から \frac{a_i + 1} {2}の位置にあります。

わかりやすくするため、真ん中の位置を median_i = \frac{a_i + 1} {2}とします。

すると漸化式は、

  • i = 0のとき

{} $$ f(0, X) = \left\{ \begin{array}{} 1 & ( X \geqq 1 ) \\ 0 & ( X < 1 ) \end{array} \right. $$

  • i >= 1 のとき

{} $$ f(i, X) = \left\{ \begin{array}{} f(i-1, X-1) & ( X < median_i ) (Xが右側) \\ p_{i-1} + 1 & ( X = median_i ) (Xが真ん中) \\ p_{i-1} + 1 + f(i-1, X-median_i) & ( X > median_i ) (Xが左側) \end{array} \right. $$

となります。

なぜこうなるのか?というのはまあ、以下のような例をお絵かきしてみて法則性を見つけ出します。


f:id:takeg:20190921151530p:plain
Xが右側のとき


f:id:takeg:20190921151532p:plain
Xが真ん中のとき


f:id:takeg:20190921151830p:plain
Xが左側のとき

あとはこれを解くプログラムを書きます。


ちなみに、

  •  a_i =2^{i+2} - 3
  •  p_i = 2^{i+1} - 1

と一般項を変形できるらしいので、こちらを使うことで高速化できます。

コーナーケース

  • 特になし

実装1(再帰関数)

# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(10000)  # 再帰関数のRecursionError対策


def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ(層の総数)(必ず奇数)
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    def f(n, x):
        """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
        if n == 0:
            return 0 if x <= 0 else 1

        median = (As[n]+1)//2

        if x < median:
            return f(n-1, x-1)
        elif x == median:
            return Ps[n-1] + 1
        elif x > median:
            return Ps[n-1] + 1 + f(n-1, x-median)

    ans = f(N, X)

    print(ans)


if __name__ == "__main__":
    solve()

計算量は O(N)です 。

実装2(DP)

漸化式を解くといったらDPなので、DPで解こうとしたら入力例3でMemoryErrorが起きました。Xの取りうる値がでかすぎてリストの作成でコケます。以下のプログラムではACできません。

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


def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ(層の総数)(必ず奇数)
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    # dp[i][x] := レベルiバーガーの下からx層に含まれているパティの総数
    dp = [[0]*(X+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, X+1):
        dp[0][i] = 1

    # 漸化式を解く
    for i in range(1, N+1):
        median = (As[i]+1)//2
        for x in range(X+1):
            if x < median:
                dp[i][x] = dp[i-1][x-1]
            elif x == median:
                dp[i][x] = Ps[i-1] + 1
            else:
                dp[i][x] = Ps[i-1] + 1 + dp[i-1][x-median]

    print(dp[N][X])



if __name__ == "__main__":
    solve()

「テスト駆動Python」写経 CHAPTER1

www.amazon.co.jp

1 はじめてのpytest

pytestを使ったテスト駆動開発についての本です。

pytestを実行する

test_one.py

def test_passing():
    assert (1, 2, 3) == (1, 2, 3)

テストを実行します。

$ pytest test_one.py
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 1 item                                                                                                                                                                                                                      

test_one.py .                                                                                                                                                                                                                  [100%] 

===================================================================================================== 1 passed in 0.01 seconds ====================================================================================================== 

より詳細に知りたい場合は、-vオプションを追加します。

$ pytest -v test_one.py
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0 -- C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\python.exe
cachedir: .pytest_cache
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 1 item                                                                                                                                                                                                                      

test_one.py::test_passing PASSED                                                                                                                                                                                               [100%] 

===================================================================================================== 1 passed in 0.01 seconds ====================================================================================================== 

test_two.py

def test_falling():
    assert(1,2,3) == (3,2,1)

テストを実行します。

$ pytest -v test_two.py
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0 -- C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\python.exe
cachedir: .pytest_cache
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 1 item                                                                                                                                                                                                                      

test_two.py::test_falling FAILED                                                                                                                                                                                               [100%] 

============================================================================================================= FAILURES ============================================================================================================== 
___________________________________________________________________________________________________________ test_falling ____________________________________________________________________________________________________________ 

    def test_falling():
>       assert(1,2,3) == (3,2,1)
E       assert (1, 2, 3) == (3, 2, 1)
E         At index 0 diff: 1 != 3
E         Full diff:
E         - (1, 2, 3)
E         ?  ^     ^
E         + (3, 2, 1)
E         ?  ^     ^

test_two.py:2: AssertionError
===================================================================================================== 1 failed in 0.04 seconds ====================================================================================================== 

pytestはファイルやディレクトリを指定しない場合、現在のディレクトリとそのサブディレクトリでテストを検索し実行します。pytestが実行されるのはtest_で始まるファイルと、_testで終わるファイル。

# ファイルを指定してテスト実行
$ pytest -v test_one.py

# 複数のファイルを指定してテスト実行
$ pytest -v tasks/test_three.py tasks/test_four.py

# ディレクトリを指定してテスト実行
$ pytest -v tasks

# 現在のディレクトリ以下すべてテスト実行
$ pytest -v

pytestのテストディスカバリ

pytestの実行するテストを検索する部分を「テストディスカバリ(test discovery)」といいます。

pytestの命名規則に準拠した名前がついたものは、pytestのテストが実行されます。その命名規則は以下の3つ。

  1. 「test_*.py」または「*_test.py」というファイル名
  2. 「test_*」という名前のメソッドや関数
  3. 「Test*」という名前のクラス

test_one.pyという名前のファイルに、「hoge()」という名前の関数があってもそれはテストされない。

このテストディスカバリルールは変更することが可能。

テストを1つだけ実行する

ファイルの中の関数を指定して、テストしたい関数のみをテストすることができます。

$ pytest -v tasks/test_one.py::test_passing

pytestのオプション

-h, --help

$ pytest --help

pytestのヘルプです。

--collect-only

$ pytest --collect-only
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 6 items                                                                                                                                                                                                                     
<Module test_one.py>
  <Function test_passing>
<Module test_two.py>
  <Function test_falling>
<Module tasks/test_four.py>
  <Function test_asdict>
  <Function test_replace>
<Module tasks/test_three.py>
  <Function test_defaults>
  <Function test_member_access>

=================================================================================================== no tests ran in 0.02 seconds ==================================================================================================== 

実行されるテストを表示します。テスト実行前にチェックするのに役立ちます。

-k EXPRESSION

$ pytest -k "asdict or defaults" --collect-only

-k オプションは、実行するテスト関数を、式を使って検索できるようにするフィルタ。

# asdictまたはdefaultsと名前がつくやつを指定
$ pytest -k "asdict or defaults" --collect-only
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 6 items / 4 deselected / 2 selected                                                                                                                                                                                         
<Module tasks/test_four.py>
  <Function test_asdict>
<Module tasks/test_three.py>
  <Function test_defaults>

=================================================================================================== 4 deselected in 0.02 seconds ==================================================================================================== 

# asdictまたはdefaultsと名前がつくやつのみテスト実行
$ pytest -v -k "asdict or defaults"
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0 -- C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\python.exe
cachedir: .pytest_cache
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 6 items / 4 deselected / 2 selected                                                                                                                                                                                         

tasks/test_four.py::test_asdict PASSED                                                                                                                                                                                         [ 50%] 
tasks/test_three.py::test_defaults FAILED                                                                                                                                                                                      [100%] 

============================================================================================================= FAILURES ============================================================================================================== 
___________________________________________________________________________________________________________ test_defaults ___________________________________________________________________________________________________________ 

    def test_defaults():
        """Using no parameters should invoke defaults."""
>       t1 = Task()
E       TypeError: __new__() missing 4 required positional arguments: 'summary', 'owner', 'done', and 'id'

tasks\test_three.py:17: TypeError
========================================================================================= 1 failed, 1 passed, 4 deselected in 0.04 seconds ========================================================================================== 

-m MARKEXPR

マーカーを使ってテスト関数の一部にマークを付けると、それらの関数をまとめて実行できるようになります。たとえば、それぞれ別ファイルに含まれているtest_replace()とtest_member_access()を実行するために、それらにマークをつけます。

マーカーには好きな名前をつけることができます。run_these_pleaseというマークをつけるには、以下のようにします。

import pytest
...
@pytest.mark.run_these_please
def test_member_access():
...

test_replace()にも同じマークをつけます。

# マークをつけた関数のみをテスト実行する
$ pytest -v -m run_these_please
======================================================================================================== test session starts ========================================================================================================
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0 -- C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\python.exe
cachedir: .pytest_cache
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 6 items / 4 deselected / 2 selected                                                                                                                                                                                         

tasks/test_four.py::test_replace PASSED                                                                                                                                                                                        [ 50%] 
tasks/test_three.py::test_member_access FAILED                                                                                                                                                                                 [100%] 

============================================================================================================= FAILURES ============================================================================================================== 
________________________________________________________________________________________________________ test_member_access _________________________________________________________________________________________________________ 

    @pytest.mark.run_these_please
    def test_member_access():
        """Check .firld functionality of namedtuple."""
>       t = Task("buy milk", "brian")
E       TypeError: __new__() missing 2 required positional arguments: 'done' and 'id'

tasks\test_three.py:26: TypeError
========================================================================================================= warnings summary ========================================================================================================== 
C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\lib\site-packages\_pytest\mark\structures.py:332
  C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\lib\site-packages\_pytest\mark\structures.py:332: PytestUnknownMarkWarning: Unknown pytest.mark.run_these_please - is this a typo?  You can register custom marks 
to avoid this warning - for details, see https://docs.pytest.org/en/latest/mark.html
    PytestUnknownMarkWarning,

-- Docs: https://docs.pytest.org/en/latest/warnings.html
=================================================================================== 1 failed, 1 passed, 4 deselected, 1 warnings in 0.04 seconds ==================================================================================== 

-x, --exitfirst

pytest -x

pytestは通常、テスト関数でassertが失敗したり例外が発生したらテストの実行はそこで中止され、そのテストは失敗となります。そして次のテストを実行します。テストが失敗したら次のテストを実行せずにテストセッション全体を底で中止したい場合、この-xオプションを使います。

$ pytest -x
======================================================================================================== test session starts ========================================================================================================
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 6 items                                                                                                                                                                                                                     

test_one.py .                                                                                                                                                                                                                  [ 16%] 
test_two.py F

============================================================================================================= FAILURES ============================================================================================================== 
___________________________________________________________________________________________________________ test_falling ____________________________________________________________________________________________________________ 

    def test_falling():
>       assert(1,2,3) == (3,2,1)
E       assert (1, 2, 3) == (3, 2, 1)
E         At index 0 diff: 1 != 3
E         Use -v to get the full diff

test_two.py:2: AssertionError

========================================================================================== 1 failed, 1 passed, 1 warnings in 0.05 seconds =========================================================================================== 

test_one.pyは成功し、test_two.pyで失敗し、そこでテストセッション全体が終了していることがわかります。

--tb=no

$ pytest --tb=no

テスト失敗時のトレースバックをオフにします。失敗したテストを簡潔に表示したい場合につかいます。

$ pytest --tb=no
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 6 items                                                                                                                                                                                                                     

test_one.py .                                                                                                                                                                                                                  [ 16%] 
test_two.py F                                                                                                                                                                                                                  [ 33%] 
tasks\test_four.py ..                                                                                                                                                                                                          [ 66%] 
tasks\test_three.py FF                                                                                                                                                                                                         [100%] 

========================================================================================== 3 failed, 3 passed, 1 warnings in 0.05 seconds =========================================================================================== 

--maxfail=num

$ pytest --maxfail=2

「テストがnum個失敗したらテストセッション全体を中止する」ときに使います。 --maxfail=2 で、テストが2つ失敗したらテストセッション全体を中止します。

-s, --capture=method

# 出力のキャプチャを無効にし、出力が標準出力に書き出される
$ pytest -s
# または、
$ pytest --capture=no

デフォルトではprint()文は標準出力に表示されませんが、この-sを使うとprint()文を標準出力に出力します。

test_one.py

def test_passing():
    assert (1, 2, 3) == (1, 2, 3)
    print("End!")

テストを実行します。

# デフォルトでは、print()文は出力されない
$ pytest test_one.py
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 1 item                                                                                                                                                                                                                      

test_one.py .                                                                                                                                                                                                                  [100%] 

===================================================================================================== 1 passed in 0.02 seconds ====================================================================================================== 

# -sオプションをつけると、print()文が出力される
$ pytest -s test_one.py
======================================================================================================== test session starts ======================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 1 item                                                                                                                                                                                                                      

test_one.py End!
.

===================================================================================================== 1 passed in 0.02 seconds ====================================================================================================== 

他にも --capture=sysや --capture=fd などがあるが、それらはよくわからないしあんまり使わなそう。

--lf, --last-failed

$ pytest --lf

最後に失敗したテストだけが再び実行されます。失敗しているテストだけを実行するときに便利。

--ff, --failed-first

$ pytest --ff

基本的に--last-failedと同じで、最後に失敗したテストを実行した後、残りの成功しているテストを実行します。

-v, --verbose

$ pytest -v

通常よりも詳細に情報が出力されます。詳しいエラー内容を知りたいときに便利。

-q, --quit

$ pytest -q --tb=line test_two.py
F                                                                                                                                                                                                                              [100%] 
============================================================================================================= FAILURES ============================================================================================================== 
C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1\test_two.py:2: assert (1, 2, 3) == (3, 2, 1)
1 failed in 0.03 seconds

出力される情報が少なくなります。--tb=lineオプションと組み合わせることで失敗しているテストの行だけが表示されるようになります。

-l, --showlocals

失敗しているテストのローカル変数とそれらの値がトレースバックで表示されます。

$ pytest -l tasks/test_four.py
======================================================================================================== test session starts ========================================================================================================
platform win32 -- Python 3.7.4, pytest-5.0.1, py-1.8.0, pluggy-0.12.0
rootdir: C:\Users\XXXX\workspace\my-practice\PythonTestingWithPytest\ch1
collected 2 items                                                                                                                                                                                                                     

tasks\test_four.py .F                                                                                                                                                                                                          [100%]

============================================================================================================= FAILURES ============================================================================================================== 
___________________________________________________________________________________________________________ test_replace ____________________________________________________________________________________________________________ 

    @pytest.mark.run_these_please
    def test_replace():
        """_replace() should change passed in fields."""
        t_before = Task("finish book", "brian", False)
        t_after = t_before._replace(id=10, done=True)
        t_expeceted = Task("finish book", "brian", True, 11)
>       assert t_after == t_expeceted
E       AssertionError: assert Task(summary=...e=True, id=10) == Task(summary='...e=True, id=11)
E         At index 3 diff: 10 != 11
E         Use -v to get the full diff


t_after    = Task(summary='finish book', owner='brian', done=True, id=10)
t_before   = Task(summary='finish book', owner='brian', done=False, id=None) 
t_expeceted = Task(summary='finish book', owner='brian', done=True, id=11)  

tasks\test_four.py:24: AssertionError

========================================================================================== 1 failed, 1 passed, 1 warnings in 0.04 seconds =========================================================================================== 

assertが失敗したときの、t_after, t_before, t_expectedの3つの変数の中身が表示されていることがわかります。

--tb=style

$ pytest --tb=no

失敗しているテストのトレースバックを出力する方法を変更します。

--tb=shortは、assertの行とエラーが評価された行だけが表示されます。

--tb=lineは、エラーが一行にまとめられます。

--tb=noは、トレースバックが完全になくなります。

--durations=N

$ pytest --durations=3

テストが実行された後に、最も時間がかかったN個のテスト/セットアップ/ティアダウンを表示します。テスト全体を高速化するときに役に立ちます。

--durations=0の場合は、最も時間がかかったものから順に全てのテストが表示されます。

--version

$ pytest --version

pytestのバージョンとインストールされているディレクトリを表示します。

$ pytest --version
This is pytest version 5.0.1, imported from C:\Users\XXXX\AppData\Local\Continuum\anaconda3\envs\pytestx\lib\site-packages\pytest.py

よく使うcondaコマンド

Conda Cheat Sheet

Conda Cheat Sheet

condaコマンド

仮想環境の作成

# conda create -n [仮想環境名]
> conda create -n py3x
# pythonのバージョンを指定したい場合は conda create -n [仮想環境名] python=3.6 など
> conda create -n py36 python=3.6

仮想環境の確認

> conda info -e

仮想環境の削除

> conda remove -n py37 --all

仮想環境の切り替え

# conda activate [仮想環境名]
> conda avtivate py36
# conda は省略可能
> activate py36

仮想環境から抜ける

> conda deactivate

パッケージのインストール

# djangoを仮想環境にインストールする
> conda install django
# djangoのバージョン2.1を指定したい場合は
> conda install django==2.1

仮想環境の保存(仮想環境のエクスポート)

# conda env export -n [仮想環境名] > [保存ファイル名(.yml)]
> conda env export -n pytestx > pytestx.yml

仮想環境の再構築(仮想環境のインポート)

# conda env create -f=[仮想環境のymlファイル]
> conda env create -f=pytestx.yml

参考

編集履歴

  • 2020/01/14、Conda Cheat Sheetの項目を追加

ABC 030: C問題の解説 (Python3)

問題:AtCoder Beginner Contest 030: C - 飛行機乗り

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

公式解説動画:なし

解説

二分探索問題です。

以下の解説は公式PDFの解説まんまです。

入力例1を考えます。


初期状態は以下のように、高橋くんは時刻0に空港Aにいます。

時刻 0 1 2 3 4 5 6 7 8 9 10 11 12 13
空港Aの出発時刻 1 5 7
空港Bの出発時刻 3 8 12 13
高橋くん A

次に、高橋くんは出発時刻が最も近い時刻1で空港Aを発ち、時刻X(=2)をかけて、時刻3に空港Bに到着します。

時刻 0 1 2 3 4 5 6 7 8 9 10 11 12 13
空港Aの出発時刻 1 5 7
空港Bの出発時刻 3 8 12 13
高橋くん B

次に、高橋くんは出発時刻が最も近い時刻3で空港Bを発ち、時刻Y(=3)をかけて、時刻6に空港Aに到着します。

時刻 0 1 2 3 4 5 6 7 8 9 10 11 12 13
空港Aの出発時刻 1 5 7
空港Bの出発時刻 3 8 12 13
高橋くん A

これで1往復しました。


次に、高橋くんは出発時刻が最も近い時刻7で空港Aを発ち、時刻X(=2)をかけて、時刻9に空港Bに到着します。

時刻 0 1 2 3 4 5 6 7 8 9 10 11 12 13
空港Aの出発時刻 1 5 7
空港Bの出発時刻 3 8 12 13
高橋くん B

次に、高橋くんは出発時刻が最も近い時刻12で空港Bを発ち、時刻X(=3)をかけて、時刻15に空港Aに到着します。

時刻 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
空港Aの出発時刻 1 5 7
空港Bの出発時刻 3 8 12 13
高橋くん A

これで2往復しました。

これ以上空港Aから出発することはできないので、答えは2往復です。


と、考え方は以上になります。

この問題の本質は「現在時刻に最も近い出発時刻をどう見つけるか」です。

入力例1において、空港Bのリストは [3, 8, 12, 13] です。現在時刻が9のとき、9以上で最も近い値はなにか?

これはリストの中身を線形探索するようなやり方をしたら全体の計算量はおそらく O(N^2)になりTLEします。

このような「ある値aに最も近いものを、リストの中から効率よく探す」といえば二分探索です。二分探索はリストの長さをNとすると、 O(logN)で探索することができ、これはリストの中身を線形探索するような O(N)よりもはるかに高速です。

Python3で二分探索はbisectモジュールを使うと簡単です。簡単な実行例は記事の最後に載せています。

コーナーケース

  • 特になし

実装

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

def solve():
    N, M = list(map(int, sys.stdin.readline().split()))
    X, Y = list(map(int, sys.stdin.readline().split()))
    As = list(map(int, sys.stdin.readline().split()))
    Bs = list(map(int, sys.stdin.readline().split()))
    As.sort()
    Bs.sort()

    ans = 0  # 最終的に出力する答え
    t = 0    # 現在時刻
    now_pos = "A"  # 現在の空港
    pre_a_i = 0  # 二分探索の前回のインデックス
    pre_b_i = 0  # 二分探索の前回のインデックス
    while True:
        if now_pos == "A":
            i = bisect.bisect_left(As, t, pre_a_i)
            if i >= N: break
            t = As[i] + X  # 空港Aを発ち、空港Bに到着した時刻t
            pre_a_i = i
            now_pos = "B"
        else:
            i = bisect.bisect_left(Bs, t, pre_b_i)
            if i >= M: break
            t = Bs[i] + Y  # 空港Bを発ち、空港Aに到着した時刻t
            pre_b_i = i
            now_pos = "A"
            ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

高速化のためpre_a_i, pre_b_iで探索範囲を狭めています。なくてもACするかも。

計算量は O(N logN + M logM) か...?(わからん)。

参考

bisectモジュールのきほん

import bisect

a = [10, 20, 20, 30, 40]
a.sort()  # aはソート済みであること

bisect_left

公式ドキュメントから引用

  • ソートされた順序を保ったまま x を a に挿入できる点を探し当てます。
  • リストの中から検索する部分集合を指定するには、パラメータの lo と hi を使います。デフォルトでは、リスト全体が使われます。
  • x がすでに a に含まれている場合、挿入点は既存のどのエントリーよりも前(左)になります。
a = [10, 20, 20, 30, 40]

bisect.bisect_left(a, 11)
# 1

bisect.bisect_left(a, 20)
# 1

bisect.bisect_left(a, 20, lo=2)
# 2

bisect.bisect_left(a, 42)
# 5

bisect.bisect_left(a, 20, lo=100)
# 100

bisect_right (bisect)

基本的にbisect_leftと同じ。

  • どのエントリーよりも後ろ(右)にくるような挿入点を返します。
a = [10, 20, 20, 30, 40]

bisect.bisect_right(a, 11)
# 1

bisect.bisect_right(a, 20)
# 3

bisect.bisect_right(a, 20, lo=2)
# 3

bisect.bisect_right(a, 42)
# 5

bisect.bisect_right(a, 20, lo=100)
# 100

Python3.7のeval()関数は長すぎる文字列を処理させようとするとエラーを吐かずに落ちることがある

TL;DR

Python3.7系だと、エラーを吐かずに終了することがあります。

現象

a = "1*"*100000
ans = eval(a[:-1])

print(ans)

print("end.")

自宅のPC(Windows10, 64bit, Python3.6.5)でこれを実行してみると、

>python hoge.py
Traceback (most recent call last):
  File "141/hoge.py", line 5, in <module>
    ans = eval(a[:-1])
RecursionError: maximum recursion depth exceeded during compilation

RecursionErrorが発生しました。

これをノートPC(Windows10, 64bit, Python3.7.1)で実行してみると、

>python hoge.py

>

エラーも吐かずに終了しました。「end.」も出力してないので、途中で落ちているっぽいです。

考えられる原因

  • 私のノートPCが原因
  • Pythonのバージョン違いによる挙動
  • 搭載メモリ容量の違いによる挙動
  • その他

ノートPCがPython3.7.1なので、とりあえず自宅デスクトップPCにPython3.7.1環境を構築して実験してみます。

> conda activate
(base) > conda create -n py371 python=3.7.1
Collecting package metadata: done
Solving environment: done


==> WARNING: A newer version of conda exists. <==
  current version: 4.6.8
  latest version: 4.7.11

Please update conda by running

    $ conda update -n base -c defaults conda



## Package Plan ##

  environment location: C:\Users\takey\Anaconda3\envs\py371

  added / updated specs:
    - python=3.7.1


The following packages will be downloaded:

    package                    |            build
    ---------------------------|-----------------
    ca-certificates-2019.5.15  |                1         166 KB
    certifi-2019.6.16          |           py37_1         156 KB
    openssl-1.1.1d             |       he774522_0         5.7 MB
    pip-19.2.2                 |           py37_0         1.9 MB
    python-3.7.1               |       h8c8aaf0_6        17.7 MB
    setuptools-41.0.1          |           py37_0         680 KB
    sqlite-3.29.0              |       he774522_0         962 KB
    vs2015_runtime-14.16.27012 |       hf0eaf9b_0         2.4 MB
    wheel-0.33.4               |           py37_0          57 KB
    ------------------------------------------------------------
                                           Total:        29.7 MB

The following NEW packages will be INSTALLED:

  ca-certificates    pkgs/main/win-64::ca-certificates-2019.5.15-1
  certifi            pkgs/main/win-64::certifi-2019.6.16-py37_1
  openssl            pkgs/main/win-64::openssl-1.1.1d-he774522_0
  pip                pkgs/main/win-64::pip-19.2.2-py37_0
  python             pkgs/main/win-64::python-3.7.1-h8c8aaf0_6
  setuptools         pkgs/main/win-64::setuptools-41.0.1-py37_0
  sqlite             pkgs/main/win-64::sqlite-3.29.0-he774522_0
  vc                 pkgs/main/win-64::vc-14.1-h0510ff6_4
  vs2015_runtime     pkgs/main/win-64::vs2015_runtime-14.16.27012-hf0eaf9b_0
  wheel              pkgs/main/win-64::wheel-0.33.4-py37_0
  wincertstore       pkgs/main/win-64::wincertstore-0.2-py37_0


Proceed ([y]/n)? y


Downloading and Extracting Packages
setuptools-41.0.1    | 680 KB    | ######################################################################## | 100%  
python-3.7.1         | 17.7 MB   | ######################################################################## | 100%  
vs2015_runtime-14.16 | 2.4 MB    | ######################################################################## | 100% 
wheel-0.33.4         | 57 KB     | ######################################################################## | 100% 
pip-19.2.2           | 1.9 MB    | ######################################################################## | 100%  
openssl-1.1.1d       | 5.7 MB    | ######################################################################## | 100%  
ca-certificates-2019 | 166 KB    | ######################################################################## | 100%  
certifi-2019.6.16    | 156 KB    | ######################################################################## | 100% 
sqlite-3.29.0        | 962 KB    | ######################################################################## | 100%  
Preparing transaction: done
Verifying transaction: done
Executing transaction: done
#
# To activate this environment, use
#
#     $ conda activate py371
#
# To deactivate an active environment, use
#
#     $ conda deactivate

(base) > conda activate py371
(py371) > python --version
Python 3.7.1

これでコードを実行してみます。

(py371) >python hoge.py

(py371) >

再現しました。原因はPythonのバージョンっぽいです。

Pythonのバージョンを色々変更して試した結果、Python3.6.9はRecursionErrorを吐き出し、Python3.7.0からエラーを吐かずに落ちました。

Python3.8系では直ってるのかわからないですけど、Python3.7系でeval()関数を使うときは注意しましょう。

参考

ABC 133: D問題の解説 (Python3)

問題:AtCoder Beginner Contest 133: D - Rain Flows into Dams

公式解説PDF:https://img.atcoder.jp/abc133/editorial.pdf

公式解説動画:https://youtu.be/8uowVvQ_-Mo?t=3228

解説

考察問題です。数式を変換してXに対する漸化式を導きます。

以下の解説は公式PDFの解説まんまです。

問題の性質により、山に降った雨の総量と、ダムに貯まった水の総量は同じなので、

 A_1+ A_2 + ... A_N = X_1 + X_2 + ... + X_N = S とします。

よって X_1は、

 X_1 = S - (X_2 + ... + X_N)    ・・・(式★)

になります。


また、

 \frac{X_i + X_{i+1}} {2} = A_i

より、

 X_i + X_{i+1} = 2 A_i

なので、(式★)は、

 X_1 = S - 2(A_2 + A_4 + A_{N-1}) と式変形することができます。

これで X_1 は求めることができました。


同様にして X_2, ..., X_N を順に求めて行けばよいですが、単純な2重ループだと O(N^2)になってしまいます。

そこで O(N)で解くために、

 X_i + X_{i+1} = 2 A_i より、

 X_{i+1} = 2 A_i - X_i

の漸化式をつくれるので、それを解いていけばOKです。

コーナーケース

  • 特になし

実装

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


def solve():
    N = int(sys.stdin.readline())
    As = list(map(int, sys.stdin.readline().split()))

    S = sum(As)
    Xs = [0]*N
    # 初期状態を決める(Xs[0])
    Xs[0] = S - 2 * sum(As[1:N:2])

    # 漸化式を解く
    for i in range(N-1):
        Xs[i+1] = 2*As[i] - Xs[i]

    print(*Xs)


if __name__ == "__main__":
    solve()

計算量は O(N) です。

ABC 131: D問題の解説 (Python3)

問題:AtCoder Beginner Contest 131: D - Megalomania

公式解説PDF:https://img.atcoder.jp/abc131/editorial.pdf

公式解説動画:https://youtu.be/XI8exXVxZ-Q?t=4046

解説

締切が早い仕事から順に終わらせていく貪欲法です。割と直感で思いつく解法ですが、なぜそれでよいのかの証明は解説PDFが詳しいです。

あんまり書くことないのですが、入力例1を考えてみます。

仕事i 仕事を終わらせるのに必要な時間 締切時刻
0 2 4
1 1 9
2 1 8
3 4 9
4 3 12

これを、締切が早い順に仕事を終わらせた場合、以下のようになります。

時刻 0 1 2 3 4 5 6 7 8 9 10 11
終わった仕事i 0 2 1 3 4

すべて締切に間に合います。


たとえば別の方法として、「仕事を終わらせるのに必要な時間が短いやつから終わらせていく」というのを思いつきますが、これだとたとえば、

i 仕事を終わらせるのに必要な時間 締切時刻
0 2 3
1 1 3
2 1 4

といった場合に、

時刻 0 1 2 3 4
終わった仕事i 1 2 0

となりますが、これは仕事0は締切時刻3に間に合っていません。


上の例を、締切が早いやつ順に仕事を終わらせてみると、

時刻 0 1 2 3 4
終わった仕事i 0 1 2

となり、これはすべて締切に間に合っています。

コーナーケース

  • 特になし

実装

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

class Work():
    """ 仕事クラス """
    def __init__(self, a, b):
        self.need_time = a  # 仕事を終わらせるのに必要な時間
        self.deadline = b   # 締切時刻


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

    works = []  # 仕事をリストにぶちこむ
    for _ in range(N):
        a, b = list(map(int, input().split()))
        works.append(Work(a, b))
    works.sort(key=lambda x: x.deadline)  # 締切が早い順にソート

    # 締切が早いやつから先に仕事を終らせる貪欲法
    now_time = 0  # 現在時刻
    for i in range(N):
        now_time += works[i].need_time
        if now_time > works[i].deadline:
            print("No")
            return
    print("Yes")



if __name__ == "__main__":
    solve()

計算量は O(N) です。

ちなみにですが、問題の制約は  1 ≤ N ≤ 2×10^5 となっていますので、まあ大体N=105くらいならPython O(N)で2秒の制約で解けるので、 O(N) で解く方法はないかな、とあたりをつけることができます。Pythonで N=106 はギリギリなイメージです。

参考