子どものウイルス性胃腸炎をみるために一日家に居た。うつってしまったのか嘔吐・下痢・発熱している。
最低限のノルマだけこなしたので夕食を抜いて寝る。リングフィットアドベンチャーはさすがにつらいので諦めた。
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit
子どものウイルス性胃腸炎をみるために一日家に居た。うつってしまったのか嘔吐・下痢・発熱している。
最低限のノルマだけこなしたので夕食を抜いて寝る。リングフィットアドベンチャーはさすがにつらいので諦めた。
今日のコミット。
2022-W02 をふりかえる。
目標。
記事。
(なし)
(なし)
勉強会。
(なし)
おでかけ。
(なし)
ゲーム。
買い物。
体調。
(なし)
育児。
2022-W02 はどうだったか。
全体的に停滞している。
仕事は淡々とやっている。
ABC235 は +2 。問題を解いたときに考えたことなどを書き続けている。
rust365 (2021-05-14) は its をつくっている。あまり進んでいない。
スーパーマリオ オデッセイは奪われし国・クッパの国・月の国・キノコ王国をクリアした。一応はエンディングを見た。コンプリートに向けて進めている。
『セキュア・バイ・デザイン』はまったく進んでいない。
第八回 アルゴリズム実技検定 (PAST) E - カラフルなTシャツを解いた。
https://atcoder.jp/contests/past202109-open/tasks/past202109_e
色ごとに最も安いもの以外は買う必要がない。価格の安い色を K 種類買えば良い。 K 種類に満たないときは -1 になる。
ぼくは色と価格を Tuple にして価格で昇順にソートして走査し、一度選んだ色は Set に追加して既に選んでいないか、 K 個を超えていないかを確認することで解いた。
ソートと Set への挿入を伴う走査はどちらも O(NlogN)
なので全体としては O(NlogN)
で間に合う。
先に色ごとの最小値を求める方法でも解いてみた。色ごとの最低価格を保持する Map を用意する。価格の昇順で先頭から K 個の合計を求めると良い。 K 種類の色がないときに -1 を返すことを忘れないように注意する。
ABC235 に参加した。 D は冷静にやれば解けそうだった。
今日のコミット。
第八回 アルゴリズム実技検定 (PAST) D - 約数を解いた。
https://atcoder.jp/contests/past202109-open/tasks/past202109_d
X と Y のそれぞれの約数の個数を求めて比較して出力する。
約数の列挙については 2020-04-06 で書いた。整数 N の約数列挙は 1 から √N までの整数 i で試し割りすれば良い。 N を i で割り切れる場合は i と N / i を追加する。 i * i = N
のときに二重で追加しないよう注意する。 O(√N) 。
X, Y <= 10^6
なので間に合う。
今日のコミット。
第八回 アルゴリズム実技検定 (PAST) C - 出現回数を解いた。
https://atcoder.jp/contests/past202109-open/tasks/past202109_c
N 個の正の整数からなる数列 A に X が何個含まれるかを求める。
N <= 10^5
なので A を走査して X と一致するものを数えれば間に合う。
its 0.5.0 をつくった。
イベントを永続化していてイベントの構造が変わるとどうすべきか迷う。今回は永続化の形式は省略可能な項目の追加とすることで互換性を保ち、内部では V2 として別のイベントを定義して古いイベントは読み込み時および処理時に変換する処理を入れた。互換性を考えると妥当そうな方法ではあるもののコードにゴミがたまっていくのも嫌ではある。基本はこういう運用を続けてメジャーバージョンアップ時にマイグレーションを入れて新しいイベントのみを残してすべて消してしまうのが良さそう。
今日のコミット。
第八回 アルゴリズム実技検定 (PAST) B - 積集合を解いた。
https://atcoder.jp/contests/past202109-open/tasks/past202109_b
N 個からなる数列 A と M 個からなる数列 B の共通の要素を昇順に出力する。
N, M <= 1000
なので O(NM)
でも間に合う。 A の各要素について B の全要素を走査して存在するかを確認してあれば出力対象に追加……を繰り返して O(NM)
。昇順に出力なので忘れずソートする。共通の要素は最大でも MIN(N, M)
個なのでソートしても計算量への影響はない。
todays-commits 0.2.0 をつくった。↓の「今日のコミット」をつくるためのコマンドなのだけど GitHub API で updated で並べていたら取得できなくなった (?) ので確認する列を pushed に切り替えた。
一昨日までは push でも updated が更新されていたように思う。何か変更したのだろうか。
今日のコミット。
第八回 アルゴリズム実技検定 A - ドリンクバーを解いた。
https://atcoder.jp/contests/past202109-open/tasks/past202109_a
A + B - C
と D
のうち小さい側を出力すれば良い。
C < B
なので入力を usize
で取って↑のとおり計算して問題ない。
A + B < C
のケースがありえると usize が負の数になって RE になってしまう点に注意する。
スーパーマリオ オデッセイで月の国をクリアしクッパを倒した。ひとまずエンディングを見た。パワームーンのコンプリートを目指していく。
今日のコミット。