2022-09-21 PAST #10 E, F, G, H を解いた / twiq 実装メモ
PAST #10 : 第10回 アルゴリズム実技検定 過去問 の E, F, G, H を解いた。
- E - 良い日付
https://atcoder.jp/contests/past202203-open/tasks/past202203_e
- 提出: https://atcoder.jp/contests/past202203-open/submissions/35029967
- 件数が少ないので前から順に日付を増やして調べていけば良い
- Rust の場合は標準ライブラリに日付を扱うものがないため実装が必要で面倒くさい
- F - 地図の塗り分け
https://atcoder.jp/contests/past202203-open/tasks/past202203_f
- 提出: https://atcoder.jp/contests/past202203-open/submissions/35030021
- 各マスを走査し、それぞれの隣接マスと国をまたいでいる場合は色が異なるかを調べる
- G - 方程式
https://atcoder.jp/contests/past202203-open/tasks/past202203_g
- 提出: https://atcoder.jp/contests/past202203-open/submissions/35030109
- 制約から
ax^5+bx > 0
なので単調増加する - 二分探索で
x
を試せば良い - 浮動小数点数や精度などがよく分からないので適当に 100 回ループした
- H - 連結成分
https://atcoder.jp/contests/past202203-open/tasks/past202203_h
- 提出: https://atcoder.jp/contests/past202203-open/submissions/35030288
- 連結成分の管理のようなので Dsu (Union-Find) が思い浮かぶ
- クエリ 2 ごとに N 件を走査すると間に合わないので leader を使って……は NG
- クエリ 2 で出力する件数の合計は
2*10^5
以下なので辺をたどれば良さそう - 提出したら TLE
- おそらく辺を増やされると辺をたどる過程で無駄が出てしまう
- Dsu (Union-Find) で既に連結している辺の追加を避けて AC
実装時に考えたことをメモしておくと良いかもしれない。毎日貼っているコミットの URL と合わせてみると良いかもしれない。そう思ったので試しに書いてみる。
bouzuya/rust-sandbox の twiq の実装メモはリポジトリにすこし残している。
https://github.com/bouzuya/rust-sandbox/tree/389a2b447463a061ec126bf7d9e4fd5d1022a8a0/twiq/docs
EventStore
trait の簡素化
EventStore
trait のメソッドをもうすこし簡素化したいfind_events
とfind_events_by_event_id_after
の二種類があるafter: Option<EventId>
を引数にして統一して良さそう- 時間的な余裕があるなら
criteria
にしておくほうが良さそう - 見えているユースケースが「ある EventId よりも後のもの」だけなので
after: ...
で進める
EventStream
の追加
Vec<Event>
となっているがEventStream
にしたほうが良い箇所がありそうEventStream
は単一のEventStreamId
を持ち、単調増加するEventStreamSeq
を持つ- ↑の定義から一部は
Vec<Event>
で残すことになりそう (EventStreamId
を横断する場合がある) - 「単一の
EventStreamId
を持つ」という部分を削る選択肢もあるだろうけど、現状はEventStream
のグループごとに取り得る event type が分類されているので、EventStreamId
ごとに区切るほうが良さそう EventStream
は aggregate の実装の共通部分を削減する上で効果がありそうEventStream
への追加のためにEventStreamSeq
の増加など定形処理が多いので削れそう- 現在の目標から外れているので保留する
InMemoryEventStore
の追加
InMemoryUserRepository
でHashMap
ではなくEventStore
にして共有しないと他の repository を追加した際に困るFirestoreEventStore
を進めても良いがまだ一意性の検査などに時間がかかるのでInMemoryEventStore
を作って先に進めたい
User::from_event_stream
の追加
InMemoryUserRepository
でInMemoryEventStore
から取得したVec<Event>
でUser
aggregate を再構築しようとして未実装なのに気づいたUser
aggregate に手を入れるならEventStream
を実装しても良いかもしれない- 明日はここから
今日のコミット。