bouzuya.hatenablog.com

ぼうずやのにっき

AGC049 : AtCoder Grand Contest 049 B - Flip Digits を解いた

AGC049 : AtCoder Grand Contest 049 B - Flip Digits を解いた。 https://atcoder.jp/contests/agc049/tasks/agc049_b

特定の操作を繰り返すことで S を T にできるか。最小回数はいくつか。

考えたこと:

  • 00 のときなにもできない
  • 01 のとき 10 にできる
  • 10 のときなにもできない
  • 11 のとき 00 にできる

これらの操作は↓の操作と解釈できる。

  • 1 を左に動かす (ただし左端からは動かせない)
  • 2 つ連続する 1 を消す

消す操作は 2 個ずつなので偶奇の変化はない。

1 の個数は増やせないので S の 1 の個数が T のそれ未満なら -1 。 1 の個数の偶奇の変化はないので S の 1 の個数と T のそれの偶奇が異なるなら -1 。 1 は左には移動できるが右には移動できないので S の右端の 1 より右側に T の 1 があれば -1 。 気持ち的には右から合わせていきたい。左を先に片付けないと右を合わせられない。左から合わせる。

個数を合わせてから移動する？と良さそう。 個数を合わせるにはどうすればいいか。 右端からの累積和を取って比較し、 T のその位置で多い分を消す。

例 3 だと↓なので……

10111
01010

累積和は↓。

012345 # 位置
433210
221100

これで操作を考えると……

  • 左に動かすと 33 を 32 にできる
  • 2 つを消すと 43 を 22 にできる

……

このあたりまで考えて諦めた。

公式解説: https://atcoder.jp/contests/agc049/editorial/330

よく分からない。

参考: https://zenn.dev/wapa5pow/articles/agc049-b-14e544392d0df7a7f711

なるほど。わかりやすい。 S_i != T_i なら 1 を持ってくることでしか合わせられない。ただ合わせるとそれぞれについて走査する必要があるので O(N2) になってしまう。そこで最後に探した 1 の位置を保持しておくことで O を下げている。確かに間に合う。

セキュア・バイ・デザインを読み進めている。

上の子のための本やはさみを買った。

今日のコミット。

2022-W01 ふりかえり

2022-W01 をふりかえる。

2022-W01 の目標 とその記事

目標。

  • ☑ 『 Domain Modeling Made Functional 』を読む

記事。

つくったもの

よんだもの

  • 『 Domain Modeling Made Functional 』 (2022-01-03)

『セキュア・バイ・デザイン』を読みはじめた (が進んでいない) 。

みたもの

その他

勉強会。

(なし)

おでかけ。

(なし)

ゲーム。

買い物。

体調。

(なし)

育児。

  • 上の子はスーパーマリオランをよく遊んでいる
  • 下の子はお尻が真っ赤だ
  • 下の子はつたい歩きが早くなっている

2022-W01 はどうだったか。

仕事がはじまった。 Java / Mockito などをひさびさに触っている。ゆるゆるやっている。

rust365 (2021-05-14) は its をつくっている。 Domain Modeling Made Functional を踏まえて Command & Event を使おうといろいろ考えている。 Event をああだこうだ考えていると自然と Event Sourcing になっている。

ABC234 は -17 で下げている。過去問題の考察を書くようにしている。

スーパーマリオ オデッセイは海の国・雪の国・料理の国をクリアした。進めている。

来週からは本格的に『セキュア・バイ・デザイン』を読んでいく。

2022-W02 の目標

ARC131 C - Zero XOR を解いた

ARC131 C - Zero XOR を解いた。

https://atcoder.jp/contests/arc131/tasks/arc131_c

最後の一個を取り除くか XOR が 0 なら勝ち。 後ろから考える。自分の手番で…… 残り 1 個なら勝ち。 残り 2 個なら負け。 残り 3 個なら勝ち。 残り 4 個なら XOR が 0 になれば勝ち、そうでなければ負け。 残り 5 個なら任意の 2 個を選択した後に XOR が 0 にならなければ勝ち、そうでなければ負け。

任意の 2 個を選択した後に XOR が 0 にならなければを愚直にやると O(N2) で解けない。

解説によると偶数個取り除いて奇数個で XOR は 0 にならないことが証明できるので奇数は必勝、偶数なら XOR が 0 にできるなら勝ちということらしい。惜しい。

ABC234 に参加した。 E まで解いて -17 。

https://atcoder.jp/users/bouzuya/history/share/abc234

スーパーマリオ オデッセイ 雪の国をクリアした。

今日のコミット。

ABC233 F - Swap and Sort を解いた

