アルゴリズム実技検定(過去問)に参加しました。アルゴリズム実技検定(PAST)はAtCoderが実施する有料コンテストです。ランディングページがおしゃれですね。Contestなどとは主に次の点が異なります。受験費用(税込8,800円/人)が掛かる12月14日から28日の任意の時刻に開始できる(その期間問題についての口外が禁止される)難度が低いほど配点が高い点数に応じた等級の認定証が付与されるRated対象なし(Unrated)順位表がない現在のところ、コンテスタントがAtCoder株式会社に貢げる唯一のコンテンツになっています。略称のPASTは漫画でも話題になりました。2019コンテストコンテストでは5時間で15問が出題されました。M問題、O問題以外の13完で88点を獲得し上級(80点以上90点未満)に認定されました。Number?入力された文字列が正整数ならその2倍を、そうでなければ"error"を出力する問題。文字列を1文字ずつ処理する方法、あるいは文字列と整数を相互に変換する方法を知っていたり、検索したりできれば解けるでしょう。1$番目の大小を出力する問題。大小とともに出力する値が絶対値でなければならない点に注意します。Third整数列のうち、3番目に大きい数を出力する問題。「X番目に小さい/大きい」は混乱を招きやすい表現ですが、本問では幸いにも、入出力例で確認することができます。Duplicated?順列から1要素が書き換えられた可能性のある整数列が与えられるので、どの数が書き換えられたか出力する問題。各数の出現回数を数え、0回の数と2回の数を出力しました。Restoreフォロー中の人がフォロー中の人を一括でフォローするなど、3種類の操作をシミュレートする問題。問題文通りに実装すればACできます。フォロー関係の行列を表現する際、vector<vector<bool>>の代わりに例えばvector<bitset<100>>を使うことで一括フォローの実装を楽にできました。フォローのフォローをフォローする操作では、行列を逐一更新してしまうと、元々フォローしていなかった人まで操作に含めてしまうので、そうならないよう一時変数を置く工夫が必要です。AC)に分割し、ソートし、結合して出力する問題。1文字ずつ読んで、大文字が2回現れるごとに分割することで、要求を満たせます。ソートするときに「大文字小文字の違いは無視する」よう注意します。分割された文字列を一旦小文字にしてからsort関数を使用するのが楽だと思います。Division$N$人の社員を3個以下のグループに分けたときの「好ましさ」の最大値を求める問題。10$なので全探索できます。bit全探索で楽に実装できました。枚持っている状態から始め、カード$x$を売る、奇数番目のカードを売る、全カードを売る3種類のクエリを処理する問題。クエリの種類別に何枚カードを売ったかを管理しました。DP」を調べると同様の問題と解説を見つけられると思います。W$のグリッド上で、左下隅から右下隅を経由し右上隅まで移動するときに、踏むマスに書かれたコストの和の最小値を求める問題。一度通ったマスのコストは二度計算しません。それぞれに行く問題に読みかえられるので、そのマスを全探索しました。Conglomerate与えられた根付き木について、頂点$a$が頂点$b$の子孫であるか判定するクエリに答える問題。根付き木を括弧列として見る要領で、根から深さ優先探索を1回し、$i$番目の頂点が何番目の頂点までを子孫として持つかをあらかじめ求めておきました。30$)を連結にするために作る辺のコストの合計の最小値を求める問題。各頂点に「色」があり、辺のコストは両端の頂点の色から計算されることになっています。5$)も与えられます。$M$頂点は無視して、与えられたすべての頂点を連結にすると考えます。この場合、両端の頂点がまだ連結になっておらずコストが最小の辺から、貪欲に作ることで最小コストを求められます。(後で知ったのですが、最小全域木というそうです。)$M$が小さいので、どの頂点を使うかを全探索することで、この問題全体での最小コストを計算できました。区間を作るためのコストの最小値を求める問題。石の両端の座標(とコスト)をソートした配列について、しゃくとり法の要領で、条件を満たす区間を探しました。(自分にはM問題より簡単に見えたので、ここまで時間を残せなかったことを反省。)感想AtCoder初級者にとっては、後半に並ぶ500点、600点級問題の連続は険しく、あっというまに5時間が過ぎてしまいました。エキスパート(90点以上)を得るにはAtCoder黄程度の実力が必要だったと思います。(あるいは、問題数に動じず最後まで考察を鈍らせない持久力が求められたのでしょうか。)受験費用の8,800円は高額だと思いました。(例えば某謎解きの検定は3,200円。学生が趣味で参加するコンテストではなく、企業の団体受験を主要な対象に据えたコンテストであると伺えます。日常的にコンテスト参加している人にとっては、検定をきっかけに競プロの認知度が向上することが一番の恩恵になりそうです。オンラインで自由に解ける以上、コンテスト名にある「検定」としての信頼性には懸念が残ります。競争やレーティング以外の報酬によって競プロerを惹きつけるコンテンツになりそうだと思いました。remin本サイトではコンテンツの分析と改善のためにGoogleアナリティクスを使用しています。本サイトのユーザは本サイトを利用することでcookieの使用に許可を与えたものとみなします。