Apple Pencil Pro
￥20,919 (2025年4月30日 13:13 GMT +09:00 時点 - 詳細はこちら価格および発送可能時期は表示された日付/時刻の時点のものであり、変更される場合があります。本商品の購入においては、購入の時点で当該の Amazon サイトに表示されている価格および発送可能時期の情報が適用されます。)
【Android15 タブレット 12インチ 2K IPS大画面】ODEA A12 2025、2000*1200解像度、8000mAh+USB-C、12GB+128GB+1TB TF拡張、A75 CPU T606 Antutu 240,000点+、アンドロイド15タブレット、2K IPS画面/GMS/5G WiFi/BT 5.0/Widevine L1 Netflix対応/GPS (12GB)
￥16,900 (2025年4月30日 13:06 GMT +09:00 時点 - 詳細はこちら価格および発送可能時期は表示された日付/時刻の時点のものであり、変更される場合があります。本商品の購入においては、購入の時点で当該の Amazon サイトに表示されている価格および発送可能時期の情報が適用されます。)
ABC403のE問題でTrie木を使う問題があったので、dataclassを使ってTrie木を表現してみました。
AtCoderの問題を解くときは、タプルで表現して、力づくで解く等になりがち何ですが、dataclassを使うと、可読性が上がるので、一度試してみました。
説明は省略します。
等が参考になると思います。
@dataclass
class TrieNode:
children: dict = field(default_factory=lambda: defaultdict(TrieNode))
is_x_terminal: bool = False
count_y: int = 0
ABC403 Eでは、文字列Xとして追加されたものかを判定するis_x_terminalと文字列Yの数をカウントするcount_yを持たせる必要があったので、この二つを持たせています。
この部分は課題に合わせて修正します。
例として、文字列Sを追加する処理を書いてみます
def add_string(trie: TrieNode, s: str) -> None:
node = trie
for c in s:
node = node.children[c]
node.is_x_terminal = True
trie_tree = TrieNode()
add_string(trie_tree, "abc")
add_string(trie_tree, "ab")
childrenの辞書は、子ノードがない場合には、TrieNodeで初期化する必要があります。
以下のコードのようにif文で記述する事になります。
def add_string(trie: TrieNode, s: str) -> None:
node = trie
for c in s:
if c not in node.children: # node.children[c] = TrieNode() # node = node.children[c]
node.is_x_terminal = True
これでも良いのですが、自動的に初期化するようにchildrenをdefaultdictを使って、初期化してあります。
子ノードがない場合でも、children[c]でアクセスするとその時点で、TrieNodeが作成されるので、if文でのチェックが不要です。
children: dict = field(default_factory=lambda: defaultdict(TrieNode))
この自動的に初期化するコードは、TrieNodeの定義の中で、TrieNodeを使う必要があって、どうやって書けばいいのか悩みましたが、lamba式を使うことで、解決しました。
lambda式は、実行した時に初めて内容が評価されるため、lambda式の中で、TrieNodeを使う記述で問題ありませんでした。
ABC403 E
from dataclasses import dataclass, field
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip("\r\n")
I = input
II = lambda: int(I())
LI = lambda: list(input().split())
LII = lambda: list(map(int, input().split()))
@dataclass
class TrieNode:
children: dict = field(default_factory=lambda: defaultdict(TrieNode))
is_x_terminal: bool = False
count_y: int = 0
trie_tree = TrieNode()
def add_x(S):
node = trie_tree
for s in S:
node = node.children[s]
if node.is_x_terminal:
# 既に追加済みの場合は処理不要
return 0
node.is_x_terminal = True
ret = node.count_y
add_count_y(S,-ret)
return ret
def add_y(S):
node = trie_tree
for s in S:
node = node.children[s]
if node.is_x_terminal:
# Prefixが一致するXが既にある場合追加しない
return 0
add_count_y(S, 1)
return 1
def add_count_y(S,val):
"""Trie木の根からSの間の全てのノードにcount_yにvalを足す"""
node = trie_tree
for s in S:
node = node.children[s]
node.count_y += val
Q =II()
ans = 0
for _ in range(Q):
t,s = LI()
if t == "1":
ans -= add_x(s)
else:
ans += add_y(s)
print(ans)
- Trie木をdataclassを使って表現してみました。
- Trie木の、Nodeにもたせる情報をdataclassを使うことで、わかりやすく記述できました。
- 実行速度については、未評価です。ABC403 Eの問題を解く限りでは、特に問題はありませんでした。
Views: 2
USB Type C ケーブル【2M/2本セット】Sweguard USB-C & USB-A 3.1A USB C ケーブル【QC3.0対応 急速充電】 タイプc 充電ケーブルiPhone16/iPhone 15 Pro MAX, iPad Pro,Samsung Galaxy S24/S23/S22/S21/S20,Sony,Xiaomi,Huawei,Pixel,Type-c機種対応(灰)
￥934 (2025年4月30日 13:13 GMT +09:00 時点 - 詳細はこちら価格および発送可能時期は表示された日付/時刻の時点のものであり、変更される場合があります。本商品の購入においては、購入の時点で当該の Amazon サイトに表示されている価格および発送可能時期の情報が適用されます。)
