AGC017 B問題 Moderate Differences

atcoder.jp

【問題の概要】
が与えられる。 を両端とした要素数 個の数列を考える。
このとき、隣り合う要素の差が 以上 以下であるような数列を作ることは可能であるかを判定せよ。
未定の要素に対して、大小の制限はない。

【考察】
よく分からないので、要素数が少ないサンプルケースでとりあえず実験する。
のとき、要素の候補を考えてみる。

要素の候補を木のようにして遷移させてみると、図のようになる。
子ノードの要素は親ノードの各要素に対して、左側ではより小さく、右側ではより大きくなるように処理を施す。
ノード内で重複する数字も発生するが、まとめている。
また、より深くしてみると分かるが、左側の子ノードの一部の要素が親ノードの一部の要素以上になったり、右側の子ノードの一部の要素が親ノードの一部の要素以下になったりすることもある。

重複するノードをまとめて、ノードに最小値と最大値だけを書くと次のようになる。(同じノードにある数字は連続するので、ノードの情報をこのように変更しても問題はない。)

このサンプルケースはNOを出力するものだが、図より確かに は数列の最後の要素にならない。

この実験を一般化すると図のようになる。
子ノードに遷移するとき、
左側 : 親ノードの最小値に、最大値に
右側 : 親ノードの最小値に、最大値に
の処理を行う。

実験してみると、同じ深さのノード間で重複する部分があるように見て取れたが、各ノードに上記の処理をしていると解釈すると、 と の加算・減算の順序が違うだけなので、同じ深さのノードの重複部分はまとめることができ、パスカルの三角形のようなグラフになる。

よって、隣り合う要素の条件と最初の要素から、最後の要素のあり得る範囲が分かる。
深さ のノード数は 個あり、深さ の 番目ノードに関して、
最小値 :
最大値 :
となる。
(ノードを左から見ていくと、最小値に関しては、

最大値に関しては、

となっていて、ここから類推もできる。)
判定にはこれを使う。
各 に対して、その範囲に最後の要素が含まれているかを判定すれば、問題の数列を作ることが可能か判定できる。
計算量は になる。

コードにすると簡単だが、考察が疲れる。
最初は、 と の大小関係をなんとなく swap して固定していたが、別に必要なかった。
横着してすべて 64bit 整数にしてしまった。

#include <iostream>
using namespace std;

int main(){
    long long N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    // 深さN-1のノードに対して判定処理を行う。
    for(long long i = 0; i < N; ++i){
        // lower_bound
        long long lb = A + i * C + (i - (N - 1)) * D;
        // upper_bound
        long long ub = A + (i - (N - 1)) * C + i * D;
        if(lb <= B && B <= ub){
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
}

【所感】
算数ゲーできません。
5年ぶりくらいに勉強してるのでﾂﾗｲ。
大学入る前は辛うじて数学力あったかもしれないが、その時期ならすぐに解けたりするんだろうか。
あんまり変わらない気もするけど。
数学力はもしかしたら中学生の方があるか。
知識はないけど、意欲は今よりあった気がする。
意欲は何にも代えがたいものだと思うので。
やる気なさ過ぎて動画つけながらやってたら、これでほとんど一日が溶けた。