hotaruの蛍雪日記

競プロとゲームをしています

緑コーダーの俺がアルゴリズム実技検定を受けたら上級だった件

こんにちは。

アルゴリズム実技検定って何?

https://past.atcoder.jp/ f:id:hotarunx:20200527204921p:plain

アルゴリズム実技検定(PAST)は、プログラミングコンテストを開催するAtCoderが2019年より始めた検定です。

5時間でプログラミングの問題を解いて、その結果で5段階の認定を受けます。

  • エキスパート 90点以上(前から解いて1問以外解く)
  • 上級 80点以上(前から解いて3問以外解く)
  • 中級 60点以上(前から解いて6問以外解く)
  • 初級 40点以上
  • エントリー 25点以上

いつものコンテストのような問題を解きます。

ざっと見たところ水色上位と青色下位が上級を取れるようです。

きみは?

https://atcoder.jp/users/machikane

f:id:hotarunx:20200527204927p:plain

今回の第3回PASTに参加しました。 その結果、12問(最初から順に解いて3問残る)をACして82点、上級でした。

f:id:hotarunx:20200527204849p:plain

上級を取れるのは水色の半分なので、私が上級を取れるのはけっこうすごいと思います。 上級易化らしくて涙。

実際コンテストでは高いパフォーマンスを出して難しい問題を解きました。

第3回では水色中級や黄色上級もちらほら見られました…。

問題

記事の性質上、第3回アルゴリズム実技検定の問題のネタバレを含みます。

第三回 アルゴリズム実技検定 問題へのリンク

A. ケース・センシティブ

問題へのリンク

やるだけですね。 s,tが同じならsame、そうでなければs,tを小文字に変換して同じならcase-insensitiveです。 うまく書くならば、要素のすべてに関数を適用するstd::transform、文字を小文字にするtolowerを使ってこう書くのがよいのではないでしょうか。 tolowerの戻り値はcharではなくintです。 transformではコンテナと関数の戻り値の型が同じでないとエラーが出るようなので、tolower戻り値の型を変更します。

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    if (s == t) {
        cout << "same" << endl;
        return 0;
    }

    // 小文字に変換
    transform(s.begin(), s.end(), s.begin(),
              [](char c) { return (char)tolower(c); });
    transform(t.begin(), t.end(), t.begin(),
              [](char c) { return (char)tolower(c); });

    if (s == t) {
        cout << "case-insensitive" << endl;
        return 0;
    }

    cout << "different" << endl;
}

B. ダイナミック・スコアリング

問題へのリンク

参加者が解いた問題のみを記録する方法は計算量が多くてTLEします。

  • 参加者が問題を解くクエリはO(1)
  • 1問題の得点を求めるのはO(N)。参加者のスコアを求めるクエリはO(NM)
  • 全体ではO(NMQ)です。

ここで、参加者が解いた問題に加えて問題の現在の得点を記録する方法を取ります。問題の得点は問題を解いたときしか変化しないため、問題を解くクエリで問題の得点を変化させます。1問題の得点を求める操作が高速化してTLに間に合います。

  • 参加者が問題を解くクエリはO(1)
  • 1問題の得点を求めるのはO(1)。参加者のスコアを求めるクエリはO(M)
  • 全体ではO(MQ)です。

C. 等比数列

問題へのリンク

R \gt 2のとき、 AR^ {30} \geq 2^ {30} = 1073741824 \gt 10^ 9 なので、第31項以降は10 ^9 より大きいです。

なので、第30項まで調べればよいです。第1項から第N項まで順に計算、10 ^9 を超えたら途中で計算を打ち切ります。 この方法だとR=1のときO(N)となってしまうので、例外処理します。

なお定数倍が非常に小さいため、C++ (GCC 9.2.1)では例外処理をしなくても実行時間約800msとなり間に合います。

D. 電光掲示

問題へのリンク

やるだけですがめんどいです。 僕は電光掲示板の文字が書いてある部分を1つの文字列として切り出して処理しました。

f:id:hotarunx:20200619234444j:plain

E. スプリンクラー

問題へのリンク

無向グラフを知っていますか? 私は知っています。

F. 回文行列

問題へのリンク

少し悩みました。 A_iA_{n-1}に同じ文字が有れば回文を作れます。

G. グリッド金移動

問題へのリンク

グリッドの範囲は無限だが、スタート、ゴール、障害物は(-200,-200)から(200,200)までの範囲内にしかない。 すぬけくんが最短経路を移動するとき、(-201,-201)から(201,201)までの範囲しか通らない。 なので(-201,-201)から(201,201)までの範囲のグリッド内で幅優先探索すれば最短距離が求められます。

H. ハードル走

問題へのリンク

1次元DPです。 下のDP表を計算します。 そしてDP表より、ジャンプしながらゴールするまでにかかる秒数を計算します。最終的な答えを計算します。dp(i): 座標iを走りながら通るまでにかかる秒数の最小値。

もしdp(i)でジャンプ中に通る秒数も加味すると、DPの遷移を考えるのが難しくなると思います。

配るDPだと実装が楽だと思います。

I. 行列操作

問題へのリンク

これは少し悩みました i行の元の行番号をR_ij列の元の列番号をC_jとします。 a_{i,j} = N \times (R_i - 1) + C_j - 1です。 こうすればクエリをO(1)で処理できるようになります。 例えばA行とB行の交換は、R_AR_Bの値の交換として表現できます。

