2021-03-05

2015年度東大理系数学第4問(3) 解説

数学高校数学東大数学数列漸化式フィボナッチ数列

(1), (2)は他の方の解説に譲るとして、(3)を考えます。

(2)までの結果をまとめると、

$p_1 = 1, p_2 = 1\\ p_{n+1} + p_{n-1} = 3p_{n} \\$

ということでした。つまり、ある項はその前後の項を足して3で割った数であるということです。

これと、フィボナッチ数列の奇数番目が等しいことを証明せよというのが今回の問題です。

簡単に言えば、以下の図が書ければ終わりです。

f:id:coonevo:20210305041237j:plain

あとはこの図を用いながら帰納法で示せるかと思います。

多くの解説が数式でゴリ押していますが、漸化式でわざわざ $n-1$ を使っているあたり、問題作成者はある項とその前後の関係が〜という思想があったんだろうと感じました。

（実は本番に解いているのですが、(1)の証明ができなくて(2)のみを解いて終わりにした記憶があります。。。）

2021-03-04

HHKB プログラミングコンテスト 2020 D - Squares

AtCoder ABC 数え上げ対称性 O(1) 余事象

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）E - Throne

AtCoder ABC 拡張ユークリッドの互除法中国剰余定理 MOD 周期逆元互いに素

E - Throne
- 拡張ユークリッドの互除法による逆元計算
- 中国剰余定理
  - 実装

E - Throne

問題へのリンク

$S + m \times K \equiv 0 \pmod N$ を満たす最小の整数 $m$ を求めよ。

拡張ユークリッドの互除法による逆元計算

まず、与式を $m \equiv -S \times K^{-1} \pmod N$ と変形することで $K^{-1} \pmod N$ が求まれば、問題を解くことができるとわかります。

ここで、 $\pmod N$ における $K$ の逆元の存在条件は、 $N$ と $K$ が互いに素であることです。

NとKが互いに素のとき

$N$ と $K$ が互いに素のとき、 $K$ の逆元 $K^{-1} \pmod N$ は、拡張ユークリッドの互除法(extGCD)によって求まります。

拡張ユークリッドの互除法による逆元の求め方

$aK + bN = 1$ を満たす整数 $(a, b)$ をextGCDによって求め、この式を $\pmod N$ の式に変形すると、 $aK = 1 \pmod N$ となることから、 $K^{-1} = a$ つまり、aが $K$ の逆元になっています。

NとKが互いに素でないとき

$N$ と $K$ が互いに素ではない場合、 $K$ の逆元 $K^{-1} \pmod N$ は存在しません。では、今回の問題を解くことはできないのでしょうか。サンプルをみればわかる通り、そういうわけではありません。

$N$ と $K$ が互いに素でないなら、互いに素にしたくなります。 $N$ と $K$ を、 $g = gcd(N, K)$ で割った結果をそれぞれ $N^{\prime}, K^{\prime}$ とおくと、 $N^{\prime}$ と $K^{\prime}$ は互いに素です。

これら $N^{\prime}$ と $K^{\prime}$ をextGCDにかけることで、 $K^{\prime -1} \pmod {N^{\prime}}$ を求めることができました。

与式に戻り $N,K,S$ をそれぞれ $N^{\prime}, K^{\prime}, \frac{S}{g}$ に置き換え、

$\frac{S}{g} + m \times K^{\prime} \equiv 0 \pmod {N^{\prime}}$

とすれば、 $\frac{S}{g}$ が整数、すなわち $S$ が $g$ の倍数である場合に、先ほどextGCDによって求めた $K^{\prime -1} \pmod {N^{\prime}}$ を用いて $m$ を求めることができます。

$S$ が $g$ の倍数ではない場合、解はありません。

実装

