bouzuya.hatenablog.com

ぼうずやのにっき

AGC009 の B を解いた / 子どもが新型コロナウイルスに感染した

AGC009 : AtCoder Grand Contest 009 の B を解いた。

  • B - Tournament https://atcoder.jp/contests/agc009/tasks/agc009_b
    • 提出: https://atcoder.jp/contests/agc009/submissions/33377796
    • 青 diff だけど普通に解けてしまった
    • 木 DP
    • 人 1 を根、対戦を辺とした木を考える (トーナメント表のまんまではある)
    • すべての頂点のそこまでに必要な対戦回数の最小値を求める
    • 葉は子がないので対戦回数は 0
    • 葉以外はそれぞれの子の必要な対戦回数をうまく並び替えることで求める
    • 対戦順序はその子がそこまでの対戦回数の昇順にすると良い
    • 木の深さを最小にしたいので、子と対戦する間にも並行して対戦を進められる (問題の条件から子と子の間には対戦はない)
    • 最初の対戦により深さの必要となるものを置くより最後の対戦に置いたほうが必要数を減らせる
    • 子との対戦ごとに対戦回数は +1 と「その子のそこまでの対戦回数」から「子との対戦回数」を引いたものを足すと求められる
    • DFS の帰りがけ順にこれらを埋めていけば根における値 (答え) が求められる

CQRS の Query 側をどう実装したものか迷っている。

Query 側 DB に query に適した形式で永続化しようと思っている。 Command 側 DB ないし何かしらの機構でそこに書かれる Event を読み込んで、 Query 側 DB に書き込む。 Query 側は query を受け取って Query 側 DB を読み込んで返す。大枠はこんな感じ。

いま迷っている点は Command 側とどれくらい分離・共有するか。少なくとも Query 側 DB の writer は Command 側からの Event の reader でないといけないので、その構造は共有しないといけなさそう。

昨日 (2022-07-19) の続き。子どもが新型コロナウイルスの検査で陽性になった。困った。

今日のコミット。