自分ができないものを敷き詰めたような問題セットだった。これは圧倒的成長のチャンスですね(削れるレートから目をそらしながら)。

ところで、ネタが多い問題で凄くニンマリしたのでそこについても語らせてください。

A Poor

setを使うのが速いです。

A,B,Cをそれぞれsetに挿入します。

setは重複した要素はカウントしない性質を利用すると、3つ組が「かわいそう」な時、必ずsetのサイズは2になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    set<int> s;
    int a,b,c;
    cin >> a >> b >> c;
    s.insert(a);
    s.insert(b);
    s.insert(c);

    if (s.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

提出 #10128785 - AtCoder Beginner Contest 155

B Papers, Please

B - Papers, Please

有名な入国審査ゲーのタイトルまんまでニンマリせざるをえない。ゲームオタクにはたまらない。

アルストツカに栄光あれ。

それぞれの整数について前から1つずつ見ていけば良いです。

判定はこんな感じ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];

    REP(i,N) {
        if ( A[i]%2 == 0 ) {
            if (!((A[i] % 3 == 0) || (A[i] % 5 == 0))) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}

提出 #10128785 - AtCoder Beginner Contest 155

めちゃんこ面白いので良ければ・・・

Steam：Papers, Please

C Poll

C - Poll

これがTLE解なの素直にワカンね〜〜〜！！！！！！

詳しい方いたら教えてください・・・

(TLE) 提出 #10143486 - AtCoder Beginner Contest 155

解き方。

1. ある文字列について種類毎に何回書かれたかカウント ($\mathcal{O}(N)$)
1. カウント終了後、文字列の種類について前から見ていって、書かれた回数が最も多い文字列の書かれた回数を取得(最悪$\mathcal{O}(N)$)
1. 再度文字列の種類について前から見ていって、書かれた回数が最も多い文字列なら配列にpushする。
1. 配列をソートして前から出力

count()を使用したら何故かTLE解になったため使わない方向で・・・

コンテスト後に書き直したんですけど、ちゃんと書けばネストかなり浅いコードになりますね・・・

map,setをイテレータで回す癖は付けたい。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    // 文字列の種類を取得
    set<string> st(ALL(S));

    // mapの初期化
    map<string,int> mp;
    for(const auto& it:st) mp.insert(make_pair(it,0));

    // 文字列のカウント
    for(const auto& it_s:S) mp[it_s]++;

    // 最も書かれた回数の多い数を取得
    int maxi = 0;
    for(const auto& it:mp) chmax(maxi,it.second);

    // 最も書かれた回数の多い文字列なら出力(mapはキー昇順になる様にソートされているので初めから辞書順になっている。)
    for(const auto& it: mp) if(maxi == it.second) cout << it.first << endl;

    return 0;
}

提出 #10171842 - AtCoder Beginner Contest 155

ちなみに入力例3ですが、

1
2
3
4
5
6
7
8


7
bass
bass
kick
kick
bass
kick
kick

多分これが元ネタでしょう。

BMS楽曲の一つでチュウニズム、太鼓、maimaiいろんな音ゲーに移植されています。僕も大好きです。

(321) (BOF2013) B.B.K.K.B.K.K. (BGA) - YouTube

Lets bass kick!

D - Pairs

無理〜〜〜〜！！！

マッチングアプリの方も無理です・・・

雑に考えると、$ N * ( N-1 )/2$ の組み合わせを全て配列などに格納して前から見てけばいいんじゃないかって思います。

しかし、格納する場所もないし時間もないので、K番目の値を単純に求めるアプローチはうまくいきません。なので、

まずは求めたい答え、K番目に小さい値をxとして、そのxを求めることを考えます。

Aの要素は問題文から-1e9~1e9範囲を取ります。

その中から二つの要素を選んで積を取るのでxの範囲は大体、$ -10^{18} $ ~ $10^{18}$であることが分かりますね。

xを決め打ちして、それがK番目かどうかを調べようとします。

前から愚直にxを見ていった場合、$ 2 * 10^{18}$ 回ほどの計算回数になります。

これは絶対間に合わないです。

しかし、よく考えてみると、xが大きければ大きいほど、Kは大きくなります。

したがって、求めたいxについて単調性があると言えるので、二分探索が有効です。

これで、計算回数が、$ 2 * 10^{18}$回から$ \log (2 * 10^{18})$回に落ちました。

ところで、二分探索をする以上、midが何番目かと言うクエリに答える必要があります。

midがk番目であるというクエリをcnt(mid)(=k)として、

cnt(mid)がK以上※1なら$right = mid$,cnt(mid)がKよりも小さいなら$left = mid$に範囲を変えていく必要があるからです。

