n度あることはn+1度ある

憶測が多いブログなので鵜呑みにしないこと

ABC113 所感

お疲れ様です。beta版がめちゃくちゃ重いコンテストでした。最近あまりこちらにモチベーションがないのと、これの影響であまり集中してできませんでした(言い訳)

A - Discount Fare

半額になるほうを半額にして出力

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x,y; cin>>x>>y;
    cout<<x+y/2;
}

B - Palace

差分の最小値とその要素番号を保存して、入力毎に比較します。最小値だけでよい場合は、全てのデータを保存する必要がありません。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,t,a; cin>>n>>t>>a;
    double min = 1e10;
    double ele =0;
    for(int i=0;i<n;i++){
        double h; cin>>h;
        double nc=(double)t-h*0.006;
        if(fabs(a-nc)<min){
            min=fabs(a-nc);
            ele=i+1;
            
        }
    }
    cout<<ele;
}

C - ID

入力した市iの属する県番号と誕生年をvectorに保存して、誕生年でソートしたコピーを作成します。
このコピーを基に、1つの年には最大で1つの市が生まれていることを利用して、年をキーにしたmapに県の番号と、何番目に生まれたかを記録しています。(あとで気が付きましたが、年をキーとした県番号を割り出すmapは必要ありません)その県に対して何番目に生まれたかというのは、県別にカウンタを保持して実装しています。
最初の実装として県別の配列を作成し、それらをソートしてfindを使用して割り出していたのですが、TLEしたのでmapにて記録しています。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m; cin>>n>>m;
    vector<pair<int,int>> v;
    for(int i=0;i<m;i++){
        int p,y; cin>>p>>y;
        v.push_back(pair<int,int>(p,y));
    }
    vector<pair<int,int>>cv = v;
    sort(begin(cv),end(cv),[](auto x, auto y){return x.second<y.second;});
    map<int,int> ken;
    map<int,int> num;
    vector<int> el(n+1,1);
    for(auto x:cv){
        ken[x.second]=x.first;
        num[x.second]=el[x.first];
        el[x.first]++;
    }
    for(auto x:v){
        printf("%06d%06d\n",ken[x.second],num[x.second]);
    }
}

D - Number of Amidakuji

解けませんでした。DPかなという予想です。明日できたら更新します。
(2018/11/5 更新) 別記事にて解説しました。よろしければそちらを参照してください。

everydaytekitou.hatenablog.com

総括

前回よりはパフォーマンスが絶対落ちていると思いますが、C問をちゃんと解けたので良かったです。サーバーが非常に重かったことが残念でした。