この間DDDについて勉強した時に知った「ドメインオブジェクトとインフラストラクチャの依存関係の逆転」を実践してみた。かなりしっくりくる。設計に関して何かがしっくりくる、という経験は初めてしたかもしれない。すごい。
今日解いた競プロの問題。
競プロ典型90問
006 Smallest Subsequence: 辞書順は前の文字の順序が後ろのすべてに優先するので、文字種でソートして拾っていく。ただし出来るだけ後ろの選択肢は残したいので、同じ文字種ならば出来るだけ左からとる。また、i文字目を決める際に後ろにはK-i文字以上残っていないといけないので、戦闘N-K+i文字の中からのみ拾っていく。あまりやらない実装だったので考察があってるか若干不安だったが、無事一発ACした。
007 CP Classes: ソートしてにぶたんするだけ。Bi以上最小とBi以下最大の両方を取るところだけ注意すればよい。
008 AtCounter: i文字目まで見てj文字目まで決めた状態のパターン数を持ってDPやるだけ。
009 Three Point Angle: ABC033-Dで見た。全探索すると当然$O(N^3)$になる。ある点$P_1$を中心として他の点を偏角でソートし、$P_1$以外のある点$P_2$を取り出して偏角を二分探索すれば、$\angle P_2P_1P_3$が良い条件を満たすような点P3を各$O(\log N)$で探すことができる。全体$O(N^2 \log N)$。方針は一瞬で見えたが偏角ソートをライブラリ化していなかったので実装にかなり手間取った。
他、非本質でさらに手間取る。計算誤差が嫌なので分数の比較は分母を払い、平方根は二乗するなどしていたが、そうすると64bitではオーバーフローする、二乗したために符号が狂うなどした。std::sortにa<b&&b<aがtrueとなるような比較関数を渡してしまうとinvalid comparator例外が飛び出すということを学んだ。また、acos(-1)が実は誤差でacos(-1.000001)みたいになっていたために範囲外エラーが起きるなどといったことも起こった。この辺はライブラリ化で次回以降かなり対処できそうなのでちゃんとライブラリ化した。
公式解説だと偏角ソートまわりはatanでかなりスマートに解決していた。
「2Dグラフィックスの仕組み」を読み進めた。ピクセル単位で具体的に何をやるのかをちゃんと解説していてとても良い。
ダンスガード・オシュガーサイクルというのを知った。氷期・間氷期とかは知ってたが更に短いのもあるんだな。
今日摂取したコンテンツ。
10億円資産ができたときに知っておいた方が良いこと
https://anond.hatelabo.jp/20220410232915
https://anond.hatelabo.jp/20220413220417
まあ話半分くらいに聞いておいた方が良さそうだが、なんかリアルな実情って感じで面白かった。
Categories: 未分類