bouzuya.hatenablog.com

ぼうずやのにっき

いろいろ注文した

DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 の D を解いた。

  • D - Digit Sum Replace https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_d
    • 提出: https://atcoder.jp/contests/ddcc2020-qual/submissions/32657564
    • 解説 AC
    • 足して 10 以上なら桁が減らない
    • すごい桁がある→どうすりゃいいんだ……
    • 断念
    • 解説を見るととてもかんたんだった
    • 操作の前後でどう変わるのかをもっとよく見ないといけなかった
    • 操作の前後で足して 10 以上なら桁が減らない・すべての桁の総和は 9 減る
    • 操作の前後で足して 10 未満なら桁が減る・すべての桁の総和が減らない
    • 桁の総和を S 、桁数を D とする
    • 桁が減る操作は D - 1 回できる
    • 桁が減らない操作は \lfloor (S - 1) / 9 \rfloor 回できる
    • 答えは (D - 1) + \lfloor (S - 1) / 9 \rfloor

いろいろ注文した。椅子を買った影響で調整が必要になったため。

今日のコミット。

ARC142 の C を解いた

ARC142 : AtCoder Regular Contest 142 の C を解いた。

  • C - Tree Queries https://atcoder.jp/contests/arc142/tasks/arc142_c
    • 提出: https://atcoder.jp/contests/arc142/submissions/32641571
    • 回数的に d_1x と d_x2 を主に使うと推測した
    • 2 の位置ごとに場合分けすると 1 の子である場合・ x_1 の子孫である場合・ x_1 以外の子孫である場合になった
    • わりと惜しいところまで行けたと思うのだけど分岐が多く微妙な WA を消すのが面倒そうなので断念
    • 解説 AC
    • 1 から x と x から 2 を主に使うところまでは正解
    • d_1x + d_x2 の最小値がほとんどの場合に答えになる
    • d_1x + d_x2 が 3 のとき「 1 の子である場合」の分岐がある
    • d_1x + d_x2 が 3 のものが 2 個以外のときは 1 (x の子孫であることがない)
    • d_1x + d_x2 が 3 のものが 2 個のときはその 2 個の距離が 1 なら 3 そうでないときは 1
    • ここまで整理できる気がしない
    • インタラクティブな問題はサンプルもなくてイライラする

JUnit5 ではテスト名は @DisplayName を使うと良い。以前はメソッド名を日本語で……といった方法が広められていたものの IDE の既定の設定で警告が出たり空白が使えなかったりとつらいので。

https://junit.org/junit5/docs/current/api/org.junit.jupiter.api/org/junit/jupiter/api/DisplayName.html

今日のコミット。

AGC017 の B と ABC112 の A, B, C, D を解いた

AGC017 : AtCoder Grand Contest 017 の B を解いた。

  • B - Moderate Differences https://atcoder.jp/contests/agc017/tasks/agc017_b
    • 提出: https://atcoder.jp/contests/agc017/submissions/32624169
    • 解説 AC
    • 解説がわかりやすい
    • Y_i = X_{i+1} - X_i とおく
    • -D <= Y_i <= -C C <= Y_i <= D \sum_{i=1}^{N-1}{Y_i} = B - A となる
    • m 個が -D <= Y_i <= -C のとき N - 1 - m 個は C <= Y_i <= D になる
    • よって -Dm + C(N - 1 - m) <= \sum_{i=1}^{N-1}{Y_i} <= D(N - 1 - m) + -Cm
    • -Dm + C(N - 1 - m) <= B - A <= D(N - 1 - m) + -Cm
    • m をすべて試して↑を満たすものが存在すれば YES なければ NO

ABC112 : AtCoder Beginner Contest 112 の A, B, C, D を解いた。

今日のコミット。

2022-W24 ふりかえり

2022-W24 をふりかえる。

2022-W24 の目標 とその記事

目標。

記事。

つくったもの

よんだもの

(なし)

みたもの

その他

勉強会。

(なし)

おでかけ。

ゲーム。

買い物。

(なし)

体調。

育児。

  • 上の子はワッペン付きの服をみて「このふく、けいさつかんみたい！」とはしゃいでいた (2022-06-16)
  • 上の子はスーパーマリオ 3D ワールドのプレイを続けて上達している
  • 下の子はちょっとはやく歩く

2022-W24 はどうだったか。

のどが痛い。せきが出ている。ひどくなっている。そろそろ熱が出そう。

朝のラジオ体操や懸垂やリングフィットアドベンチャーを続けている。リングフィットアドベンチャーは来週あたりで称号コンプリートできそう。

