ライブラリについて

SortedSetは外部ライブラリであり、インストールする必要があるようだ。

pip install sortedcontainers

外部ライブラリなのに使えるの？とか思うだろうが、
どうやらAtCoderでは一部のライブラリがジャッジシステム？の中にインストールされているようだ

numpy==1.24.1
scipy==1.10.1
networkx==3.0
sympy==1.11.1
sortedcontainers==2.4.0
more-itertools==9.0.0
shapely==2.0.0
bitarray==2.6.2
PuLP==2.7.0
mpmath==1.2.1
pandas==1.5.2
z3-solver==4.12.1.0
scikit-learn==1.3.0
ac-library-python
cppyy==2.4.1

Docker上のpypy環境に入れようとしてあれこれ

筆者の実行環境はDocker上のコンテナでpypyを構築したものを使用している

参考記事：

pipを使用してインストールしようとしたらエラーがでた

 $ pypy3 -m pip install sortedcontainers
error: externally-managed-environment

× This environment is externally managed
╰─> To install Python packages system-wide, try apt install
    python3-xyz, where xyz is the package you are trying to
    install.
    
    If you wish to install a non-Debian-packaged Python package,
    create a virtual environment using python3 -m venv path/to/venv.
    Then use path/to/venv/bin/python and path/to/venv/bin/pip. Make
    sure you have pypy3-venv installed.
    
    If you wish to install a non-Debian packaged Python application,
    it may be easiest to use pipx install xyz, which will manage a
    virtual environment for you. Make sure you have pipx installed.
    
    See /usr/share/doc/python3.*/README.venv for more information.

note: If you believe this is a mistake, please contact your Python installation or OS distribution provider. You can override this, at the risk of breaking your Python installation or OS, by passing --break-system-packages.
hint: See PEP 668 for the detailed specification.

Microsoft Copilotにエラー貼り付けて質問してみたが、
どうやらapt-getでインストールしたパッケージだからpipが使えないらしい

そして苦戦しつつもインストール

色々質問しまくってコマンド実行していたらエラー文にそれっぽいのが

 $ pypy3 -m ensurepip
ensurepip is disabled in Debian/Ubuntu for the system python.

Python modules for the system python are usually handled by dpkg and apt-get.

    apt-get install python3-<module name>

Install the python3-pip package to use pip itself.  Using pip together
with the system python might have unexpected results for any system installed
module, so use it on your own risk, or make sure to only use it in virtual
environments.

藁にも縋る思いで実行してみたら何か通ったような出力

$ sudo apt-get install python3-sortedcontainers
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
Suggested packages:
  python-sortedcontainers-doc
The following NEW packages will be installed:
  python3-sortedcontainers
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 31.9 kB of archives.
After this operation, 163 kB of additional disk space will be used.
Get:1 http://deb.debian.org/debian bookworm/main amd64 python3-sortedcontainers all 2.4.0-2 [31.9 kB]
Fetched 31.9 kB in 0s (154 kB/s)                    
debconf: delaying package configuration, since apt-utils is not installed
Selecting previously unselected package python3-sortedcontainers.
(Reading database ... 62534 files and directories currently installed.)
Preparing to unpack .../python3-sortedcontainers_2.4.0-2_all.deb ...
Unpacking python3-sortedcontainers (2.4.0-2) ...
Setting up python3-sortedcontainers (2.4.0-2) ...

実行チェック

とりあえず昨日の記事(ABC297E)をSortedSetで書いてみたコードを実行してみる

main.py

import sys
from sortedcontainers import SortedSet

def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    N, K = rLI()
    A = sorted(rLI())
    q = SortedSet()
    L = [float('inf')]*K
    L[0] = A[0] 
    b = A[0]
    for a in A:
        q.add(a)
        q.add(a+A[0])
    for i in range(1,K):
        b=q[0]
        q.remove(b)
        if L[i-1] == b:
            b=q[0]
            q.remove(b)
        L[i] = b
        for a in A:
            q.add(a+b)
            while len(q)>K:q.pop()
    print(L[-1])    
    
if __name__ == '__main__':
    main()

テストしてみたら動いたようだ

 $ test
[INFO] online-judge-tools 11.5.1 (+ online-judge-api-client 10.10.1)
[INFO] 3 cases found
[WARNING] GNU time is not available: time

[INFO] sample-1
[INFO] time: 0.287316 sec
[SUCCESS] AC

[INFO] sample-2
[INFO] time: 0.058428 sec
[SUCCESS] AC

[INFO] sample-3
[INFO] time: 0.478311 sec
[SUCCESS] AC

[INFO] slowest: 0.478311 sec  (for sample-3)
[SUCCESS] test success: 3 cases

そしてAtCoderのサイトに提出したら無事にAC

どうやら問題なくいけたようだ。

まとめ

Dockerでapt-getして入れたpypy3はpipできないようなので

$ apt-get install python3-sortedcontainers

でインストールしよう

でもAtCoder Libraryはこの方法では無理そうなのでまた今度調べます…