Pythonで競技プログラミングハンズオン

PyLadies Tokyo Meetup #16の資料

Transcript

1. Python で競技プログラミング ハンズオン 真嘉比 愛 (@a_macbee) 2016-11-27@VOYAGE GROUP PyLadies Tokyo Meetup #16 1
2. [ 大前提] 本日の想定環境 Python 3.* 私の環境はPython 3.5.2 2
3. 本日やること 競技プログラミングにチャレンジします！ 競技プログラミングでは、 参加者全員に同一の 課題が出題され、 より早く、 与えられた要求を 満足するプログラムを正確に記述することを競 う。 by Wikipedia 到達したいゴー ル 参加にあたり知っていると便利なTips を理解 一連の流れを理解して， ひとりでもコンテスト に参加出来るようになる 3
4. 競技プログラミングの基本的な形式 大体以下のような形式だと考えて良い 問題文： ほげほげするプログラムを作成しなさい 入力： 1 1 出力： hoge 制約： プログラムの実行時間：◦ 秒以内 メモリの使用量：◦ MB 以内 4
5. 今すぐ始めるために知っておくこと 以下の3 つについて紹介 1. 入力の受け取りかた 2. 出力のしかた 3. 制約を満たしているか否かの確かめかた 最悪これは知らなくても良い 5
6. 今すぐ始めるために知っておくこと 以下の3 つについて紹介 1. 入力の受け取りかた 2. 出力のしかた 3. 制約を満たしているか否かの確かめかた 最悪これは知らなくても良い 6
7. 1. 入力の受け取りかた input() を利用して簡単に受け取ることが出来る 入力として受け取りたい数値 1 # a 2.0 # b 3 4 5 # c Python 側での処理 a = int(input()) b = float(input()) c = [int(x) for x in input().split()] 7
8. [ 閑話] Python 2 で input() を使わない Python 2 の input() は入力された文字列をそのまま実 行（ eval() ） してしまうので非常に危険 --> raw_input() を代わりに利用する a = raw_input() # for Python 2.* Python 3 では raw_input() は廃止され， input() が raw_input() の動作をする． みんなPython 3 を使いま しょう 8
9. 今すぐ始めるために知っておくこと 以下の3 つについて紹介 1. 入力の受け取りかた 2. 出力のしかた 3. 制約を満たしているか否かの確かめかた 最悪これは知らなくても良い 9
10. 2. 出力のしかた print() 出力を使う # 入力 a = input() b = input() # 出力 c = 0 ... ... print(c) 10
11. [ 例題] 総和を求めるプログラム スペー ス区切りの数値を与えられたら， その総和を出 力する calculator.py を作成しなさい $ python calculator.py 1 2 3 4 5 15 11
12. [ 例題] 総和を求めるプログラム スペー ス区切りの数値を与えられたら， その総和を出 力する calculator.py を作成しなさい $ python calculator.py 1 2 3 4 5 15 ↓ # calculator.py dat = [int(x) for x in input().split()] print(sum(dat)) 12
13. 今すぐ始めるために知っておくこと 以下の3 つについて紹介 1. 入力の受け取りかた 2. 出力のしかた 3. 制約を満たしているか否かの確かめかた 最悪これは知らなくても良い 13
14. 3. 制約を満たしているかの否かの確 かめかた（1/7） 色々 な制約があるが， ここでは以下の2 つを紹介 プログラムの実行時間 e.g. 2 秒以内 メモリの使用量 e.g. 256MB 以内 14
15. 3. 制約を満たしているかの否かの確 かめかた（2/7） プログラムの実行時間の計測には， time モジュー ル の time.time() 関数を利用する 実行開始時間と終了時間の差分を見ている import time start = time.time() dat = [int(x) for x in input().split()] print(sum(dat)) print('{} [ms]'.format(1000 * (time.time() - start))) 15
16. 3. 制約を満たしているかの否かの確 かめかた（3/7） input.txt 1 2 3 4 5 実行結果 $ python calculator.py < input.txt 15 0.3211498260498047 [ms] ※ 連続で実行する場合は __pycache__ を削除すること 16
17. 3. 制約を満たしているかの否かの確か めかた（4/7） Unix 環境であれば time コマンドも便利 $ time python calculator.py < input.txt 15 python calculator.py < input.txt 0.10s user 0.08s system 87% cpu 0.201 total 17
18. 3. 制約を満たしているかの否かの確か めかた（5/7） メモリの使用量の計測には memory_profiler を使う memory_profiler は pip で簡単に導入できる $ pip install psutil memory_profiler メモリ使用量を計測したい関数に， @profile のデコ レー タをつけるだけでプロファイリングが行われる 18
19. 3. 制約を満たしているかの否かの確か めかた（6/7） python -m memory_profiler 分析したいPython ファイル という 形式で実行すると， プロファイリングが行われる $ python -m memory_profiler calculator.py < input.txt 15 Filename: calculator.py Line # Mem usage Increment Line Contents ================================================ 3 22.781 MiB 0.000 MiB @profile 4 def main(): 5 22.785 MiB 0.004 MiB print(sum([int(x) for x i 19
20. 3. 制約を満たしているかの否かの確か めかた（7/7） プログラムの実行時間 time.time() (time モジュー ル) Unix のtime コマンド メモリの使用量 @pro le (memory_pro ler モジュー ル) python -m memory_pro ler 20
21. やってみましょう！ 21
22. チャレンジするコンテスト yukicoder: http://yukicoder.me/ yukicoder は競技プログラミング・ アルゴリズム を練習する目的で運営されています。 競技プログラミングの模試・ 勉強会のような位置 づけを目指しております。 “ “ 22
23. No.5 数字のブロック Ellen は数字のブロックで遊ぼうとしている。 数字が書かれているブロックはそれぞれ高さ1 で幅は W である。 それらのブロックを高さ1, 幅L の大きな箱 の中に入れる。 Ellen は大きな箱にどれだけブロックがたくさん入る か気になったが。 組み合わせがたくさんあって大変な ことに気づいて、 すぐに夜になってしまいそうであ る。 あなたは、 代わりに大きな箱に最大何個のブロックが 入るかを求めてください。 制限：1 ケー ス 5.000 秒 / メモリ制限 512 MB i 23
24. 入力形式 L N W W W ... W 1 行目: 箱の幅 L（1≤L≤10000） 2 行目: ブロックの数 N (1≤N≤10000) 3 行目: 各ブロックの幅 W (1≤Wi≤L) が半角スペー ス区切りになっている 1 2 3 N i 24
25. 出力形式 求めた数値を返す（ 末尾に改行を付ける） 25
26. サンプル 入力 16 3 10 5 7 出力 2 26
27. どういうプログラムを書くか イメー ジ出来ますか？ 27
28. 回答サンプル # 入力を受け取る L = int(input()) _ = input() blocks = [int(block) for block in input().split()] # boxes を小さい順に並び替えて，L からひいていく # L がマイナスになったらそのときのidx を出力 answer = 0 for block in sorted(blocks): L = L - block if L >= 0: answer += 1 else: break print(answer) 28
29. 問題にチャレンジ！ 以下の問題にチャレンジしてみましょう 早く解き終わった方は別の問題にもチャレンジ！ No.46 はじめのn 歩 No.207 世界のなんとか No.56 消費税 No.47 ポケットを叩くとビスケットが２倍 問題ペー ジのURL: {number} の部分に問題No. を入れて下さい http://yukicoder.me/problems/no/{number} 29
30. [ 閑話] Python の速度問題 C++ 言語と比較して， プログラムの実行時間やメモ リ使用量が制限されてしまう 実行時間が1 秒の場合C++ なら10 ルー プでも耐 えられるが，Python だと10 ルー プでも厳しめ 要素あたりのメモリ使用量が多い 参考: http://qiita.com/lethe2211/items/38303f4120bfd96 3679a 7 6 30