競技プログラミングなんでもカレンダーを作り、
この記事で無事25記事目（完走賞🎉）
学んだこと等を振り返る。
目次
- 学んだこと
- 投稿した記事
- 総括
学んだこと
期間中の新しく覚えたテクニックは以下のもの
- メモ化再帰
- mod998244353の逆数
- sortedset
- 他の配列をkeyにしてソートする
メモ化再帰
再帰関数で何度も使う値を配列などで保存するテクニック。
defaultdict君が役に立つ
from collections import defaultdict
memo = defaultdict(lambda: None)
def factorial(n):
if n == 0:
return 1
if memo[n] is None:
memo[n] = n * factorial(n-1)
return memo[n]
print(factorial(5)) # 120
print(factorial(10)) # 3628800
Pythonではデコレーターもあるので便利
from functools import lru_cache
@lru_cache
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
print(factorial(5)) # 120
print(factorial(10)) # 3628800
mod998244353 の逆数
確率を mod で表現するときにこのようなテクニックが必要になる。
Pythonにはpow関数でmodを使えるのでそこで-1乗を求めるだけ
mod = 998244353
inv = lambda x: pow(x, -1, mod)
VSCodeにスニペットを登録すると便利
"Modular Inverse": {
"prefix": "::mod_inv",
"body": [
"mod = ${1|998244353,1000000007|}",
"inv = lambda x: pow(x, -1, mod)"
],
"description": "モジュラ逆数を計算する"
},
SortedSet
sortedcontainersのライブラリをインストールして使えるモジュール
setのように、同じ要素を1つだけいれることができるが、
内部は昇順に並んでいるため、先頭を取れば最小値、最後尾を取れば最大値を取得できる。
from sortedcontainers import SortedSet
# SortedSetの作成
sset = SortedSet([5, 1, 3, 2, 4])
# 要素の追加
sset.add(6)
print(sset) # 出力: SortedSet([1, 2, 3, 4, 5, 6])
# 要素の削除
sset.remove(3)
print(sset) # 出力: SortedSet([1, 2, 4, 5, 6])
# 要素の存在確認
print(4 in sset) # 出力: True
print(3 in sset) # 出力: False
# 最小値と最大値の取得
print(sset[0]) # 出力: 1
print(sset[-1]) # 出力: 6
他の配列をkeyにしてソートする
同じ大きさのリストA,Bに対してAの昇順でBをソートすることもできるよねって話。
考えれば特になんでもないテクニックだが、個人的には全く思いつかなかったのでメモ。
A = [3, 1, 2]
B = ['a', 'b', 'c']
# Aの順序でBをソート
sorted_B = [x for _, x in sorted(zip(A, B))]
print(sorted_B) # 出力: ['b', 'c', 'a']
投稿した記事
種類ごとにカウント
- E問題を解いた記事: 12記事
- D問題を解いた記事: 5記事
- F問題を解いた記事: 2記事
- ABC振り返り記事: 4記事
- その他: 2記事
アドベントカレンダー開始前に
E問題を多く解くことを目標としていたが、12問と
投稿した記事の割合としては半分ぐらいの結果となった。
とりあえず目標としては達成(?)
期間内のABC振り返り
アドベントカレンダー期間と直前に開催されたABCの結果を軽く振り返る
4完できた回がなく、それどころか最近は2完という体たらく
特に直近2回はちょっとした誤字でWA喰らっているので気をつけたい
総括
当初の予定通りE問題を多く解くことができたが、
ABCの結果が振るわないのでそこは残念だったところ。
まだまだ精進が必要だと思った