仕事では大規模なリファクタリングをしていた。

AtCoder は ABC256 で 1174 (-20) でまた下げた (https://atcoder.jp/users/bouzuya/history/share/abc256) 。水色復帰どころかさらに下げた。

朝・夜のコミットは続けている。 rust365 (2022-02-19) は its 0.18.0 で its issue update-title を追加した。気まぐれに suiro という水路パズルをつくろうとしている。

『 Loop Hero 』をプレイしている。

2022-W25 の目標

  • tokio tutorial を読む
  • Loop Hero のことを書く

AGC016 の B を解いた

AGC016 : AtCoder Grand Contest 016 の B を解いた。

  • B - Colorful Hats https://atcoder.jp/contests/agc016/tasks/agc016_b
    • 提出: https://atcoder.jp/contests/agc016/tasks/agc016_b
    • 解説 AC
    • 解説動画 https://youtu.be/kdQtQSgIYPI?t=1350 の頭の数列を求めるには……が大切だった
    • 数列は全体の色数からそれを除くことで色数が減るなら色数-1そうでないなら色数として求められる
    • 全体の色数を A とする
    • a_i は A か A-1 しかない → MAX(a) - MIN(a) > 1 なら No
    • MAX(a) - MIN(a) = 0 なら「それを除いても色数の減るものがない」
    • 各色は 2 匹以上に被られている
    • 全体で一色なら a_i = N-1 そうでなければ 2 * a_i <= N
    • MAX(a) - MIN(a) = 1 なら「それを除くと色数の減るものがある」ので
    • a のうち MIN(a) と一致する個数が 1 匹だけに被られている (除くと色数の減るものの個数)
    • a のうち MAX(a) と一致する個数が 2 匹以上に被られている (除いても色数の減らないものの個数)
    • 前者を COUNT_MIN, 後者を COUNT_MAX とする
    • MAX(a) は減らないものの個数なので色数 A = MAX(a) になる
    • 2 匹以上に被られている「色数」は A - COUNT_MIN で求められる
    • COUNT_MIN < A かつ 2 * (A - COUNT_MIN) <= COUNT_MAX
    • usize を使ったので 2 * A <= COUNT_MAX + 2 * COUNT_MIN とした

ABC256 に参加した (https://atcoder.jp/users/bouzuya/history/share/abc256) 。 1174 (-20) で水復帰ならず。 B でハマって慌ててしまった。 D でもったいない WA を出した。 E はもうすこし時間があれば解けたと思う。

近所の風呂屋に行った。想像はしていたけど子どもを連れて……は厳しい。

今日のコミット。

ARC134 の C を解いた

ARC134 : AtCoder Regular Contest 134 の C を解いた。

bouzuya/rust-sandbox its 0.18.0 をつくった。

its issue update-title を追加した。特に新しい要素はないので作業。

2022-W21 あたりから子どものお絵かきボード (ブギーボードの大きいようなもの) をメモに使っていたのだけどやめた。

紙の場合は「書いたものを残したままもう一枚」ができるもののお絵かきボードだと消してしまわないといけない。写真などを撮って……とするのが正しいのは分かるのだけど実際問題不便だった。

今日のコミット。

ARC138 の A を解いた

大和証券プログラミングコンテスト 2022 Spring (ARC138 : AtCoder Regular Contest 138) の A を解いた。

  • A - Larger Score https://atcoder.jp/contests/arc138/tasks/arc138_a
    • 提出: https://atcoder.jp/contests/arc138/submissions/32502350
    • 1..=K と K+1..=N から 1 項ずつ選んで swap する
    • 1 項でも swap すれば s+1 以上になるはずなので 2 項ずつ選ぶ必要はない
    • 操作回数は swap する項のうち 1..=K 側を i K+1..=N 側を j としたとき j-i になる
    • i を走査して A_i < A_j を満たす j のうち最小のものを得たい
    • A を座標圧縮したものを B とし、セグメント木で B_j に j を入れて B_i + 1..=N の範囲の MIN(j) を取って解いた
    • 解説を見ると (A_i, -i) でソートして走査し i > K のときそこまでの i <= K のうち最大のものと交換すれば良いとなっていた

『カールじいさんの空飛ぶ家』を観た。別れの多い映画で悲しい気持ちになった。

crates:termion を使って suiro に UI をつけている (途中) 。

上の子がワッペン付きの服をみて「このふく、けいさつかんみたい！」とはしゃいでいた。

今日のコミット。