※1 cnt(mid)がK以上と書かれているのは$ cnt(mid)+1 $が実際のmidの順位だからです。$cnt(mid) \geq K$ ならば $ cnt(mid)+1 > K$ です。

話を戻して,midがk番目であるというクエリは、雑に書くと$\mathcal{O}(N^{2})$です。

しかし、Aが予めソートされているなら、積を作るペアの片方を固定すると、ペアのもう片方は単調性を持ちます。

よって、ペアの片方を固定(=前から全部見る)して、もう片方は二分探索をすることで、midよりも小さいペアの数を $\mathcal{O}(N\log N)$で答えることができます。

二分探索 -> クエリに答えるを繰り返して答えにありつけば終わりです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


// nC2を求める関数
ll pair_conb(ll n) {
    return n*(n-1)/2;
}


double getTime(chrono::system_clock::time_point st,chrono::system_clock::time_point ed) {
    return static_cast<double>(chrono::duration_cast<chrono::microseconds>(ed - st).count() / 1000.0);
}

void solve() {
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];

    sort(ALL(A));
    // binary search (K番目の値である様なxを探す)
    // お気持ち的に NC2ループの二個目のforを二分探索にしてNlogNに計算量を落としおいる。
    ll left = -2e18, right = 2e18;
    while (right - left > 1) {
        // cnt はx(mid)よりも小さい数のカウンタ
        ll mid = (left+right)/2, cnt = 0;

        REP(i,N) {
            // 普通に書いたらO(N^2)だが、xを決め打ちするのと、Aの単調性を利用することでO(NlogN)に落とす。
            // 片方をA[i]と決定して,iより先にある値mで、A[i]*A[m] < x 以下である様な最大のmを二分探索で求める
            ll l = i, r = N;
            while ( r - l > 1) {
                ll m = (l+r)/2;
                if (A[i] >= 0) (A[i] * A[m] < mid) ? l = m : r = m;
                else (A[i] * A[m] < mid) ? r = m : l = m;

            }
            // l を足す(m) -> (r-l) == 0なら r = lなので自明
            // (r-l) == 1 なら m = (l+r)/2;から切り捨てられるので結局 (l+l)/2と同じなので l を使用する
            cnt += (A[i] >= 0) ? l - i : N - r;

        }
        // cnt が小さい -> xが小さい
        ( cnt < K) ? left = mid : right = mid;
    }
    cout << left << endl;
}
int main() {
    auto st = chrono::system_clock::now();
    solve();
    auto ed = chrono::system_clock::now();
    cerr << "end with: " << getTime(st,ed) << "ms" << endl;

    return 0;
}

提出 #10190235 - AtCoder Beginner Contest 155

E- Payment

E - Payment

二次元配列になるDPほんまわからん・・・

入力されたNのある桁について考えると、取れる行動は二つ -> その桁の枚数分払う。 -> その一個上の桁の値を増やしてお釣りを貰う。

上から見ていけばDPで解けそう。

コード書く前に遷移式を書いてみる。

dp[i][over]

上位i桁目まで見て、使用する紙幣の枚数が最小となる時の枚数。 overがtrueならi桁目を一枚余分に支払って、i+1桁目でお釣りを貰う予定。

とする。

$dp[i+1][false]$についてはこの二つから遷移できる

$dp[i][false]+N[i]$ i桁目をぴったり払ってて、今回もぴったり払う場合
$dp[i][true]+10-N[i]$ i桁目を1枚余分に払ってたので、今回はお釣りを取る場合

この二つの小さい方を取れば良い。

$dp[i+1][true]$についてはこの二つから遷移できる

$dp[i][false]+N[i]+1$ i桁目をぴったり払ってて、今回は下の桁のために一枚多く払う場合
$dp[i][true]+10-(N[i]+1)$ i桁目を1枚余分に払ってたので、今回はお釣りを取るが、また余分に払うため、お釣りを1枚残す場合

この二つの小さい方を取れば良い。

また初期値は$dp[0][true] = 1$で他は全て0となる

あとは順次計算していけば終わり

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    string N;
    cin >> N;
    vector<vector<int>> dp(N.size()+1,vector<int>(2,0));
    dp[0][1] = 1;
    FOR(i,1,N.size()+1) {
        int Ni = N[i-1] - '0';
        dp[i][0] = min(dp[i-1][0]+Ni,dp[i-1][1]+10-Ni);
        dp[i][1] = min(dp[i-1][0]+Ni+1,dp[i-1][1]+10-Ni-1);
    }
    cout << dp[N.size()][0] << endl;
    return 0;
}

提出 #10226643 - AtCoder Beginner Contest 155

感想

辛い！！！！！！！！！