競プロ典型90問 ★2問題コード解説[4]
はじめに
もう冬も本番になってきましたね。
買い物に行くと、店内BGMがクリスマスソングだったり、長靴に入ったお菓子が売られていたりと、年末を実感しますね。
本日も競プロ典型90問から★2問題を2問、解説していきたいと思います！
競プロ典型90問
055 - Select 5（★2）
直感的な解法としては、N個の整数から5つ数字を選んで、それがPで割れるかどうかを判定する、というのを5つ選ぶ組合せの数だけ行う、ということが考えられます。
しかし、競プロ的な考え方だと、５重ループは計算量が多すぎてTLEになってしまうのではないか、と考えるのが自然です。
しかし、実は５重ループでも、今回は5<=N<=100という制約があったり、ループ内の処理が簡単だということで、制限時間内に実行することが出来ます。
Pythonでは、itertoolsライブラリのcombinationsを用いて組み合わせを出力することが出来ます。組合せの計算はnC5 = 1/120 * N^5となり、５重ループと同等の計算量となります。
実は、このコード、言語をPythonとして実行すると、TLEになってしまいます。ですので、提出の際は、言語をPyPy3（現行では7.3.0）に設定して実行してください。
PyPy3は、ざっくりいうと通常のPythonより高速に動作する（ことが多い）処理系です。再帰が含まれるようなコード以外はPyPy3で実行するのが良いかもしれません。（PyPy３に関しては勉強中です…詳しいことはよくわかっていません…）
以下がコードになります。
from itertools import combinations N, P, Q = map(int,input().split()) A = list(map(int,input().split())) ans = 0 for a, b, c, d, e in combinations(A, 5): if a % P * b % P * c % P * d % P * e % P == Q: ans += 1 print(ans)
061 - Deck（★2）
tの値に応じて、カードを上に入れるか下に入れるか、という問題です。
リストの初めをデッキの上、後ろをデッキの下という風に考えていきたいのですが、リストの頭に要素を挿入するのは意外と難しいです。
そこでPythonにはdepueという便利なモジュールがあります。
deque型はリスト型のappend()で後ろに追加するのと同様に、前に要素を追加することが出来ます。これによって、tの値に応じてカードを上に入れるか下に入れるかを簡単に実装することが出来ます。
以下、コードです。
from collections import deque q = int(input()) d = deque() for i in range(q): t, x = map(int, input().split(" ")) if t == 1: d.appendleft(x) elif t == 2: d.append(x) else: print(d[x-1])
おわりに
ここまでご覧いただき、ありがとうございました。競プロ典型90問の★2問題は次回で最後となります。以降は★3問題の解説やブックレビューをしていこうかなと考えています。
