ARC051 A, B 考察

ARC051 A 塗り絵

赤の円・青の長方形のどちらが残る条件も相手の内側に収まっていない状態であること。逆に相手の内側に収まる条件を考える。

赤の円が青の長方形の内側に収まる条件……円の上下左右の端の点が青の長方形の左右の間かつ上下の間にあるとき。

青の長方形が赤の円の内側に収まる条件……長方形の左上・右上・右下・左下の四点が円の中心から半径以下の距離にあるとき。

https://atcoder.jp/contests/arc051/submissions/15368767

ARC051 B 互除法

実際に問題文の counter を実装して挙動を確認しながら解いた。

fn gcd(c: i64, a: i64, b: i64) -> (i64, i64) {
    if b == 0 {
        (c, a)
    } else {
        gcd(c + 1, b, a % b)
    }
}

fn f(a: i64, b: i64) -> i64 {
    gcd(0, a, b).0
}

#[test]
fn test_f() {
    assert_eq!(f(1, 1), 1);
    assert_eq!(f(1, 2), 2);
    assert_eq!(f(2, 3), 3);
    assert_eq!(f(3, 5), 4);
    assert_eq!(f(5, 8), 5);
    assert_eq!(f(314159265, 358979323), 12);
}

ユークリッドの互除法のアルゴリズムは gcd(b, a % b) で再帰する。次の a はひとつ前の b で次の b はひとつ前の a % b である。これを逆向きに進める。

a と b は i 番目と i + 1 番目で同じになっている。残りの a % b を無駄なく増やそうとすると a + b にしておくと良さそうだ（よく分からないけどそう見える）。結果的にこれはフィボナッチ数列になっている。

上限の K <= 40 でも a, b <= 10^9 には問題なさそうだった。

https://atcoder.jp/contests/arc051/tasks/arc051_b

https://developer.mozilla.org/ja/docs/WebAssembly をざっと読んだ。良い。

先週に読んでいた https://rustwasm.github.io/docs/book/ が ↑ からも触れられている。 Rust から〜というのは WASM 的には有力な選択肢のようだ。

『バック・トゥ・ザ・フューチャー PART2 』を観た。前回は 2016-07-14 に観ている。

前回の記事を観たらごちゃごちゃとケチをつけていたけど「同じ時間の別の場所を見せる」「裏では実はこうなっていた」みたいのはわりと好きだ。 アベンジャーズ / エンドゲーム (2019-05-05) のもわりと好きだった。

リングフィットアドベンチャー。継続している。ワールド 9 に入った。

昼寝を 15 分しようとしたら 3 時間寝ていた。朝も寝坊した。そして 23:00 を過ぎている。ボロボロだ。