提出へのリンク

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x2, y2;
    long long d = extGCD(b, a%b, x2, y2);
    x = y2;
    y = x2 - (a / b) * y2;
    return d;
}
long long mod_inv(long long a, long long m){
    ll x, y;
    ll d = extGCD(a, m, x, y);
    if(d != 1)return -1;
    if(x < 0)x += m; 
    return x;
}
long long safe_mod(long long a, long long m){
    return (a%m+m)%m;
}
void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    ll g = gcd(N, K);
    ll inv = mod_inv(K/g, N/g);
    if(S % g != 0){
        cout << -1 << endl;
    }
    else{
        ll ans = S/g * (-inv);
        ans = safe_mod(ans, N/g);
        cout << ans << endl;
    }
}

中国剰余定理

$S + m \times K \equiv 0 \pmod N$

という式から、以下のような連立合同式を考えます。

中国剰余定理によって、この連立方程式を解きます。（解がない場合もあります。その場合は、今回は-1を出力して終わりです）。

このとき、 $N$ と $K$ の最小公倍数を $lcm$ とすると、

$x \geq S$ の場合、 $m = \frac{x-S}{K}$

$x \lt S$ の場合、 $m = \frac{x+lcm-S}{K}$

となります。

中国剰余定理で求まる $x$ は、周期 $lcm$ であり、その間に唯一のものであるから、当然今回の解に不適切なものも出てくる（ $S$ 未満など）ので、その場合は、一個先の解を使えばよい（ $lcm$ を足しているのはそのためである）。

実装

提出へのリンク

2021-02-19

Codeforces Round #703 (Div. 2) D - Max Median

Codeforces 中央値二分探索決めうち二分探索

codeforces.com

問題

You are a given an array 𝑎 of length 𝑛. Find a subarray 𝑎[𝑙..𝑟] with length at least 𝑘 with the largest median. Then, output the maximum median you can get.

解説

まず「中央値がxにできるか」という判定問題をO(N)で解くことができれば、決めうち二分探索によってこの問題をO(NlogN)で解くことができます。

ここで、判定する条件を緩和し、「中央値をx以上にできるか」とします。数列aの値をx以上である場合、1, そうでない場合-1とすれば、数列の中央値がx以上になるかは、その数列の総和で判定することができるとわかります。具体的には、総和が0より大きいなら、中央値がx以上になります。

判定条件の緩和によって、数列が決まったとき「中央値をx以上にできるか」という判定問題をO(N)で解くことができました。一方で、今回の問題では長さK以上の場合を聞かれているので少し困ります。

実は今回は、累積和による連続する数列の値の和を求める計算を考えれば、取る数列の右端を決めたとき、その右端からK以上離れた累積和の最小値が和を最大化するので、その情報を前から更新しながら持てばよいとわかります。

以上のような方針で、この問題をO(NlogN)で解くことができました。

中央値の判定問題は、以上のような「値の二値化」+「二分探索における判定条件の緩和」が絡む場合があるようです。割と上位陣が高速に説いていたので典型ということなのでしょう。

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i,N)cin >> a[i];

    auto check = [&](int x) -> bool{
        vector<int> v(N);
        rep(i,N){
            v[i] = (a[i] >= x) ? 1: -1;
        }
        vector<int> c(N+1, 0);
        rep(i,N){
            c[i+1] = c[i] + v[i];
        }
        int minn = 0;
        for(int i = K; i <= N; i++){
            chmin(minn, c[i-K]);
            if(c[i]-minn > 0)return true;
        }
        return false;
    };

    int ok = 0, ng = *max_element(all(a)) + 1;
    while(ng - ok > 1){
        int mid = (ok + ng) / 2;
        (check(mid) ? ok: ng) = mid;
    }
    cout << ok << endl;
}

2021-01-10

本棚

その他商品紹介

本棚を購入しました。家が広くなりました。全人類本棚を買ってください。

本棚のリンクです。

作りはかなりしっかりしていて、組み立てるのも2人必要かもしれませんが楽しくできました。

2020-12-31

2020年を振り返る

その他

月ごとの要約