ABC233 F - Swap and Sort を解いた。

https://atcoder.jp/contests/abc233/tasks/abc233_f

順列の各要素を頂点・操作対象の要素間を辺とすることは見えた。連結成分内での要素の swap はできるけど、連結成分間では swap できないのでそうなってしまうと -1 になるのも見えた。ただ P を昇順に並べ替える方法とそれが 5 * 10^5 におさまるのかが見えなかった。

解説動画: https://youtu.be/-6clqT8n794?t=1107 解説: https://atcoder.jp/contests/abc233/editorial/3164

連結成分ごとに葉から順に正しい要素へとあわせていく。「葉から順」は dfs して帰りがけ順にすれば良い。さらに各要素ごとに入れ替えるべき要素を dfs して探す。見つからなければその連結成分には存在しないので -1 。最悪の場合は正しい位置に持ってくるのに要素数分の swap なので 1 個目は 999 2 個目は 998 ……となる。

AMAZON ORIGINAL 『シンデレラ』を観た

今日のコミット。

AGC037 A - Dividing a String を解いた

AGC037 A - Dividing a String https://atcoder.jp/contests/agc037/tasks/agc037_a を解いた。

未証明の貪欲法で。長さが違えば S_i != S_{i+1} にはなるので雰囲気としては 1 つおきに結合するだけで十分になる。この場合は最後の要素の残り方次第でおかしくなるので後ろのほうで調整した。

見た目や diff よりずっと難しく感じた。

参考: https://drken1215.hatenablog.com/entry/2020/11/11/164900 参考: https://betrue12.hateblo.jp/entry/2020/05/01/201510

bouzuya/rust-sandbox の its/0.2.3 をつくった。機能は増えていないのだけど Aggregate を Entity とは別物として定義するのを試している。

頭が痛い。

今日のコミット。

ARC118 C - Coprime Set を解いた

ARC118 C - Coprime Set を解いた。

問題: https://atcoder.jp/contests/arc118/tasks/arc118_c 解説: https://atcoder.jp/contests/arc118/editorial/1206 参考: https://xenous.hatenablog.com/entry/2021/05/10/011235

  • i != j に対して A_i != A_j かつ gcd(A_i, A_j) > 1 …… (1)
  • gcd(A_1, A_2, ..., A_N) = 1 …… (2)

(1) から A_i は A_j の倍数になっている。 (2) から数列全体では共通部分がない

素数を列挙するのかと思ったけど素数だと (1) を満たせない。 ここで頭が止まってしまって解説を読む。 解説を読んでもいまひとつよく分からないので別の記事を検索して参考 URL に至る。

6, 10, 15 は 2 * 3, 2 * 5, 3 * 5 。

これらの倍数を追加すると条件を満たしながら数列を大きくできる。

数列の最大個数が N (2500) を超えていれば良い。

fn f(set: &mut BTreeSet<usize>, a: usize, b: usize) {
    for x in 1.. {
        if a * x > 10000 {
            break;
        }
        for y in 1.. {
            if a * x * b * y > 10000 {
                break;
            }
            set.insert(a * x * b * y);
        }
    }
}

こういう感じの関数をつくって f(&mut set, 2, 3) てな具合にした。

『セキュア・バイ・デザイン』を読みはじめた。

今日のコミット。

SwitchBot カーテン (第二世代) を買った

SwitchBot カーテン (第二世代) を買った。壊れてしまったので手で開けていたけどやはり時間で開けたいので買いなおした。道具なしに手でローラー部分の取り外しができるようになっていた。ローラー部分のつくりも若干変わっていた。箱にぴっちり入っていて開封しづらいのは変わらず。細かい変化はまだよく分からない。

セキュア・バイ・デザインを買った。明日から読んでいく。

第二回日本最強プログラマー学生選手権 D - Nowhere P を解いた。

問題: https://atcoder.jp/contests/jsc2021/tasks/jsc2021_d 解説: https://atcoder.jp/contests/jsc2021/editorial/1108

とっかかりがなさそうだと諦めてすぐ解説を読んだ。

P の倍数になってはいけないので x mod P ≡ 0 を避ける。 A_1 は [1, P) から選べるので P - 1 通り。 A_2 は A_1 で選んだものとの和の mod P が 0 にならないように選ぶと P - 2 通り。 これが長さ N まで続くので (P - 1)(P - 2)^(N - 1) で求められる。

解説を読んでから思ったことにはきちんと手で試せば分かったかもしれない。

『スーパーマリオ オデッセイ』海の国をクリアした。ビーチバレー 100 回は検索したら 2P 側で操作すると良いとあってそのとおりにしたらクリアできた。

今日のコミット。