AtCoder 生活110日目

前回

#110日目
今日は、灰色を2問と茶色2問と緑色1問を解きました。

|問題|難易度|自力で解けた|かかった時間|
|:-:|:-:|:-:|---|---|
|ABC115|C|✕|33分16秒|
|ARC106|A|✕|42分25秒|
|ARC099|C|◯|33分56秒|
|CODE FESTIVAL 2017 qual B|B|◯|12分|
|ABC178|D|✕|189分26秒|

##ABC115_C

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    ll n,k;
    cin >> n >> k;
    vector<ll> h(n);
    rep(i,n)cin >> h[i];
    sort(h.begin(),h.end());
    ll ans = INF;
    rep(i,n-k+1){
        ans = min(ans,(h[i + k - 1] - h[i]));
    }
    cout << ans << endl;
}

解くのにかかった時間：33分16秒
感想：2パターンしか考えてなくて暫く悩んだ。

##ARC106_A

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    ll n;
    cin >> n;
    ll x = 1,y = 1;
    for(int i = 1;i <= 37;i++){
        y = 1;
        x *= 3;
        for(int j = 1;j <= 25;j++){
            y *= 5;
            if(x + y == n){
                cout << i << " " << j << endl;
                return 0;
            }
            else if((x + y) > n) break;
        }
    }
    cout << -1 << endl;
}

解くのにかかった時間：42分25秒
感想：乗数の全探索難しい

##ABC094_C

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    int n;
    cin >> n;
    vector<pii> x(n);
    vector<int> y(n);
    rep(i,n){
        int a;
        cin >> a;
        y[i] = a;
        x[i].first = a;
        x[i].second = i;
    }
    sort(x.begin(),x.end());
    int a = x[n/2 - 1].second;
    int b = x[n/2].second;
    rep(i,n){
        if(y[i] <= y[a])cout << y[b] << endl;
        else cout << y[a] << endl;
    }
}

解くのにかかった時間：33分56秒

##CODE FESTIVAL 2017 qual B_B

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i,n)cin >> d[i];
    int m;
    cin >> m;
    vector<int> t(m);
    rep(i,n) cin >> t[i];
    sort(d.begin(),d.end());
    sort(t.begin(),t.end());
    int c = 0;
    int j = 0;
    rep(i,n){
        if(d[i] == t[j]){
            c++;
            j++;
        }
    }
    if(c == m)cout << "YES" << endl;
    else cout << "NO" << endl;
}

解くのにかかった時間：12分

##ABC178_D

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;
const int MOD = 1e9+7;

int main(){
    int s,a[2010];
    cin >> s;
    a[0] = 1,a[1] = a[2] = 0;
    for(int i = 3;i <= s ;i++){
        a[i] = (a[i-3] + a[i-1])%MOD;
    }
    cout << a[s] << endl;
}

解くのにかかった時間：189分26秒
感想：動的計画法の把握と式の意味を理解するのが困難だった。

###最後に
何故か灰色より茶色の方が今日は簡単だった。