FHC 2020 Round1 A-Perimetric

Round1はA1とBを解いて通過でした.

リンク

https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/problems/A1

問題概要

2次元平面上に左下の点が, 右上の点がの長方形が個与えられる.

1からNの各について, を次のように定める. この時, をで割った余りを求めよ.

• 1からi番目の長方形を重ねて出来る図形の外周の長さをとする.

制約

A1

全てのiに対しては一定　

A2

A3

解法

まずはA1を解く時に使った基本的な考え方から.

出来上がる図形は一見複雑だが, 横の長さに注目するとこれは簡単に求められることが分かる.

区間の重なりだけ見れば良い

従って残りは長方形の縦の辺について注目すれば良い. A1ではの制約が小さいため左から見ていき毎回前20個程度を調べれば求める周長が得られる.

// A1
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

constexpr ll mod=1e9+7;

ll solve(){
    int n,k,w; cin >> n >> k >> w;
    vector<ll> l(n),h(n);
    for(int i=0;i<k;i++){
        cin >> l[i];
    }
    ll a,b,c,d; cin >> a >> b >> c >> d;
    for(int i=k;i<n;i++){
        l[i]=(a*l[i-2]+b*l[i-1]+c)%d+1;
    }
    for(int i=0;i<k;i++){
        cin >> h[i];
    }
    cin >> a >> b >> c >> d;
    for(int i=k;i<n;i++){
        h[i]=(a*h[i-2]+b*h[i-1]+c)%d+1;
    }
    ll presum=0; // 過去の横幅の和
    ll sum=0; // ここに縦の差分を足し引き
    ll res=1;
    int lastid=0; // 見ている連結成分の左端のindex
    vector<pair<int,pair<ll,ll>>> v;
    // 長方形の右端の座標, H\_{i}の大きさ, 他の長方形にどれだけその辺が被っているか 
    for(int i=0;i<n;i++){
        if(i&&l[i-1]+w<l[i]){ // 見ている連結成分の更新
            presum+=(l[i-1]+w-l[lastid])*2;
            lastid=i;
        }
        if(i==0){
            sum+=2*h[i];
        }
        else{
            // 長方形を追加した時に左側の辺がどれだけの長さ使えるか計算
            ll mx=0;
            for(int j=i-1;j>=0;j--){
                if(l[j]+w>=l[i]){
                    mx=max(mx,h[j]);
                }
                else break;
            }
            if(mx<h[i]){
                sum+=h[i]-mx;
            }
            // 長方形を新しく追加したことによる更新
            for(int j=(int)(v.size())-1;j>=0;j--){
                if(l[i]<=v[j].first){
                    ll mi=min(v[j].second.first,h[i]);
                    mi=max(mi,v[j].second.second);
                    sum-=mi-v[j].second.second;
                    v[j].second.second=mi;
                }
                else break;
            }
            sum+=h[i];
        }
        ll tmp=presum+(l[i]+w-l[lastid])*2+sum;
        (res*=tmp%mod)%=mod;
        v.push_back(make_pair(l[i]+w,make_pair(h[i],0)));
    }
    return res;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    freopen("perimetric_chapter_1_input.txt", "r", stdin);
    freopen("Aoutput.txt", "w", stdout);
    int q; cin >> q;
    for(int i=1;i<=q;i++){
        printf("Case #%d: %lld\n",i,solve());
    }
}

長方形を一個追加した時に値を足し引きしていく考え方は同じでA2も解くことができる.

下図のように斜線を引いた長方形を追加した状況を考える. 今追加した長方形と共通区間が存在した場合, 赤矢印の分だけ今の総和から引く.

ここで重要なのが高さは単調減少なので図中の緑矢印の部分が今後の総和に関与する事はない. 従って下図のように区間のマージをすることができる. 長方形の横の長さについても同様に値を足し引きする.

// A2
ll solve(){
    /*
   入力受け取り
   */
    set<pair<ll,ll>> st;
    st.insert({-1e15,-1e15}); st.insert({1e15,1e15});
    for(int i=0;i<n;i++){
        now+=(w[i]+h[i])*2;
        auto it=st.lower_bound({l[i],l[i]});
        it--;
        ll L=l[i],R=l[i]+w[i];
        for(int j=0;j<2;j++){
            while(it!=st.end() && !(it->second<l[i]) && !(it->first>l[i]+w[i])){
                L=min(L,it->first); R=max(R,it->second);
                now-=h[i]*2;
                now-=(min(it->second,l[i]+w[i])-max(it->first,l[i]))*2;
                it=st.erase(it);
            }
            it++;
            if(it==st.end())break;
        }
        st.insert({L,R});
        now%=mod;
        (res*=now)%=mod;
    }
    if(res<0)res+=mod;
    return res;
}

A3は気合いでえいっ！(実装ばーん)

// A3
ll solve(){
    /*
   入力受け取り
   */
    ll res=1, now=0;
    set<pair<pair<ll,ll>,ll>> st;
    st.insert({{0,1e15},0});
    for(int i=0;i<n;i++){
        ll L=l[i],R=l[i]+w[i];
        ll s=-1,t=-1,b=-1;
        auto it=st.lower_bound({{L,-1},-1});
        it--;
        while(it!=st.end()){
            if(it->first.second<=L){
                s=b=it->second;
                it++;
                continue;
            }
            auto p=*it;
            it=st.erase(it);
            if(p.first.first<L){
                s=b=p.second;
                st.insert({{p.first.first,L},p.second});
                p.first.first=L;
            }
            now-=abs(b-p.second);
            b=p.second;
            if(p.second>0)now-=2*(min(p.first.second,R)-p.first.first);
            if(p.first.second>R){
                t=p.second;
                st.insert({{R,p.first.second},p.second});
                break;
            }
        }
        st.insert({{L,R},h[i]});
        now+=(R-L)*2+abs(h[i]-s)+abs(h[i]-t);;
        now%=mod;
        (res*=now)%=mod;
    }
    if(res<0)res+=mod;
    return res;
}