やるだけPython競プロ日誌

競プロの解説をPythonでやっていきます。できるだけ初心者に分かりやすいように『やるだけ』とかは言わないようにします。コメントについては必ず読んでいます。どんなに細かいことでもいいのでコメントくださればうれしいです。

Flask 1.0 has released! Flask 1.0での変更点

2018/4/26にFlaskのversion 1.0がリリースされました。


以下にその変更点を訳してまとめておきます。翻訳は完了しました。誤った部分があればご指摘ください。

Python2.6 と 3.3のサポートが終了しました

Python 2.6 and 3.3 are no longer supported. (pallets/meta#24)

要求されるライブラリのバージョンは以下の通りです: Werkzeug >= 0.14, Jinja >= 2.10, itsdangerous >= 0.24, Click >= 5.1.

Bump minimum dependency versions to the latest stable versions: Werkzeug >= 0.14, Jinja >= 2.10, itsdangerous >= 0.24, Click >= 5.1. (#2586)

コンソールから実行された際、app.runを無視するようになりました。これによって、デバッグを煩わせる振る舞いを無くします。

Skip app.run when a Flask application is run from the command line. This avoids some behavior that was confusing to debug.

JSONIFY_PRETTYPRINT_REGULARのデフォルトの値をFalseにしました。jsonify()デバッグモードではデフォルトでインデントで整えられたコンパクトな返り値を返します。

Change the default for JSONIFY_PRETTYPRINT_REGULAR to False. jsonify() returns a compact format by default, and an indented format in debug mode. (#2193)

Flask.__init__は引数 host_matchingを取るようになり、それをurl_mapにセットするようになりました

Flask.__init__ accepts the host_matching argument and sets it on url_map. (#1559)

Flask.__init__は引数 static_host_argumentを取るようになり、静的ルートを定義するときの引数hostとしてにそれを渡すようになりました。

Flask.__init__ accepts the static_host argument and passes it as the host argument when defining the static route. (#1559)

send_file()Unicodeattachment_filenameでサポートしました。

send_file() supports Unicode in attachment_filename. (#2223)

url_for()からhandle_url_build__error()_schemeを渡すようになりました

Pass _scheme argument from url_for() to handle_url_build_error(). (#2017)

add_url_rule()が引数 provide_automatic_optionsOPTIONSを追加することを無効にするために受け取れるようになりました。

add_url_rule() accepts the provide_automatic_options argument to disable adding the OPTIONS method. (#1489)

MethosViewサブクラスがメソッドハンドラをベースクラスから受け継ぐようになりました

MethodView subclasses inherit method handlers from base classes. (#1936)

リクエストの始めのセッションを開く段階で起こったエラーが appのエラーハンドラで処理されるようになりました

Errors caused while opening the session at the beginning of the request are handled by the app’s error handlers. (#2254)

Blueprintにjson_encoderjson_decoderが appのエンコーダとデコーダを上書きするために追加されました。

Blueprints gained json_encoder and json_decoder attributes to override the app’s encoder and decoder. (#1898)

Flask.make_response()が、レスポンスのタイプが正しくない場合TypeErrorValueErrorを挙げるようになりました。エラーメッセージが、タイプの違いを説明するために分かりやすくなりました。

Flask.make_response() raises TypeError instead of ValueError for bad response types. The error messages have been improved to describe why the type is invalid. (#2256)

アプリケーションによって作成されたルートを出力するためにroutesCLIコマンドに追加しました。

Add routes CLI command to output routes registered on the application. (#2259)

セッションのドメインのクッキーが素のhostnameか IPアドレスだった場合、警告するようになりました。Chromeのように一部のブラウザでは正しく動作しないからです。

Show warning when session cookie domain is a bare hostname or an IP address, as these may not behave properly in some browsers, such as Chrome. (#2282)

IPアドレスをセッションのクッキーのドメインとして受け入れるようになりました。

Allow IP address as exact session cookie domain. (#2282)

SERVER_NAMEを通して検出された場合、SESSION_COKKIE_DOMAINが自動で設定されるようになりました

SESSION_COOKIE_DOMAIN is set if it is detected through SERVER_NAME. (#2282)

FLASK_APPの引数のないapp factoryのcreate_appmake_appを自動検出するようになりました。

Auto-detect zero-argument app factory called create_app or make_app from FLASK_APP. (#2297)

flaskコマンドで実行する際、factory関数にscript_infoパラメータを与えなくてもよくなりました。もし一つのパラメータ、あるいは、script_infoというパラメータを取る際、ScriptInfoオブジェクトが渡されます。

Factory functions are not required to take a script_info parameter to work with the flask command. If they take a single parameter or a parameter named script_info, the ScriptInfo object will be passed. (#2319)

FLASK_APP=myproject.app:create_app('dev')のように、必要ならばFLASK_APPを引数とともにapp factoryに渡せるようになりました。

FLASK_APP can be set to an app factory, with arguments if needed, for example FLASK_APP=myproject.app:create_app('dev'). (#2326)

pip install -eは未だ最適ですが、FLASK_APPは可編集モードでインストールされていないローカルなパッケージを指定できるようになりました。

FLASK_APP can point to local packages that are not installed in editable mode, although pip install -e is still preferred. (#2414)

Viewクラスのアトリビュートprovide_automatic_optionsadd_url_rule()で検出されるようにas_view()に設定されるようになりました。

The View class attribute provide_automatic_options is set in as_view(), to be detected by add_url_rule(). (#2316)

エラー処理はblueprint, code, app, code, blueprint, exception, app, exceptionに登録されたハンドラを試すようになりました。

Error handling will try handlers registered for blueprint, code, app, code, blueprint, exception, app, exception. (#2314)

セッションがすべてのリクエストの間アクセスされ(消去されなかっ)た場合、Cookieがレスポンスの Varyヘッダーに追加されるようになりました。

Cookie is added to the response’s Vary header if the session is accessed at all during the request (and not deleted). (#2288)

test_request_context()が引数subdomainurl_schemeをベースURLを作成する際に受け取れるようになりました。

test_request_context() accepts subdomain and url_scheme arguments for use when building the base URL. (#1621)

APPLICATION_ROOT'/'をデフォルトで設定するようになりました。これは、APPLICATION_ROOTNoneに設定していた時に暗黙的に行われていたことです。

Set APPLICATION_ROOT to '/' by default. This was already the implicit default when it was set to None.

TRAP_BAD_REQUEST_ERRORSがデフォルトでデバッグモード中に有効になりました。

デバッグモード中、一般的な bad request message の代わりにBadRequestKeyErrorが正しくないキーとともにメッセージを持つようになりました。

TRAP_BAD_REQUEST_ERRORS is enabled by default in debug mode. BadRequestKeyError has a message with the bad key in debug mode instead of the generic bad request message. (#2348)

セッションクッキー内に異なる型を保存するためにTaggedJSONSerializerとともに新しいタグを登録できるようになりました。

Allow registering new tags with TaggedJSONSerializer to support storing other types in the session cookie. (#2352)

リクエストがスタック文脈にプッシュされていない場合のみにセッションが開かれるようになりました。これにより containing viewを使った同じセッションにstream_with_context()ジェネレータを使ってアクセスすることが可能になりました。

Only open the session if the request has not been pushed onto the context stack yet. This allows stream_with_context() generators to access the same session that the containing view uses. (#2354)

テストクライアントのリクエストメソッドに jsonキーワードの引数を追加しました。これにより、与えられたオブジェクトをJSONとしてダンプして、適切なコンテントタイプを充てることができるようになります。

Add json keyword argument for the test client request methods. This will dump the given object as JSON and set the appropriate content type. (#2358)

RequestResponseクラスの両方に登録されたmix-inにJSONハンドルを抽出します。これは、JSONレスポンスのテストを非常に簡単にするために、レスポンスにis_json()メソッドとget_json()メソッドを追加します。

Extract JSON handling to a mixin applied to both the Request and Response classes. This adds the is_json() and get_json() methods to the response to make testing JSON response much easier. (#2358)

エラー処理のキャッシュを無くしました。なぜなら、それがエクセプション継承の階層に予期できない結果をもたらすからです。もしMROをトラバースしたくなければ、各エラーにハンドラを明示的に登録してください。

Removed error handler caching because it caused unexpected results for some exception inheritance hierarchies. Register handlers explicitly for each exception if you want to avoid traversing the MRO. (#2362)

世界協定時でない時間のJSONエンコードに誤りが発生する問題を修正しました

Fix incorrect JSON encoding of aware, non-UTC datetimes. (#2374)

jinja_envが既にアクセスされていても、テンプレート自動再読み込みはデバッグモードを優先するようになりました。

Template auto reloading will honor debug mode even even if jinja_env was already accessed. (#2373)

以下の非推奨のコードが削除されました。

The following old deprecated code was removed. (#2385)

flask.ext - flask.ext名前空間を通す代わりに拡張機能をじかに名前でインポートします。例えば、 import flask.ext.sqlalchemyimport flask_alchemyになります。

flask.ext - import extensions directly by their name instead of through the flask.ext namespace. For example, import flask.ext.sqlalchemy becomes import flask_sqlalchemy.

Flask.init_jinja_globals - Flask.create_jinja_environment()に代わりに拡張されました

Flask.init_jinja_globals - extend Flask.create_jinja_environment() instead.

Flask.error_handlers - Flask.error_handler_specを追跡に使用し、Flask.errorhandler()をハンドラの登録に使用してください。

Flask.error_handlers - tracked by Flask.error_handler_spec, use Flask.errorhandler() to register handlers.

Flask.request_globals_class - Flask.app_ctx_globals_classを代わりに使用してください。

Flask.request_globals_class - use Flask.app_ctx_globals_class instead.

Flask.static_path - Flask.static_url_pathを代わりに使用してください。

Flask.static_path - use Flask.static_url_path instead.

Request.module - Request.blueprintを代わりに使用してください。

Request.module - use Request.blueprint instead.

Request.jsonプロパティが非推奨ではなくなりました。

The Request.json property is no longer deprecated. (#1421)

EnvironBuilderDicttest_client.openに渡すことがサポートされました。

Support passing a EnvironBuilder or dict to test_client.open. (#2412)

python-dotenvがインストールされていた場合、flaskコマンドとFlask.run()環境変数.env.flaskenvから読み込むようになりました。

The flask command and Flask.run() will load environment variables from .env and .flaskenv files if python-dotenv is installed. (#2416)

テストクライアントにフルURLを渡すとき、スキーム内のURLがPREFERRED_URL_SCHEMEの代わりに渡されるようになりました。

When passing a full URL to the test client, the scheme in the URL is used instead of PREFERRED_URL_SCHEME. (#2430)

Flask.loggerがシンプルになりました。LOGGER_HANDLER_POLICYのコンフィグが削除されました。ロガーの名前は常にflask.appになりました。ロガーの名前は常にflask.appです。レベルは最初のアクセス時にのみ設定され、毎回Flask.debugをチェックすることはしません。 Flask.debugに依存するものではなく、使用されるフォーマットは1つだけです。ハンドラは削除されておらず、ハンドラがすでに設定されていない場合にのみハンドラが追加されます。

Flask.logger has been simplified. LOGGER_NAME and LOGGER_HANDLER_POLICY config was removed. The logger is always named flask.app. The level is only set on first access, it doesn’t check Flask.debug each time. Only one format is used, not different ones depending on Flask.debug. No handlers are removed, and a handler is only added if no handlers are already configured. (#2436)

Blueprint view関数の名前はドットを含まなくなりました。

Blueprint view function names may not contain dots. (#2450)

いくつかの場合で誤ったRangeのリクエストにより起きるValueErrorが修正されました。

Fix a ValueError caused by invalid Range requests in some cases. (#2526)

開発用サーバーがデフォルトでスレッディングを行うようになりました。

The development server uses threads by default. (#2529)

silent=Trueでコンフィグを読み込んだ時、ENOTDIRエラーが無視されるようになりました。

Loading config files with silent=True will ignore ENOTDIR errors. (#2581)

--cert--keyのオプションをflask runに渡すことで、開発用サーバがHTTPSを使用して実行するようになりました。

Pass --cert and --key options to flask run to run the development server over HTTPS. (#2606)

セッションクッキーのSameSite属性を操作するために、SESSION_COOKIE_SAMESITEを追加しました。

Added SESSION_COOKIE_SAMESITE to control the SameSite attribute on the session cookie. (#2607)

テスト用のFlask CLIコマンドを呼び出すためのクリックランナーを作成するためにtest_cli_runner()を追加しました。

Added test_cli_runner() to create a Click runner that can invoke Flask CLI commands for testing. (#2636)

サブドメインマッチングがデフォルトで無効にされ、SERVER_NAMEを設定することが暗黙的にサブドメインマッチングを有効にすることがなくなりました。有効にするには、Flaskコンストラクタにsubdomain_matching=Trueを渡してください。

Subdomain matching is disabled by default and setting SERVER_NAME does not implicily enable it. It can be enabled by passing subdomain_matching=True to the Flask constructor. (#2635)

blueprintのurl_prefixがappに登録されたとき、末尾に単独のスラッシュがあった場合、それを取り除くようになりました。

A single trailing slash is stripped from the blueprint url_prefix when it is registered with the app. (#2629)

silentが true の時、Request.get_json()が解析に失敗した場合、結果をキャッシュしなくなりました。

Request.get_json() doesn’t cache the result if parsing fails when silent is true. (#2651)

Request.get_json()は任意のエンコーディングをサポートしなくなりました。以降のJSONUTF-8によりエンコードされた、RFC 8259準拠のものが推奨されます。しかし、FlaskはUTF-8, -16, -32を自動で判別します。

Request.get_json() no longer accepts arbitrary encodings. Incoming JSON should be encoded using UTF-8 per RFC 8259, but Flask will autodetect UTF-8, -16, or -32. (#2691)

ブラウザが無視してしまうような巨大なクッキーについてWerkzeugが警告したときのため、それらをコントロールするためMAX_COOKIE_SIZEResponse.max_cookie_sizeを追加しました。

Added MAX_COOKIE_SIZE and Response.max_cookie_size to control when Werkzeug warns about large cookies that browsers may ignore. (#2693)

小さいウィンドウでも見やすいよう、ドキュメンテーションのテーマを更新しました。

Updated documentation theme to make docs look better in small windows. (#2709)

新しいユーザを落とし穴から守るため、チュートリアルと例として挙げるプロジェクトをより構造化されたアプローチに変更しました。

Rewrote the tutorial docs and example project to take a more structured approach to help new users avoid common pitfalls. (#2676)

国会でも話に上がった "HASH" をPythonで -- hash()じゃないよ! --

以前、”国会にhash関数の話が出たwww”といって、そっちの界隈の人でちょっとした話題になっていました。

では、hashとはなんなのか?分からない人もいると思います。

それがわかっても、Pythonでの実装がわからない方もいらっしゃると思いますので、この記事を書いた次第です。

hashって?

wikipediaを参照すると

データから算出した小さな値。各データを区別・表現する目的に用いる。

となっています。

つまり、あるデータから、それ固有の値を取り出して(計算から導き出す)、データの区別に使うための値。です

この計算というのが大事で、たとえば、長さが400ページ以上もある本を文字に落とし込んで所得したhashと、

その文字列の句点と読点を一個だけ入れ替えた文字列のhashは異なります

そこから、文書の改ざん対策などにも用いられるんですね。

また、その『元からhashを求めるのは用意である』が『hashから元を求めるのは非常に困難である』という性質を利用して、暗号・セキュリティにも用いられています。

Pythonで実装

Pythonにはhash関数が元からありますので、それを利用してみましょう。

>>> hash("1")  # "ハッシュ不可能"(listやset, dictなど)は用いないでください
4940519975841726253

求められましたね。

しかし、これではだめです

このhashが信頼できるのは、このインタープリタを閉じるまでだからです。

一度閉じて、もう一度実行してみましょう。

>>> hash("1")
2261270426266027010

おなじ文字列のhashを取り出したにもかかわらず、違う値が出ていますよね。

このように、正当性を確かめるには、標準のhashは不向きであるとわかります。

そこで使うのが、hashlibです

>>> import hashlib
>>> hashlib.md5(b"1").digest()  # bytesにしましょう
b'\xc4\xcaB8\xa0\xb9#\x82\r\xccP\x9aou\x84\x9b'
  # 一度閉じます
>>> import hashlib
>>> hashlib.md5(b"1").digest()
b'\xc4\xcaB8\xa0\xb9#\x82\r\xccP\x9aou\x84\x9b'  # 同じ値が返ってきます

みなさんが同じコードを打っても、同じ値が返ってくるはずです。

これが、一意性を保っているということです。

MD5(hash化の方法の種類です)のほかに、SHA1、SHA224、SHA256、SHA384、SHA512が対応しているようです。

ユーザーのパスワードをhash化して持っておき、ログインしようとしたときに、そのhashと入力された文字列のhashを比べる、なんてこともできますよね。
MD5に関しては、衝突(別のデータが同じhash値を持つ)ことが他のものと比べて多いようなので、注意です


しかし、まだまだパスワードは軟弱で、Brute-Force-Attack(総当たり攻撃)に対抗するだけの力がありません。

なので、Salt(パスワードと関係のない値)と反復を繰り返すのがhashlib.pbkdf2_hmac()です。

より高度な使用

>>> import os, hashlib, binascii
>>> salt = os.urandom(64)  # osの提供する64文字長の信頼できるrandomなbytes
>>> salt
b'\xc0<U\xdc5\xea\x8d+y\xe6W\x882U\xdaG\xbe\xd5\x19\xc0\xb2l\xf5\xd5/~W2\xa9\x92z\x8b\xff\xba\x8bs\x95t)I\xd1s\xfa.\x85R\xff\xd6\x89\x10n\xb7\xc3<\x84\x87\xea\xe6X\x8a\xdb,\xc3\x1c'
>>> dk= hashlib.pbkdf2_hmac("sha256", b"PaSsWoRd", salt, 100000)  # sha256でb"PaSsWoRd"とsaltを使って100000回hmacの反復
>>> binascii.hexlify(dk)  # 得られたhash
b'53ce88a1559e955b7b68794225365af09261f0a411629cef554de208e33e8da7'

といった感じです。

最低反復は 10,000回以上回すことが推奨されています。

それでは皆さん、よいPythonLifeを!!

AtCoder に登録したら解くべき精選過去問 10 問 をPythonで解いてみた

全く違うサイトにはなりますが、 drken 氏がQiitaで投稿された
AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ - Qiita

Pythonで解いてみました。

ある程度難しい問題があるので、説明を端折ることもあると思いますが、できるだけわかりやすく説明します。

0問目 PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

A: はじめてのあっとこーだー(Welcome to AtCoder) - Language Test | AtCoder

問題文
高橋君はデータの加工が行いたいです。
整数 a,b,cと、文字列 s が与えられます。
整数 a+b+c と、文字列 s を並べて表示しなさい。

入力
入力は以下の形式で与えられる。

a
b c
s
1 行目は、整数 a (1≦a≦1,000) が与えられる。
2 行目は、整数 b,c (1≦b,c≦1,000) が与えられる。
3 行目は、文字列 s が与えられる。この文字列の長さは 1 文字以上 100 文字以下である。
出力
a+b+c と s を空白区切りで 1 行に出力せよ。

また、出力の末尾には改行を入れること。

要は、与えられる文字列と数字を出力しろということですね。

a = int(input())
b, c = map(int, input().split())
print(a+b+c, input())

1問目 ABC086A - Product

A: Product - AtCoder Beginner Contest 086 | AtCoder

問題文
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

制約
1 ≤ a,b ≤ 10000
a,b は整数
入力
入力は以下の形式で標準入力から与えられる。

a b
出力
積が奇数なら Odd と、 偶数なら Even と出力せよ。

非常に簡単な問題ですね

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")

かけ合わせたものを純粋に割った方が早いです

2問目 ABC081A - Placing Marbles

A: Placing Marbles - AtCoder Beginner Contest 081 | AtCoder

問題文
すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス i には si が書かれています。

すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約
s1,s2,s3 は 1 あるいは 0
入力
入力は以下の形式で標準入力から与えられる。

s1s2s3
出力
答えを出力せよ。

つまり、1の個数を数えればいいわけですね。

print(input().count("1"))

与えられるのは文字列ですので、そのままcountでよいと思います

3問目 ABC081B - Shift only

B: Shift only - AtCoder Beginner Contest 081 | AtCoder

問題文
黒板に N 個の正の整数 A1,…,AN が書かれています.

すぬけ君は,黒板に書かれている整数がすべて偶数であるとき,次の操作を行うことができます.

黒板に書かれている整数すべてを,2 で割ったものに置き換える.
すぬけ君は最大で何回操作を行うことができるかを求めてください.

制約
1≤N≤200
1≤Ai≤109
入力
入力は以下の形式で標準入力から与えられる。

N
A1 A2 ... AN
出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ.

つまり、与えられた数字を一気に2で割るとしたとき、何回まで整数のままで割れますか。ということです。

import math
n = input()
a = list(map(int, input().split()))
ans = float("inf")
for i in a:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)
print(round(ans))

binに変換すると、右に続く0の数が、何回2で割れるか、というものになっています。ですから、わざわざrfindとかを使います。
なんかいもfor分を回すのはめんどくさいですからね。
Pythonは面白い言語で、"無限"を表現しようとすると、float("inf") としなければいけません。

4問目 ABC087B - Coins

B: Coins - AtCoder Beginner Contest 087 | AtCoder

問題文
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
0≤A,B,C≤50
A+B+C≥1
50≤X≤20,000
A,B,C は整数である
X は 50 の倍数である
入力
入力は以下の形式で標準入力から与えられる。

A
B
C
X
出力
硬貨を選ぶ方法の個数を出力せよ。

制約が大きいとforの回し方を工夫する必要がありますが、今回は小さいので、普通に回しましょう。

a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)

rangeの引数には+1を忘れないで入れておきましょう。

5問目 ABC083B - Some Sums

B: Some Sums - AtCoder Beginner Contest 083 | AtCoder

問題文
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

制約
1≤N≤104
1≤A≤B≤36
入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。

N A B
出力
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

文字列変換→リストでsumとすればよいでしょう。制約も小さいので。

n, a, b = map(int, input().split())
ans = 0
for i in range(n+1):
    if a <= sum(list(map(int, list(str(i))))) <= b:
        ans += i
print(ans)

美しいですね。

6問目 ABC088B - Card Game for Two

B: Card Game for Two - AtCoder Beginner Contest 088 | AtCoder

問題文
N 枚のカードがあります. i 枚目のカードには, ai という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約
N は 1 以上 100 以下の整数
ai (1≤i≤N) は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.

N
a1 a2 a3 … aN
出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

パット見ても、sliceを使いそうですよね。

n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

これでよいと思います。sliceでは2つ区切りで取り出して、sumを求めるということをしています。rangeも同じような使い方ができますよね。

7問目 ABC085B - Kagami Mochi

B: Kagami Mochi - AtCoder Beginner Contest 085 | AtCoder

問題文
X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい(一番下の餅を除く)もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。

ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は di センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約
1≤N≤100
1≤di≤100
入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。

N
d1
:
dN
出力
作ることのできる鏡餅の最大の段数を出力せよ。

何やら難しそうなことを言ってますが、要は、ユニークな要素はいくつありますか。ということです。ですので、setがうまく使えそうですね。

n = int(input())
print(len(set(map(int, [input() for i in range(n)]))))

非常に簡単ですね。

8問目 ABC085C - Otoshidama

C: Otoshidama - AtCoder Beginner Contest 085 | AtCoder

問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
1≤N≤2000
1000≤Y≤2×107
N は整数である。
Y は 1000 の倍数である。
入力
入力は以下の形式で標準入力から与えられる。

N Y
出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。

N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。


これに関しては、よーくfor文の条件を考えないとTLE(時間オーバー)してしまいます

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")

はい。じつは、for文二回でいけるんですね。それも当然で、2種類の枚数が定まれば、自然ともう一種類も定まるからですね。
競プロは、時間がきちきちになることはありますが、必ず解けます
あと、exit()を忘れないように…(僕は一回忘れました)

9問目 ABC049C - 白昼夢 / Daydream

C: 白昼夢 / Daydream - AtCoder Beginner Contest 049 | AtCoder

問題文
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

T の末尾に dream dreamer erase eraser のいずれかを追加する。
制約
1≦|S|≦105
S は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。

S
出力
S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

つまり、与えられる文字列は、すべて、["eraser", "erase", "dream", "dreamer"]でなっていますか。という問題です。

s=input().replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
if s:
    print("NO")
else:
    print("YES")

考えてみると分かるのですが、dreamerは、後ろのerを削っても大丈夫です。ですが、eraseとeraserが削られると致命的ですよね。

ですから、先にeraseとeraserを消しておいて、あとからdream, dreamerを消します。
残った文字列が空ならばOKです。でなければ、何か混ざっています。

10問目 ABC086C - Traveling

C: Traveling - AtCoder Beginner Contest 086 | AtCoder

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi,yi) を訪れる予定です。

AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約
1 ≤ N ≤ 105
0 ≤ xi ≤ 105
0 ≤ yi ≤ 105
1 ≤ ti ≤ 105
ti < ti+1 (1 ≤ i ≤ N−1)
入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。

N
t1 x1 y1
t2 x2 y2
:
tN xN yN
出力
旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

これも考えてみると実に簡単です。

n = int(input())
for i in range(n):
    t, x, y = map(int, input().split())
    if x + y < t or (x + y + t) % 2:
        print("No")
        exit()
print("Yes")

それぞれの t, x, y について
x + y が t より大きければダメ。
x + y と t の偶奇が違っていればダメ
この二つのコードを書けば終わりです。

終わりに

未だPythonは日本ではあまり主流とまではいっていません。それが競技プログラミングともなれば、ほとんどがC++などといった高速な言語ばかりです。
我々Pythonistaは、それによる速度の遅さのせいでしばしばPythonistaにしかわからない苦悩を味わうときさえあります。
しかし、少なくとも私はPythonに対する愛で乗り越えてきましたし、これからもそうでしょう。
特にfunctools, itertools, bisect, 等といった標準ライブラリには感服せざるを得ません。
豊富なライブラリに幾度となく助けられてきました。それは競技プログラミングでも同じです。
あなたも、この素晴らしい言語に対する愛が深まるように応援しています。

いい話

Pythonパーカーを作っています。ちなみに、私のデザインですが、一切私に利益は来ないようにするので、お安いです。
買いたいという人が多ければ多いほど安くなるので、DMなりコメントなりリプライなりよろしくお願いします。

Pythonでenumerateを賢く使う。

enumerateって?

英語で『数え上げる』という意味です。この関数の引数にイテレータを与えると、何回そのイテレータを呼び出したかを数える数と、そのイテレータ自身を返します。
例えば

for i, j in enumerate(range(5, 0, -1)):
    print(i, j)
"""
0 5
1 4
2 3
3 2
4 1
"""

rangeの特異な使い方については、こちらをご覧ください
delta114514.hatenablog.jp


となります。 i には 呼び出し回数が、j にはイテレータ(今回は、特にジェネレータです)の値が入っています。

ちなみに、enumerateは引数を二つ取ります。二つ目は、1番初めの番号を決めます。

for i, j in enumerate(range(5, 0, -1), start=5):
    print(i, j)
"""
5 5
6 4
7 3
8 2
9 1
"""

これを使うと、AtCoderのこのC問題なら2行で解くことができます。
C - 背の順

問題文

高橋学級には N 人の生徒がいます。 生徒は 1 から N まで出席番号が振られています。 i 番目の生徒の身長は a_i です。 a_i はすべて相異なります。
高橋先生は N 人の生徒を背の高い方から順に並べました。 N 人の生徒の出席番号を背の高い方から順に出力してください。

制約

2≦N≦10^5
ai は整数である。
1≦a_i≦10^9
a_i はすべて相異なる。

部分点

30 点分のテストケースでは、N≦1000 を満たす。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 … a_N

出力

N 行出力せよ。 i 行目には、i 番目に背の高い生徒の出席番号を出力せよ。

はい。
愚直にやると

n = int(input())
individuals = list(map(int, input().split()))
for i in range(n):
    tallest = max(individuals)
    number = individuals.index(tallest)  # tallestを直に入れても良いです
    print(number + 1)
    individuals[number] = 0

背の高い人を毎回割り出して、その番号を返し、身長をブラックホール圧縮することでカウントしないようにしています。


ですが、こちら、TLEしてしまいました。


悲しいなぁ…

ですが、このenumerateを使う方法ならTLEせずに解けます。

n=int(input())
for i in sorted(enumerate(list(map(int, input().split())), start=1), key = lambda x :x[1], reverse = True):
    print(i[0])

lambdaについては 
delta114514.hatenablog.jp
をご覧ください
わかりやすくすると

def getsecond(n):  # lambdaの明示化
    return n[1]
 
n = int(input())
individuals = list(map(int, input().split()))  # 入力
enumerated_individuals = list(enumerate(individuals, start=1))  # enumerateされたlistを作る
enumerated_individuals.sort(key=getsecond, reverse=True)  # 身長でsortする
for i in enumerated_individuals:
    print(i[0])

です。つまり、身長と、入力された順番で対応したlistを作り、身長でsort(番号はくっついたまま)することにより、上から取り出すことで、番号のみを取り出すことができます。

各実行ごとでは

def getsecond(n):  # lambdaの明示化
    return n[1]
 
n = int(input())
individuals = list(map(int, input().split()))  # 入力
# individuals == [[160, 120, 150, 170]]

enumerated_individuals = list(enumerate(individuals, start=1))  # enumerateされたlistを作る
#enumerated_individuals == [(1, 160), (2, 120), (3, 150), (4, 170)]

enumerated_individuals.sort(key=getsecond, reverse=True)  # 身長でsortする
#enumerated_individuals == [(4, 170), (1, 160), (3, 150), (2, 120)]

for i in enumerated_individuals:
    print(i[0])

となります。

いいでしょ~、enumerate!!

それではみなさん、よいPythonLifeを!

宣伝…

Pythonの無名関数=(lambda)について

lambda

分かりにくいですよね笑

私も理解するために少し時間がかかりました。

簡単に言うと

””
def せずに関数を定義する
””

ものです。

もし、あるイテレータ・構造の二番目を取り出す関数を作るには

def getsecond(n):
    return n[1]

とできますが、もっと短く

getsecond = lambda x: x[1]
getsecond([1, 2])
  # 2

とできます。

lambda の文法について

lambda の文法は
"""
lambda 引数: 返り値
"""

となっています。なので、

先ほどのlambdaでいうと

x を引数としたときに、x[1]を返り値にする。

ということです。

なので、keyを引数に取るようなsortで、絶対値を基準にソートしたいとき

a = [1, 3, 5, 7, -2, -4, -6]
print(sorted(a))
  # [-6, -4, -2, 1, 3, 5, 7]
print(sorted(a, key=lambda x: abs(x)))
  # [1, -2, 3, -4, 5, -6, 7]

とできます。

どうですか?分かりやすかったですか?
質問があれば気軽にどうぞ!

宣伝…

ただの回数繰り返しだけじゃない! range()の賢い使用法

rangeって?

英語で範囲 を現します。Pythonでは、第一引数から第二引数まで、第三引数区切りで値を作ります。


え?引数を3つも取れるの?


そう思った方のための記事となりますので、すでに知っていた方はブラウザバックしていただいても大丈夫です…。

引数について

公式のリファレンスでは

class range(start, stop[, step])
range コンストラクタの引数は整数 (組み込みの int または __index__ 特殊メソッドを実装するオブジェクト) でなければなりません。step 引数が省略された場合のデフォルト値は 1 です。start 引数が省略された場合のデフォルト値は 0 です。 step が 0 の場合、ValueError が送出されます。

step が正の場合、range r の内容は式 r[i] = start + step*i で決定されます。ここで、 i >= 0 かつ r[i] < stop です。

step が負の場合も、range r の内容は式 r[i] = start + step*i で決定されます。ただし、制約条件は i >= 0 かつ r[i] > stop です。

r[0] が値の制約を満たさない場合、range オブジェクトは空になります。range は負のインデックスをサポートしますが、これらは正のインデックスにより決定されるシーケンスの末尾からのインデックス指定として解釈されます。

となっています。

簡単に言うと、
『全ての引数は整数で、step=0だけはやめてね』
ということです。

つまり、日ごろ皆さんが使っている
range(n)

range(0, n, 1)
同義です

トリッキー(?)な使い方

もしstep < -1 且つ stop < start の時、返すイテレータは、徐々に数が小さくなっていきます。

ただ、上記のどちらかのみが成り立つとき、イテレータは何も返しません。

以下対話型シェルでの実行です。

>>> list(range(0, 5, 1))
[0, 1, 2, 3, 4]
>>> list(range(5, 0, -1))  # 負のstepになっても、stopの値は含まないことに注意してください
[5, 4, 3, 2, 1]
>>> list(range(5, 0, 1)) == list(range(0, 5, -1))  # 両方とも空のリストを返します。
True
>>> list(range(5, 0, 1))
[]
>>> list(range(100, -1, -2))
[100, 98, 96, 94, 92, 90, 88, 86, 84, 82, 80, 78, 76, 74, 72, 70, 68, 66, 64, 62, 60, 58, 56, 54, 52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0]
  # このようにすることで、1行で”100から0まで、偶数を降順でリストアップする”が実装できます

いかがでしょうか?使いやすいでしょう?

それでは、みなさん!頑張ってくださいね!

宣伝…

数え上げに使えるcollections の Counter のお話

"collections" ライブラリの "Counter"。文字通り、数えるためにあります。

『数え上げ?普通にfor文回せばいいじゃんアゼルバイジャン

という方もいらっしゃるでしょう。

お前それ競プロの前でも言えんの?

))

では、for + リストでの数え上げがどの程度の愚行なのか実験していきましょう。

for + リストでの数え上げ

import time  # @1
summ = 0
for j in range(1, 11):  #@2
    start = time.time()
    for i in range(int(1e4)):  #@3
        count = [0 for m in range(200)]
        for i in """
        Beautiful is better than ugly.
        Explicit is better than implicit.
        Simple is better than complex.
        Complex is better than complicated.
        Flat is better than nested.
        Sparse is better than dense.
        Readability counts.
        Special cases aren't special enough to break the rules.
        Although practicality beats purity.
        Errors should never pass silently.
        Unless explicitly silenced.
        In the face of ambiguity, refuse the temptation to guess.
        There should be one-- and preferably only one --obvious way to do it.
        Although that way may not be obvious at first unless you're Dutch.
        Now is better than never.
        Although never is often better than *right* now.
        If the implementation is hard to explain, it's a bad idea.
        If the implementation is easy to explain, it may be a good idea.
        Namespaces are one honking great idea -- let's do more of those!
        """:  #@4
            count[ord(i)] += 1  #@5
    end = time.time()
    print("{}: {}  (sec)".format(j, end - start))  #@6
    summ += end - start
for i in range(len(count)):
    if count[i]:
        print("{!r}: {}, ".format(chr(i), count[i]), end="")  #@7
print("")
print("average: {}  (sec)".format(summ / 10))  #@8
  • @1: 時間を計りたいので、timeをimportします
  • @2 10回回して、平均を出そうと思います
  • @3 10000回計算します
  • @4 Pythonインタープリタで >>>import this と入力してみてください。同じものが出ます。これは、Pythonのエッセンスです
  • @5 それぞれの番号を決めるのは面倒なので、文字ごとの文字番号をインデックスにしています
  • @6 10000回計算するごとに、その回の計算時間を出力します
  • @7 改行を改行として出力してしまうので、{!r}を使うことにより、エスケープシーケンスをつけて出力できます
  • @8 10回の平均を出します

出力がこちらになります

1: 1.5162262916564941  (sec)
2: 1.5041000843048096  (sec)
3: 1.5104267597198486  (sec)
4: 1.574958086013794  (sec)
5: 1.4988515377044678  (sec)
6: 1.488734483718872  (sec)
7: 1.499678611755371  (sec)
8: 1.5089690685272217  (sec)
9: 1.5006461143493652  (sec)
10: 1.4950613975524902  (sec)
'\n': 20, ' ': 278, '!': 1, "'": 4, '*': 2, ',': 3, '-': 6, '.': 18, 'A': 3, 'B': 1, 'C': 1, 'D': 1, 'E': 2, 'F': 1, 'I': 3, 'N': 2, 'R': 1, 'S': 3, 'T': 1, 'U': 1, 'a': 50, 'b': 19, 'c': 16, 'd': 16, 'e': 86, 'f': 10, 'g': 11, 'h': 29, 'i': 49, 'k': 2, 'l': 33, 'm': 15, 'n': 38, 'o': 41, 'p': 20, 'r': 31, 's': 42, 't': 74, 'u': 20, 'v': 5, 'w': 4, 'x': 6, 'y': 15, 
average: 1.5097652435302735  (sec)

1.5秒ですか~…。

う~ん、遅い!w

つぎに、ディクショナリを使ってみましょう。

defaultdict をつかう数え上げ

defaultdictを使えば、存在しない要素(key)を指定したときに、勝手に初期化してくれます。

import time
import collections
summ = 0
for j in range(1, 11):
    start = time.time()
    for i in range(int(1e4)):
        count = collections.defaultdict(int)
        for i in """
        Beautiful is better than ugly.
        Explicit is better than implicit.
        Simple is better than complex.
        Complex is better than complicated.
        Flat is better than nested.
        Sparse is better than dense.
        Readability counts.
        Special cases aren't special enough to break the rules.
        Although practicality beats purity.
        Errors should never pass silently.
        Unless explicitly silenced.
        In the face of ambiguity, refuse the temptation to guess.
        There should be one-- and preferably only one --obvious way to do it.
        Although that way may not be obvious at first unless you're Dutch.
        Now is better than never.
        Although never is often better than *right* now.
        If the implementation is hard to explain, it's a bad idea.
        If the implementation is easy to explain, it may be a good idea.
        Namespaces are one honking great idea -- let's do more of those!
        """:
            count[i] += 1
    end = time.time()
    print("{}: {}  (sec)".format(j, end - start))
    summ += end - start
print(count)
print("average: {}  (sec)".format(summ / 10))

こちらの出力はこうなります

1: 1.0501744747161865  (sec)
2: 1.0498456954956055  (sec)
3: 1.0457956790924072  (sec)
4: 1.050318956375122  (sec)
5: 1.0362188816070557  (sec)
6: 1.044149398803711  (sec)
7: 1.0807437896728516  (sec)
8: 1.0319969654083252  (sec)
9: 1.0468177795410156  (sec)
10: 1.0291187763214111  (sec)
defaultdict(<class 'int'>, {'\n': 20, ' ': 278, 'B': 1, 'e': 86, 'a': 50, 'u': 20, 't': 74, 'i': 49, 'f': 10, 'l': 33, 's': 42, 'b': 19, 'r': 31, 'h': 29, 'n': 38, 'g': 11, 'y': 15, '.': 18, 'E': 2, 'x': 6, 'p': 20, 'c': 16, 'm': 15, 'S': 3, 'o': 41, 'C': 1, 'd': 16, 'F': 1, 'R': 1, "'": 4, 'k': 2, 'A': 3, 'v': 5, 'U': 1, 'I': 3, ',': 3, 'T': 1, '-': 6, 'w': 4, 'D': 1, 'N': 2, '*': 2, '!': 1})
average: 1.046518039703369  (sec)

1秒ですか…そこそこですね…
まだまだいけそうですね()

では、大本命、Counterを使ってみましょう

Counter での数え上げ

import time
from collections import Counter
summ = 0
for j in range(1, 11):
    start = time.time()
    for i in range(int(1e4)):
        count = Counter("""
        Beautiful is better than ugly.
        Explicit is better than implicit.
        Simple is better than complex.
        Complex is better than complicated.
        Flat is better than nested.
        Sparse is better than dense.
        Readability counts.
        Special cases aren't special enough to break the rules.
        Although practicality beats purity.
        Errors should never pass silently.
        Unless explicitly silenced.
        In the face of ambiguity, refuse the temptation to guess.
        There should be one-- and preferably only one --obvious way to do it.
        Although that way may not be obvious at first unless you're Dutch.
        Now is better than never.
        Although never is often better than *right* now.
        If the implementation is hard to explain, it's a bad idea.
        If the implementation is easy to explain, it may be a good idea.
        Namespaces are one honking great idea -- let's do more of those!
        """)
    end = time.time()
    print("{}: {}  (sec)".format(j, end - start))
    summ += end - start
print(count)
print("average: {}  (sec)".format(summ / 10))

そして気になる実行時間ですが

1: 0.4078483581542969  (sec)
2: 0.41309595108032227  (sec)
3: 0.4018237590789795  (sec)
4: 0.40430498123168945  (sec)
5: 0.4073166847229004  (sec)
6: 0.424285888671875  (sec)
7: 0.4343554973602295  (sec)
8: 0.42177391052246094  (sec)
9: 0.43581199645996094  (sec)
10: 0.4025719165802002  (sec)
Counter({' ': 278, 'e': 86, 't': 74, 'a': 50, 'i': 49, 's': 42, 'o': 41, 'n': 38, 'l': 33, 'r': 31, 'h': 29, '\n': 20, 'u': 20, 'p': 20, 'b': 19, '.': 18, 'c': 16, 'd': 16, 'y': 15, 'm': 15, 'g': 11, 'f': 10, 'x': 6, '-': 6, 'v': 5, "'": 4, 'w': 4, 'S': 3, 'A': 3, 'I': 3, ',': 3, 'E': 2, 'k': 2, 'N': 2, '*': 2, 'B': 1, 'C': 1, 'F': 1, 'R': 1, 'U': 1, 'T': 1, 'D': 1, '!': 1})
average: 0.4153188943862915  (sec)

Yeah!! Pythonic!!

0.4秒ですって。

リストに比べて約1/4程になりましたね…

このように、非常に高速な演算が可能です。

ちなみに、Counterはdict型を返します。

Counterの便利な使い方

Counterには多くの便利な機能があります。

Counter.elements()

それぞれのkeyを、value個入れたリストを返してくれます。

from collections import Counter
let = Counter("abraham lincoln said\"abracadabra\"")
print(let)
print("".join(sorted(let.elements())))

とすれば、

Counter({'a': 9, 'b': 3, 'r': 3, ' ': 2, 'l': 2, 'i': 2, 'n': 2, 'c': 2, 'd': 2, '"': 2, 'h': 1, 'm': 1, 'o': 1, 's': 1})
  ""aaaaaaaaabbbccddhiillmnnorrrs

となります。

Counter.most_common()

出現回数の多い(valueの多い)ものを、上から引数個分だけ取り出してくれます。引数が無ければ、全て取り出してくれます。

sorted(list(let.items()), key=lambda x: x[1], reverse = True)[:引数]

と同じですね。

from collections import Counter
let = Counter("abraham lincoln said\"abracadabra\"")
print(let.most_common(3))

とすれば

[('a', 9), ('b', 3), ('r', 3)]

が返ってきます。

Counter.substract(another Counter)

Counterから、another Counterの値を引きます。破壊的な関数です。

from collections import Counter
leta = Counter("abraham lincoln said\"abracadabra\"")
letb = Counter("baby array and bad bully")
leta.subtract(letb)
print(leta)

答えがマイナスなどになることも十二分にあり得ます。

Counter({'a': 4, 'i': 2, 'c': 2, '"': 2, 'r': 1, 'h': 1, 'm': 1, 'n': 1, 'o': 1, 's': 1, 'l': 0, 'd': 0, 'b': -1, 'u': -1, ' ': -2, 'y': -3})

どうでしょうか?

非常に使いやすいと思います。

Pythonボトルネックは速度なので、それさえ乗り越えられれば愛せるようになりますよ。すでに愛している方は、さらに愛せるように…

いいお話

あ、そうだ(唐突)

Pythonパーカーを作ろうと思っています。興味の湧いた方はどうぞご一報ください。

かう人が多ければ多いほど安くできるので、募集中です(宣伝)

ちなみに、私に利益な一切来ないようにします…(純粋な愛ゆえのパーカーなので、それで金儲けしようとは考えていません。)
なので、思われているより安いと思いますよ笑

では皆さん、よいPythonライフを!!