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 の簡素化
EventStoretrait のメソッドをもうすこし簡素化したい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>でUseraggregate を再構築しようとして未実装なのに気づいたUseraggregate に手を入れるならEventStreamを実装しても良いかもしれない- 明日はここから
今日のコミット。