u_sho競プロぶろぐ

21歳。みゃーくぴとぅ。ゆる~く続けますたぶん。  デザイン変えました(2019/2/25)これでいきます

AtCoder Beginner Contest 119 (ABC119)

みなさん,おはこんばんにちは,u_shoですにゃ
MacBook Airの記事をかいていたらABCの記事こんな時間になっちまったよ(昼だが(夜だったので))
u-sho.hatenablog.com

実は前回のABC118にも出ていたのだけど,3か月ぶりに競プロしてみたら爆死したからそっちの記事は書かないよ
あと,今回でなんと
AtCoder緑になりました
いぇ~いv(棒)
いえ,爆死しなければ上がれることは分かっていたので。
ついでに言えば,最高パフォも1415に更新しました(実はこっちの方が嬉しい)。

今回の勝因は,ABC史上2番目に正答率の低かったC問題に5分で見切りをつけたことですね。
わからないなら(もしくは実装に時間がかかるなら)一旦とばす。これ大事
ではでは,問題の方に

A - Still TBD

A問題は日付がyyyy/mm/ddの形で渡されるので,それが平成(Heisei)か次の年号(To Be Determined)か(なぜまだ発表されていないんだ)を判別するやつです。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string S;
    cin>>S;
    if(S<="2019/04/30") cout<<"Heisei\n";
    else cout<<"TBD\n";
    return 0;
}

string型の比較演算はまず長さで比較して,次に辞書順で比較します。
今回のケースでは長さはすべて等しく,また日付は辞書順ですので,これでOKです。
制約を見ている人は,mの部分が4以下かどうかだけ判定すればよかったみたいですね←爆死のもと

B - Digital Gifts

N人から x JPY(日本円) か x BTC(ビットコイン) のお年玉をもらえるので(貰いたい),
それが全部で何円か,合わせてみましょう。という,問題だけ見ると小学校の算数。
1BTCあたり380000円なので,それにをもとに計算すると,こんな感じ

#include <bits/stdc++.h>
using namespace std;

int main(){
    double N, x, ans=0.0;
    string u;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> x >> u;
        if(u=="JPY") ans += x;
        else ans += x*380000.0;
    }
    cout << ans << endl;
    return 0;
}

今回は有効数字8桁だったので,double型なら十分です。
(参考)浮動小数点数型と誤差
出力もcoutのデフォルトでOKです。不安ならprintfを使いましょう。

C - Synthetic Kadomatsu

l[i](3≦iN)の長さのN本の竹に対して,魔法を使ってA,B,Cの長さの3本の長さの竹を錬成しましょう。
えー,個人的にはむずかった。発想としては,各々の竹にに関して,

  1. Aに使う
  2. Bに使う
  3. Cに使う
  4. 使わない

の4通りがあるので,4^N(N≦8)で全探索すれば解けます。

なんか,数学1Aの「場合の数」で、
『通し番号のついた8個くらいのボールをそれぞれ名前の付いた3個くらいの箱に入れるやり方は何通り?』
っていう問題と発想は似てると思うんですよ。

僕はこれと類似の発想を見る度に天才だと思っているし,この発想は苦手というか穴ですが、
典型ではあるので,他の人が解けていないのはちょっと謎に思いました。
みんな私と同じところが苦手なのでしょうか・・・
ともかく典型は解けるようになりたいと思ったのですよ。

D - Lazy Faith

1本の道があって,一方の端からs[i](1≦iA)の距離に神社(shrine),t[i](1≦iB)の距離に寺(temple)があり,
君がx[i](1≦iQ)の場所にいるとき,神社と寺を少なくとも1回ずつ訪れるには最短どのくらい歩けばいい?

こういう問題が出たら,とりあえずソートします。*1
んで,こういうときは実際に想像します。

  1. 右隣のお家に回覧板を回して,その右隣のお家にも何か差し入れするとき→→
  2. 右隣のお家に回覧板を回して,左隣のお家には何か差し入れするとき  →←←
  3. 左隣のお家に   〃   ,右隣のお家には   〃    とき  ←→→
  4. 左隣のお家に回覧板を回して,その左隣のお家にも何か差し入れするとき←←

というパターンがあって,回覧板(神社)と差し入れ(寺)はこの場合区別しなくてもよいので,これで以上になります。 

これを4パターンをそれぞれのxについて全探索すればよいわけですが,
A,B,Q≦1e5なので,『それぞれのxについてO(log(A+B)程度で解く必要がある』ことが分かります。
これが†真の制約†です。

全探索自体は4パターンしかないので,それぞれのxがソート済みのsとtのそれぞれ何番目にあるかをO(log(A+B)程度で求めればよいわけです。
それぞれのxがソート済みのstのそれぞれ何番目にあるかを求めるのといえば,
upper_bound()やlower_bound()がお馴染みですが,
奇しくもそれらの計算量はO(logn)なので(2分探索するため),なんと†真の制約†をクリアできました。やったね☆

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A), t(B), x(Q);
    for(ll i=0LL; i<A; i++){
        cin >> s[i];
    }
    for(ll i=0LL; i<B; i++){
        cin >> t[i];
    }
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    for(ll i=0LL; i<Q; i++){
        cin >> x[i];
    }

    for(int i=0; i<Q; i++){
        ll ans=0LL;
        decltype(s)::iterator its = upper_bound(s.begin(), s.end(), x[i]);
        decltype(t)::iterator itt = upper_bound(t.begin(), t.end(), x[i]);

        ll sl = *its, tl = *itt;
        if(its==s.end())sl=3e10;
        if(itt==t.end())tl=3e10;

        ll ss = *(its-1), ts = *(itt-1);
        if(its==s.begin())ss=-3e10;
        if(itt==t.begin())ts=-3e10;

        if( sl < tl ){
            ans = min( x[i] + sl - 2*ts, -x[i] + 2*sl - ts );
            ans = min( ans, tl - x[i] );
            ans = min( ans, x[i] - min(ss,ts) );
        }else{
            ans = min( x[i] + tl - 2*ss, -x[i] + 2*tl - ss );
            ans = min( ans, sl - x[i] );
            ans = min( ans, x[i] - min(ss,ts) );
        }
        cout << ans << endl;
    }

    return 0;
}

こぼれ話

手元でg++コンパイルして提出前に確認できたから
イテレータ関連でCEやREを投げなかったのが嬉しかったかな。
やっぱり手元に実行環境は作っておくもんだね。
そういえば今回はレッツノートで参戦しました。

*1:ソートの計算量は配列の大きさnについてO(n log n)なので,そこだけ確認しましょう。