AtCoder Beginner Contest 294 参加記 - 茶処・まっちゃら亭の一休みばしょ

こんにちは、またやってきました、ABCのお時間です。
今回はかなり楽しかったですね...問題も解答も！！！

※あ、この記事は C++ only です

結果

今回は ABCD 20分以内早解き、E 50分以内でした。パフォは 1177 と、なかなか私にとって好成績でした。
レートは 852 (前回比+43) に上がりました。よしよし...

実は、E 本番 AC は、この回が初めてです。あまりにも突然すぎたので、私はAC直後に素直に喜べませんでした...すみません

解説

※思考ふわふわ解説になっています。厳密に解説していないので正当性もふわふわなので、「ふ～ん抹茶ってこんな美味いんだ～」程度で見てください。

A

問題はこちら。

まぁ普通に、for文+if文で頑張りましょうって話です。
偶数かどうかは $A_i\bmod 2=0$ かどうか判定することで実装できます。

Submissionは以下のようになります。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<P>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
ll siz(T& a){return (ll)a.size();}

int main(void){
    int n; cin >> n;
    rep(i,n){
        int a; cin >> a;
        if(a%2 == 0) cout << a << " ";
    }
}

B

問題はこちら。

まぁこれも、普通にやるだけです。
$H$ 行 $W$ 列のグリッドを入力して、そこからアスキーコードで頑張るという感じです。

アスキーコードとは、端的に言うと各文字に振られる番号のことです。逆にその番号が振られた文字をアスキー文字と言います。
例えば a には $97$ 、b には $98$ の番号が振られています。これは小文字だけでなく大文字でも、なんなら数字、記号などにも同じように振られています。

つまりどういうことかというと、 $A_{i,j}$ が . でない場合は、答えは $(A_{i,j}-1)+65(=X)$ というアスキーコードをアスキー文字に直したものです。ここで 65 という数値はアスキー文字 A に対応しています。わからない場合は、実験してみるとわかるかと思われます。

アスキーコードからアスキー文字に変換しますが、これは int 型を char 型に変換する※ことでできます。

Submissionは以下のようになります (ll siz=...から上は同じなので省略しています)。

int main(void){
    int h,w; cin >> h >> w;
    rep(i,h){
        rep(j,w){
            int a; cin >> a;
            if(a == 0) cout << ".";
            else cout << char(a+'A'-1);
        }
        cout << "\n";
    }
}

※この変換を一般には型キャストと呼ばれるようです

C

問題はこちら。

最初は「おっ...！？」となりましたが、問題を要約するとこういうことです。

長さ $N+M$ の数列 $C=(A_1,A_2,...,A_N,B_1,B_2,...,B_M)$ を昇順にソートを行う。各 $A_1,A_2,...,A_N$ と $B_1,B_2,...,B_M$ についてそれぞれの要素が $C$ の何番目にある？

この問題では、全探索をするとざっくり $(N+M)^2$ 回くらいなので、間に合いません。つまりこの「何番目にあるか？」の判定を高速化する必要があります。
制約より、 $C$ の要素は相異なるため答えはただ $1$ 通りに定まります。よってこれは連想配列などを用いて実装することができます。

連想配列 $mp$ として、キーを要素、値をその index 、すなわち mp[C_i] = i $(1\le i\le N+M)$ として記録することで、「何番目にあるか」を $log(N+M)$ で判定できるので、全体で $(N+M)log(N+M)$ で実装が可能です。

(すみませんtex記法がバグるのでオーダー記法で書かれていませんが、そういうことです)

Submissionは以下のようになります。

int main(void){
    int n,m; cin >> n >> m;
    vector<int> A(n),B(m),C;
    map<ll,ll> mp;
    rep(i,n) cin >> A[i];
    rep(i,m) cin >> B[i];
 
    rep(i,n) C.push_back(A[i]);
    rep(i,m) C.push_back(B[i]);
 
    sort(all(C));
    rep(i,n+m) mp[C[i]] = i;
 
    rep(i,n) cout << mp[A[i]]+1 << " ";
    cout << endl;
    rep(i,m) cout << mp[B[i]]+1 << " ";
 
}

(読みにくかったらすいません)

D

問題はこちら。

うっ、ってなった問題です。特に日本語がむずかったので、何度も読み直してなんとか通りました。
私は次のようなキュー(set)を作って解きました。

$st\ := N$ 人の呼ばれていない人の番号管理
$Q\ :=$ 受付に行ってないけど呼ばれた人の番号管理

