bouzuya.hatenablog.com

ぼうずやのにっき

2022-W35 ふりかえり

2022-W35 をふりかえる。

2022-W35 の目標 とその記事

目標。

  • ☑ 2022-07 ふりかえりを書く
  • ☑ 2022-08 ふりかえりを書く
  • ☑ ブラーバのことを書く
  • ☐ 『ソフトウェアテスト技法練習帳』を読み進める

記事。

つくったもの

(なし)

よんだもの

(なし)

みたもの

(なし)

その他

勉強会。

(なし)

おでかけ。

ゲーム。

  • フィットボクシング 2 31 + 1 + 36 日目 (2 + 2 日抜け)
  • Mindustry 24 で 3 連敗 (進まず)
  • スーパーマリオ 3D ワールド ワールド 8 (進まず)

買い物。

  • ブラーバジェット m6 (...)

体調。

育児。

  • 上の子は下の子を暴力でなんとかする
  • 上の子は涼しくなってきたが水シャワーをやめない
  • 上の子は懸垂マシンに登るのをやめない
  • 下の子は壁にクレヨンで落書きをした (ベタそうだが上の子のときはなかった)
  • 下の子はとにかくすぐに泣く

2022-W35 はどうだったか。

2022-08 が終わった。すこし涼しくなっている。