J. 回転寿司

問題へのリンク

それぞれの子供が今までに食べた寿司の美味しさを記録しておきます。 二分探索で誰が寿司を食べるかがわかります。

K. コンテナの移動

問題へのリンク

連結リストを知っていれば解法が思いつくかもしれません。 私はUnion Findを実装したことがあるので思いつきました。

各コンテナの下のコンテナ番号と各机の一番上のコンテナ番号を管理します。 こうすればクエリはO(1)、各コンテナが乗っている机はO(N)で求められます。

L. スーパーマーケット

問題へのリンク

前から順に解いていって、これを解ければ上級です。

なんと1\leq a_i \leq2です。

商品棚1列目と2列目の商品を、高速に最大値を取り出して新しい値を入れられるデータ構造で管理したらいいです。

このデータ構造にはpriority_queueを使えば良いと考えます。 しかし商品を2列目のデータ構造から1列目のデータ構造に移動する必要がありますが、priority_queueでは特定の要素を取り出すことができません。

本番では、消費期限がユニークなことを利用して、取り出した商品を記録する方法でこの問題を解決しました。 2列目のpriority_queueから1列目のpriority_queueに移動する代わりに、2列目のpriority_queueから商品を取り出さずに1列目のpriority_queueに商品を入れます。 priority_queueで取り出した商品を記録します。 2列目のpriority_queueから、すでに取り出した商品を取り出そうとしたときは、もう一度取り出すという処理をしました。

本番の実装 https://atcoder.jp/contests/past202005-open/submissions/14648246

丁寧に書くならばsetを使えば良いでしょう。 最後の要素が最大値です。要素取り出しも挿入も\log(N)でできます。

クエリはこう処理しました。

  1. 商品棚の状態を表すdequeshelfs[i]と、商品棚vectorshelfsを用意する。
  2. 1列目と2列目の商品を表すrow_goods[0], row_goods[1]を用意する。
  3. 最大商品をrow_goodsから探す。
  4. 商品棚の状態を最大商品を取り出した後に更新する。
    1. 最大商品が入っている商品棚の商品をrow_goodsから取り出す。
    2. shelfsから最大商品を取り出す。
    3. 最大商品が入っていた商品棚の商品をrow_goodsに入れる。

書き直した実装 https://atcoder.jp/contests/past202005-open/submissions/14648078

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;

    // 陳列棚集合
    // 商品棚の集合を管理する
    // pairは商品の{消費期限, 陳列棚番号}を表す
    vector<deque<pair<int, int>>> shelfs(n);
    for (int i = 0; i < n; i++) {
        int ki;
        cin >> ki;
        for (int j = 0; j < ki; j++) {
            int t;
            cin >> t;
            shelfs[i].push_back({t, i});
        }

        // 番兵
        // 商品棚に商品が無いときの例外処理を省くため、消費期限0の商品を番兵として追加する
        shelfs[i].push_back({0, 1});
        shelfs[i].push_back({0, 1});
    }

    // 1列目と2列目の商品を管理する
    // 消費期限最大の商品を取り出したり、新たに商品を入れる処理を頻繁に行うため平衡二分探索木にしている
    vector<set<pair<int, int>>> row_goods(2);

    // shelfsの商品をrow_goodsに入れる
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < n; j++) row_goods[i].insert(shelfs[j][i]);

    int m;
    cin >> m;

    // 消費者が商品を取り出していく
    for (int customers = 0; customers < m; customers++) {
        int ai;  // 消費者が何列目の商品まで見るか
        cin >> ai;

        // 取り出す商品、つまり消費期限最大商品
        pair<int, int> best_good = {-1, -1};
        // 商品が1列目、2列目にある。商品がどこの商品棚にある。
        int row_best_good = -1, shelf_best_good = -1;

        // 1列目、2列目の中から取り出す商品を探す
        for (int i = 1; i <= ai; i++) {
            // setでは商品は昇順に並んでいる。row_goodsの最後の要素が最大の要素
            pair<int, int> nowbest_good = *prev(row_goods[i - 1].end());

            if (nowbest_good > best_good) {
                best_good = nowbest_good;
                row_best_good = i - 1;
                shelf_best_good = best_good.second;
            }
        }

        // shelfs, row_goodsを、商品を取り出した後の状態に更新する

        // 取り出す商品が入っている商品棚の商品をrow_goodsから取り出す。
        row_goods[0].erase(shelfs[shelf_best_good][0]);
        row_goods[1].erase(shelfs[shelf_best_good][1]);

        // 取り出す商品をshelfsから削除する
        if (row_best_good == 0) {
            shelfs[shelf_best_good].pop_front();
        } else {
            shelfs[shelf_best_good].erase(
                next(shelfs[shelf_best_good].begin()));
        }

        // 取り出す商品が入っていた商品棚の商品をrow_goodsに入れる
        row_goods[0].insert(shelfs[shelf_best_good].front());
        row_goods[1].insert(shelfs[shelf_best_good][1]);

        cout << best_good.first << endl;
    }
}

M. 行商計画問題

問題へのリンク

ここから解けませんでした。

N. 入れ替えと並び替え

問題へのリンク

O. 輪投げ

問題へのリンク