Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【AGC001-B: Mysterious Light】再帰的な性質に気づく方法

B - Mysterious Light

N=1000までの部分点なら理解出来ましたし、コンテスト中にも気づくべきだと思いました。

問題

三角形の中を不思議な光が反射するから長さを求めなさい

考え方

f:id:akiradeveloper529:20190814141444p:plain

このサンプルのうち、3番目と5番目の光に注目すると、どちらも平行四辺形の中を鈍角から打ち出されてるという共通点があります。従ってここに再帰的な性質を見出します。

ある平行四辺形の鈍角から発射した光が最終的に辿る距離を、平行四辺形の長さをa,bとしてf(a,b)で表すと、サンプルから、f(a,b) = 2*a + f(a,b-a)が言えそうです。

しかし、これははっきりと証明されているわけではなく、たぶんそうなるだろうとしか言えないと思います(少なくともコンテスト中には)。

あとは、1番目と2番目の光の合計がNなので、答えはN+f(N-X,X)となります。

実装

fn f(a: usize, b: usize) -> usize {
    assert!(a<=b);
    if a==b {
        return a
    }
    let (x,y) = if a <= b-a {
        (a, b-a)
    } else {
        (b-a, a)
    };
    2*a + f(x, y)
}
fn solve() {
    input! {
        N: usize, X: usize,
    }
    let (a,b) = if X <= N-X {
        (X, N-X)
    } else {
        (N-X, X)
    };
    println!("{}", N+f(a,b));
}

考察

sorted(desc=false, x...)みたいな関数はテンプレで持っておいてもいいかなぁと思った。コードがわかりづらいので。

ずっと1本目と2本目を絡めて再帰を探そうとしていましたが、1本目と2本目を無視するというのがポイントでした。再帰的な性質を見つけるには、全体ではなく部分に注目するという手筋もあるのだとわかりました。

満点解法はたぶん、bからaを引ける回数が事前に計算出来るから、一回一回やっていくではなくどかっどかっと計算していくことが出来ることを言ってるのだと思います。