fal_rnd_log

fal_rnd

Nafmo、家を買う。 / 解説

問題ページ:

初出: Nafmo、家を買う。 | OJ
リメイク: https://hoj.hamako-ths.ed.jp/onlinejudge/problems/791
(リンク切れてたら教えてください)

はじめに

拙作の解説です
これをgithubに置いておくのはおかしい(唐突)
あと微追記(2017/12/02)

方向性

  • 家{ サイズ, お値段 } -> pair?      マップ? <-AC
  • Nafmo君の希望サイズに一番近い -> 何かしらのデータ構造に突っ込んで検索?

クエリ数:O( q )
* vectorで管理してforで検索
->追加:O( 1 ) 検索:O( q )  ->O( q2 )
* vectorで管理、クエリ2の度にソートからの二分探索 ->追加:O( 1 ) ソート:O( qlogq ) 検索:O( logq )
->O( q( qlogq+logq ) )
->O( q2logq )              クエリ1、遅くなるんですね(書きながら気づく)

map とは

std::map(c++、unorderedでない)とは、 (JavaではTreeMap(NavigableMap))
キーとそれに対応する値のpairを要素とするコンテナクラスで、キーを指定して値を高速に取り出せます。
内部で二分探索木を使っているので、(N=中の要素数)挿入:O( logN )、検索:O( logN )で操作でき、格納されている要素は常にソート済みになります。
c++ std::map - Google 検索 まあ私がしゃべるよりググってもらったほうが

続・方向性

クエリ数:O( q )
* map<size,value>で管理 ->追加:O( logq ) 検索:O( logq )
->O( qlogq )
->間に合う!

mapはキーの重複が出来ない
...同じサイズの家の情報でお高いほうは持ってる意味が無いので安い方を保持するようにすれば解決  

(検索キー"以下"の要素の取得、出来ましたか?)

Writer解

C++

#include <iostream>
#include <map>
using namespace std;
 
#define REP(i,n)   for(int i=0;i<n;++i)
#define FOR(i,l,r) for(int i=l;i<=r;++i)
 
using ll=long long;
using ull=unsigned long long;
 
const char en='\n';
 
int main(){
    cin.tie();
    ios::sync_with_stdio(false);
 
    map<ll,ll> m;
    ll r=0,mod=1000000007;

    int q;cin>>q;
    REP(i,q){
        int sw;cin>>sw;
        switch(sw){
            case 1:
                ll a,b;cin>>a>>b;
                m[a]=(m[a]==0)?b:min(m[a],b);
                break;
            case 2:
                ll v;cin>>v;
                auto high=m.lower_bound(v),low=high;
                if(low!=m.begin())--low;
                ll h=(high==m.end())?9223372036854775807ll:abs(high->first-v);
                ll l=abs(low->first-v);
                if(h>l){
                    r+=low->second;
                }else if(h<l){
                    r+=high->second;
                }else{
                    r+=min(high->second,low->second);
                }
                r%=mod;
                break;
        }
    }
    cout<<r<<en;
}

Java(8)(HOJのみ)

import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;
 
class Main{
        static final Scanner s=new Scanner(System.in);
        public static void main(String[]$){
                TreeMap<Long,Integer> tmap=new TreeMap<>();
                long r=0,mod=1000000007;
                for(int q=s.nextInt();q>0;q--){
                        switch(s.next()){
                        case "1":
                                tmap.merge(s.nextLong(),s.nextInt(),Math::min);
                                break;
                        case "2":
                                long v=s.nextLong();
                                Entry<Long,Integer> high=tmap.ceilingEntry(v),low=tmap.floorEntry(v);
                                if(dist(v,high)>dist(v,low)){
                                        r+=low.getValue();
                                }else if(dist(v,high)<dist(v,low)){
                                        r+=high.getValue();
                                }else{
                                        r+=Math.min(high.getValue(),low.getValue());
                                }
                                r%=mod;
                                break;
                        }
                }
                System.out.println(r);
        }
        private static long dist(long v,Entry<Long,Integer> e){
                return e==null?Long.MAX_VALUE:Math.abs(v-e.getKey());
        }
}

入力周りとか 追加のところとか キー以下を直に取れるところとかスマートですね(布教)

















おま○け(あとがき)

初投稿です。(コンテスト問題)
ゆるふわな解説となっております。   オーダーの辺りとかちょっと怪しいし定数倍を考慮してないしで色々不安ですけどまあなんとかなるでしょう(罠)
ご意見、ご感想はTwitterまで