1月: 就活をしていた。
2月: 就活をしていた。
3月: 落ちる
4月: 内定を得る
5月: 2社受かる
6月: 進路決め(就活終了)
7月: 中間発表
8月:
9月:
10月:
11月: HTTFで健闘する、ハル研プロコンで2週間溶かす。マラソン沼にハマる
12月: 修論がやばくて、やばい

その他

8月〜10月の記憶がほどんどない、何をしていたんだろう
髪の毛を3月くらいから切っていなくて、大変なことに

感想

就活は大変でした。3月くらいから某ロナで面接がオンラインに移行して、戸惑いもありました。最終面接がオンラインだと、家なのにスーツを着て、重圧があり、変な感覚になります。内定が決まったときは泣きました。

競プロ的には、AtCoderでレートを200くらい上げたこと、マラソン形式に楽しく取り組めたことに満足しています。

マラソンは楽しいです。普段アルゴでは絶対に戦えないようなレベルの人たちと同じページの順位表に乗れる可能性があるというだけでワクワクしますし、評価関数を決めたり、計算量を操ったりするのも自由度が高く面白いです。問題が違っても、上位層の使っている手法が意外と共通であることに気づいてからは、自分の知ってる手法に落とし込むために問題の言い換えを考える時間も好きになりました。自明な貪欲を組んだあと、ビームを打ったら劇的に改善される瞬間は最高です。みんなもやろう、マラソンマッチ。人生とのバランスは考えた方がいい気はしますが。

来年度からは業務erになる予定ですが、マラソン、特にハル研プロコンのおかげで開発っぽいことに触れることができて、そういうコードの構造を読み解いたり、構成を考えるのも楽しいと思えたので、この気持ちを忘れずにやっていきたいと思います。

できるならマラソンっぽい案件をやってみたいという気持ちはあるのですが、まずはソフトウェアの開発の基本からという気持ちです。そもそもマラソンっぽい仕事、日本に少ないイメージで、あっても研究者レベルの人がやっていそうです。英語ができたら可能性がありますか？

あと某感染症のせいでリモートワークが増えたわけですが、自己管理能力がないことがよくわかったので入社後もかなり不安です。リモートワークしてる先輩社会人の皆さんはどのようにモチベーションを保って勤務しているのでしょう。

2020年はイレギュラーなこともありましたが、とりあえず生きて終えられそうなのでよかったです。競プロがなかったら就職先も異なっていたことでしょうし、在宅時間を耐えることもできなかったように思います。ありがとう競技プログラミング。

2020-11-02

最近AtCoderが調子が良いので分析してみた

2020/8/22以降のAtCoderにおけるパフォーマンスが上振れているので分析してみました。

コンテスト	順位	パフォ	新Rating	差分	解答	理由
ABC176	519	1789	1371	+58	緑diff 53:28	類題既知
ABC177	605	1732	1412	+41	緑diff 23:01	spf(高速素因数分解)
ABC178	864	1597	1432	+20	緑diff 34:38	マンハッタン距離は45°回転
ABC179	1120	1454	1434	+2	緑diff遅 87:21	周期苦手
ACLC1	332	1835	1481	+47	水青diff 108:00	貪欲, extGCD
ACLBC	1285	1110	1449	-32	水diff解けず	基本的なDPができません
ARC104	1270	1387	1443	-6	茶diff遅	誤読したのと次黄diffで崖
HHKB2020	571	1728	1475	+32	水diff 43:01	数え上げ
ARC105	295	2038	1545	+70	黄diff	コドフォに類題のあるゲーム
AGC048	964	661	1482	-63	☀️	😭
ARC106	891	1518	1486	+4	緑diff 64:06	構築(区間スケ問題)
ARC107	658	1698	1509	+23	緑diff 36:57	得意めな数え上げ
ABC181	366	1776	1538	+29	緑diff 46:02	添字ガチャが得意

最近緑diffがABC-Eに置かれることが多く、そこまでをある程度早く解いて甘い汁を吸っているか、同レート帯と比べて得意な数え上げを確実に仕留めているだけでした！

いかがでしたか？

ながめも

競技プログラミングについて