問題を見た感じ、次のようなことが高速にできるやつを探してくればいいと思いました。

数値 $x$ をキューから消去する
ソート済の配列から最初の要素を取り出す

う～ん...と思ってると、天から set が舞い降りてきたのです。そう、set は順序付き集合であるため、数値を挿入するときに自動的にソートをしてくれるのです。しかも、計算量は要素数 $n$ として $logn$ です。さらに set には erase 関数で該当する数値を高速に消去することができます。

3種類目のイベントにおいて「最も小さい番号の人が呼ばれる」ということは、ソート済のキューのうち最初の要素を取り出す、すなわち set に対するイテレータ begin を取り出すことで実装可能です。

さらに「人 $x$ が呼ばれる」というのは、キュー $Q$ から数値 $x$ を消去することに相応します。
さらにさらに「受付に呼ばれていない人のうち、最も小さい番号の人が受付に呼ばれる」というのは、キュー st から *st.begin() ※を消去することに相応します。

Submissionは以下になります。

int main(void){
    int n,q; cin >> n >> q;
    set<int> st,seen,Q;
    rep(i,n) st.insert(i+1);
 
    rep(i,q){
        int t; cin >> t;
        if(t == 1){
            Q.insert(*st.begin());
            st.erase(*st.begin());
        }
        else if(t == 2){
            int x; cin >> x;
            Q.erase(x);
            seen.insert(x);
        } else {
            cout << *Q.begin() << endl;
        }
    }
}

※ * は、イテレータが指し示す要素のことを表します
※ seen というキューがありますが、関係ありません。最初、受付に行った人のキューとして書きましたが、st が代わりにやってくれているのでいらなかったためです。

E

問題はこちら。

一瞬、ふへ？になった問題です。
でも、考えてみましょう。実はこれ、皆さんのご想像通り、私が作った問題とほぼ同じだったのです。

あ、ってなりました。その問題(自作)の想定解、ついおととい(3/18?)に書いたもので、「え、運命の出会い...💕」ってなりました。

私の友だちもなんか高速で解いてたので、それを見てからもう一度見たら思いついたのです。
もしかしたら序盤で気づいていたら青perfも夢ではない...！？！？

...あ、じゃあ解説に入ります。

ランレングス圧縮された情報をもとに頑張れ！って問題です。
これは $A,B$ 毎に pos という現時点で見る index をもって動かします...ん～、端的に言うとしゃくとり法？貪欲法？ですかね...(本質は違うので多分そうは言えないかもですが)

$A,B$ 毎の現時点で見る index を $pa,pb$ とします。で、入力は pair でやっているので、first,second を使います。

B[pb].second <= A[pa].second なら...
- A[pa].first == B[pb].first (今見ている整数が同じか？) なら答えに B[pb].second を足す※
- A[pa].second -= B[pb].second する (見た整数の個数を減少させる、これは pa が探索済であることを表す)
- pb++ する (このブロックでは pa を基準にしているため、pb を進める)
それ以外なら...
- A[pa].first == B[pb].first なら答えに A[pa].second を足す
- B[pb].second -= B[pa].second する (これは pb が探索済であることを表す)
- pa++ する (このブロックでは pb を基準にしているため、`pa を進める)

わかりづらくてすみません、でも実際にデバッグ大臣を呼んでみるとわかると思います...

Submissionは以下のようになります。

int main(void){
    ll l,n,n2; cin >> l >> n >> n2;
    vector<P> A(n),B(n2);
    rep(i,n) cin >> A[i].first >> A[i].second;
    rep(i,n2) cin >> B[i].first >> B[i].second;
 
    ll ans = 0;
    int pa = 0,pb = 0;
    while(pa < n && pb < n2){
        if(B[pb].second <= A[pa].second){
            if(A[pa].first == B[pb].first) ans += B[pb].second;
            A[pa].second -= B[pb].second;
            pb++;
        } else {
            if(A[pa].first == B[pb].first) ans += A[pa].second;
            B[pb].second -= A[pa].second;
            pa++;
        }
    }
 
    cout << ans;
}

※B[pb].second <= A[pa].second の条件より、A[pa].second-B[pb].second は $0$ 以上になります。つまりこれは A[pa].second 以前に B[pb].second が被覆していることを示すため、そのまま答えに加算することが適切です。これも実験でわかります。多分。

Epilogue

入緑後初めてのABC、なんとかまた上げることができました。とりあえず、作問ができる資格が持てたのでよかったです。

よし、緑梅してきます。