AtCoder は ABC267 に参加した。 1208 → 1170 (-38) (https://atcoder.jp/users/bouzuya/history/share/abc267) 。茶パフォを出して緑に落ちた。良くない解き方をして良くない結果になった。

朝・夜のコミットを続けている。 rust365 (2022-02-19) は twiq を進めている。

プログラミング Tips ぽいもの。

ラジオ体操・懸垂・フィットボクシング 2 を続けている。まだ二人目を進めている。

2022-07, 2022-08 のふりかえりを書いている。『ソフトウェアテスト技法練習帳』ずっと書いてあって笑ってしまう。読む・やる気がないのになぜ書いてあるんだろう。停滞している。

停滞している。

2022-W36 の目標

疲れている

今日は一日子どもに振り回されて疲れている。日に当たりながら動き回るとだいたいダメ。

ABC267 。まだ結果は出ていないけど緑になる。 C で問題文の読み間違いとつまらないミスでハマってしまい、 C の発展問題の D を飛ばして、 E が解けそうで解けず、逆転もなく終了。

今日のコミット。

ABC201 A, B, C, D, E を解いた

マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201） の A, B, C, D, E を解いた。

kubernetes で kind: CronJob の一覧を得たいときは kubectl get cronjob 。

体調が悪い。

今日のコミット。

ABC263 の E を解いた

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263） の E を解いた。

  • E - Sugoroku 3 https://atcoder.jp/contests/abc263/tasks/abc263_e
    • 提出: https://atcoder.jp/contests/abc263/submissions/34492207
    • 解説 AC
    • 本番でも解けず
    • こういう場合に後ろから考えるのは分かる
    • また DP なのも分かる
    • とりあえず求めたいものを DP に入れて DP[N] = 0 からはじまって DP[1] が答えになるのは分かる
    • あとは式を書いて変形・整理すると TLE だが解ける
    • AC するためにはあとは区間の和が高速に求められれば間に合うことが見える
    • DP で貰う DP にして区間の和や最大値などを累積和やセグメント木などと組み合わせて高速化するのはよくある形
    • 今回は累積和と DP で解いた
    • 式を書いて変形・整理するところができなかった (うーん……)

今日のコミット。

googleapis/google-cloud-rust を試している / ABC134 の A, B, C, D, E を解いた

https://github.com/bouzuya/rust-sandbox/commit/8b358eb7e56a01011d0312677bdf88ff61d2dae8 で https://github.com/googleapis/google-cloud-rust を使うようにしてみた。これで bouzuya/rust-sandbox の twiq の firestore との認証まわりが解決した。

google-cloud-rust の google-cloud-auth は Google Cloud 用の認証を担う crate 。 https://google.aip.dev/auth/4110 にある ADC : Application Default Credentials を実装してある。ドキュメントを参照しながら自身で実装しても良いのだけど各環境での取得やリフレッシュの考慮などが面倒なのでこれを使うことにした。

ローカルでは Service Account Credential ファイルを用意して GOOGLE_APPLICATION_CREDENTIALS 環境変数にそのパスを書く。 Cloud Run などの環境では特に何も指定しなくても既定の Credential を取得してくれる……はず (未検証) 。

ABC134 : AtCoder Beginner Contest 134 の A, B, C, D, E を解いた。

今日のコミット。

ブラーバジェット m6 を返却した

2022-08-28 にブラーバ m6 を返却した。これは 2022-08-03 にレンタルしていると書いたものだ。約 1 ヶ月にわたって試した結果として「買っても良さそうだ」と感じている。 2022-08-03 の印象から大きく変わることはなかった。

これはルンバや食洗機などでもそうだったけど、まず「過度に期待してはいけない」。人が丁寧に掃除するとそちらのほうがきれいだ。期待するのは「最低限の作業を機械に肩代わりさせる」こと。ルンバのとき (2020-09-09) に書いたのだけど、なくなると効果があったのだとわかる。ルンバがきれいにしてくれるという印象はないけど、毎日のように動いてホコリをはらう (最低限の作業) 程度の仕事はして、確かにゴミを集めている。たぶんブラーバも同じような効果を期待できると思う。そこまできれいにはならないけど、毎日のように動いて床を拭くのは差が出ると思う。その程度の効果を期待するのが良い。過度に期待してはいけない。

あとは「機械が活躍できる状態に持っていく」ことの効果がある。床にものを置かない。これはとても大きい。例えとして適切か分からないけどプログラマ的には「テスタビリティ」っぽいと思っている。テストを書くかはともかくテスタビリティを確保しておくと良い。床を掃除するかはともかく床にものを置かないほうが良い。そんな感じ。いざ床を掃除したくなったとき床のものをどけるところからはじめなくて済む。テスタビリティの確保が保証される嬉しさに似ている。

Amazon での価格が先週くらいまでは 59,800 円 +5,980 ポイント (10%) で 53,820 円だったのが 76,868 円 +23,048 ポイント (30%) で 53,820 円になっている。おそらくポイントを使って支払った際に金額が下がることでポイントも下がって損するはずなので、以前の価格に戻ったタイミングで買おうかと思っている。そも公式の価格が 59,800 円だから……。

最後にレンティオ (rentio) の返却は開封時点から箱を残せ・梱包時のために写真を撮れと書いていたり梱包用のテープもついていて気がきいていた。無駄な買い物を減らせるかもしれないし、わりと良いサービスだと思う。

すこし体調が悪い。

ABC266 : AtCoder Beginner Contest 266 の E を解いた。

今日のコミット。

FieldValue.serverTimestamp は setToServerValue REQUEST_TIME か

疑問: Cloud Firestore の Node.js API の FieldValue.serverTimestamp は FieldTransform の setToServerValue REQUEST_TIME か。

結論: おそらくそう

https://firebase.google.com/docs/reference/js/firestore_.md#@firebase/firestore

https://www.npmjs.com/package/firebase

https://github.com/firebase/firebase-js-sdk

https://github.com/firebase/firebase-js-sdk/tree/v4.5.1/packages/firestore

https://www.npmjs.com/package/@firebase/firestore

If you are developing a Node.js application that requires administrative access to Cloud Firestore, use the @google-cloud/firestore Server SDK with your developer credentials.

https://www.npmjs.com/package/@google-cloud/firestore

https://github.com/googleapis/nodejs-firestore

https://github.com/googleapis/nodejs-firestore/blob/ce9abfd8cd65d0d2be4dd7f6a56fb679a100296a/dev/src/field-value.ts#L85-L87

  static serverTimestamp(): FieldValue {
    return ServerTimestampTransform.SERVER_TIMESTAMP_SENTINEL;
  }

https://github.com/googleapis/nodejs-firestore/blob/ce9abfd8cd65d0d2be4dd7f6a56fb679a100296a/dev/src/field-value.ts#L312-L366

/**
 * A transform that sets a field to the Firestore server time.
 *
 * @private
 * @internal
 */
class ServerTimestampTransform extends FieldTransform {
  /**
   * Sentinel value for a server timestamp.
   *
   * @private
   * @internal
   */
  static SERVER_TIMESTAMP_SENTINEL = new ServerTimestampTransform();


  private constructor() {
    super();
  }


  /**
   * Server timestamps are omitted from document masks.
   *
   * @private
   * @internal
   */
  get includeInDocumentMask(): false {
    return false;
  }


  /**
   * Server timestamps are included in document transforms.
   *
   * @private
   * @internal
   */
  get includeInDocumentTransform(): true {
    return true;
  }


  get methodName(): string {
    return 'FieldValue.serverTimestamp';
  }


  validate(): void {}


  toProto(
    serializer: Serializer,
    fieldPath: FieldPath
  ): api.DocumentTransform.IFieldTransform {
    return {
      fieldPath: fieldPath.formattedName,
      setToServerValue: 'REQUEST_TIME',
    };
  }
}

toProto は https://cloud.google.com/firestore/docs/reference/rest/v1/Write#fieldtransform の FieldTransform の setToServerValue と一致している。おそらく setToServerValue: 'REQUEST_TIME' を取得しているものだろうと判断した。

ABC106 : AtCoder Beginner Contest 106 の A, B, C, D を解いた。

  • A - Garden https://atcoder.jp/contests/abc106/tasks/abc106_a
  • B - 105 https://atcoder.jp/contests/abc106/tasks/abc106_b
  • C - To Infinity https://atcoder.jp/contests/abc106/tasks/abc106_c
    • 提出: https://atcoder.jp/contests/abc106/submissions/34441075
    • 先頭から K 文字目までを見ていく
    • 1 以外が出現した場合は 5000 兆日後にはその文字が続いているところを K は指すのでそれを出力する
    • 仮に K 文字目まで 1 が続く場合は K <= 10^18 なのでまずそうだが |S| <= 100 で 5000 兆日後の長さは K 以上なのですべて 1 の場合は 100 にしかならないため問題ない
  • D - AtCoder Express 2 https://atcoder.jp/contests/abc106/tasks/abc106_d
    • 提出: https://atcoder.jp/contests/abc106/submissions/34441508
    • Q 個のクエリのそれぞれで M 個の区間を調べると O(QM) になる
    • Q <= 10^5 で M <= 2*10^5 なので O(QM) では間に合わない
    • 試行 1: L で昇順に並べておくことを考えてみる
    • p..=q におさまるためには q <= L の位置を二分探索できる、これは速い
    • しかし q <= L な区間の中で R <= q な位置を探そうとすると順に走査すると遅い
    • かといって q <= L な区間の中から R でソートしては間に合わないのでダメ
    • 試行 2: 今度は p で昇順に並べることを考えてみる
    • その時点で p <= L なものを……これではあまり変わらないのでダメ
    • 全体から区間を絞る (減らす) のは難しいので、走査しながら足せば良いのではと思いつく
    • 試行 3: 区間を L の昇順、クエリを p の昇順に並べて、クエリを後ろから走査する
    • p <= L の区間を Vec に追加する
    • これで L の条件を満たすものだけを取り出せているので、もう L は気にしなくて良い
    • これでは R のソートが必要なので間に合わない (Vec ではダメ)
    • ただ R の集合のうち q 以下のものの個数を高速に取れれば良い
    • これは FenwickTree (BIT: Binary Indexed Tree) に適している
    • R の集合への追加は 1 点更新で、クエリは区間和だ
    • まとめ:
    • 区間を L の降順、クエリを p の昇順に並べる (クエリは答えのために添え字を残しておく)
    • クエリを後ろから走査する (p の降順に走査する)
    • 各クエリの p 以上の L を持つ区間を走査する (毎回区間を先頭から走査せず走査開始位置を保持しておく)
    • 各区間の R について、 FenwickTree の R の位置に区間の個数 1 を加算する
    • FenwickTree の 1..=q の区間和を得て、答えを保持する
    • 最後まで走査して答えを保持し終えたら添え字順に出力して終わり
    • ソートが O(NlogN) と O(QlogQ) で走査は O(Q + M logN) かな
    • 自力で解けた。解説では累積和で解いている

今日のコミット。