もふふろぐ

第一回 アルゴリズム実技検定

atcodercompetitiveprogram

12月14日に実施されたコンテスト第一回 アルゴリズム実技検定（過去問）に参加しました。

アルゴリズム実技検定（PAST）はAtCoderが実施する有料コンテストです。 ランディングページがおしゃれですね。 普段実施されているAtCoder Beginner Contestなどとは主に次の点が異なります。

  • 受験費用（税込8,800円/人）が掛かる
  • 12月14日から28日の任意の時刻に開始できる（その期間問題についての口外が禁止される）
  • 難度が低いほど配点が高い
  • 点数に応じた等級の認定証が付与される
  • Rated対象なし（Unrated）
  • 順位表がない

現在のところ、コンテスタントがAtCoder株式会社に貢げる唯一のコンテンツになっています。

略称のPASTは漫画でも話題になりました。

コンテスト

コンテストでは5時間で15問が出題されました。 M問題、O問題以外の13完で88点を獲得し上級（80点以上90点未満）に認定されました。 全完できずとても残念(๑>﹏<๑｀)

A 2 倍チェック / Is It a Number?

入力された文字列が正整数ならその2倍を、そうでなければ"error"を出力する問題。 文字列を1文字ずつ処理する方法、あるいは文字列と整数を相互に変換する方法を知っていたり、検索したりできれば解けるでしょう。

B 増減管理 / Up and Down

整数列の$i$番目と$i + 1$番目の大小を出力する問題。 大小とともに出力する値が絶対値でなければならない点に注意します。

C 3 番目 / The Third

整数列のうち、3番目に大きい数を出力する問題。 「X番目に小さい/大きい」は混乱を招きやすい表現ですが、本問では幸いにも、入出力例で確認することができます。

D 重複検査 / Duplicated?

順列から1要素が書き換えられた可能性のある整数列が与えられるので、どの数が書き換えられたか出力する問題。 各数の出現回数を数え、0回の数と2回の数を出力しました。

E SNS のログ / Restore

フォロー中の人がフォロー中の人を一括でフォローするなど、3種類の操作をシミュレートする問題。 問題文通りに実装すればACできます。 フォロー関係の行列を表現する際、vector<vector<bool>>の代わりに例えばvector<bitset<100>>を使うことで一括フォローの実装を楽にできました。

フォローのフォローをフォローする操作では、行列を逐一更新してしまうと、元々フォローしていなかった人まで操作に含めてしまうので、そうならないよう一時変数を置く工夫が必要です。

F DoubleCamelCase Sort

入力の文字列を[A-Z][a-z]*[A-Z]の形をした文字列（例. AtcodeR, AC）に分割し、ソートし、結合して出力する問題。 1文字ずつ読んで、大文字が2回現れるごとに分割することで、要求を満たせます。

ソートするときに「大文字小文字の違いは無視する」よう注意します。 分割された文字列を一旦小文字にしてからsort関数を使用するのが楽だと思います。

G 組分け / Division

$N$人の社員を3個以下のグループに分けたときの「好ましさ」の最大値を求める問題。 $N \leq 10$なので全探索できます。 bit全探索で楽に実装できました。

H まとめ売り / Bulk Selling

カード $1, \dots, N$ をそれぞれ $C_1, \dots, C_N$ 枚持っている状態から始め、カード$x$を売る、奇数番目のカードを売る、全カードを売る3種類のクエリを処理する問題。 クエリの種類別に何枚カードを売ったかを管理しました。

I 部品調達 / Procurement

bit DPをする問題。 典型的なので、「bit DP」を調べると同様の問題と解説を見つけられると思います。

J 地ならし / Leveling

$H \times W$のグリッド上で、左下隅から右下隅を経由し右上隅まで移動するときに、踏むマスに書かれたコストの和の最小値を求める問題。 ただし、一度通ったマスのコストは二度計算しません。

グリッド上のある1マスから、左下隅・右下隅・右上隅それぞれに行く問題に読みかえられるので、そのマスを全探索しました。

K 巨大企業 / Conglomerate

与えられた根付き木について、頂点$a$が頂点$b$の子孫であるか判定するクエリに答える問題。 根付き木を括弧列として見る要領で、根から深さ優先探索を1回し、$i$番目の頂点が何番目の頂点までを子孫として持つかをあらかじめ求めておきました。

L グラデーション / Gradation

$N$頂点（$2 \leq N \leq 30$）を連結にするために作る辺のコストの合計の最小値を求める問題。 各頂点に「色」があり、辺のコストは両端の頂点の色から計算されることになっています。 加えて、連結にしなくてもよい$M$頂点（$1 \leq M \leq 5$）も与えられます。

まず、$M$頂点は無視して、与えられたすべての頂点を連結にすると考えます。 この場合、両端の頂点がまだ連結になっておらずコストが最小の辺から、貪欲に作ることで最小コストを求められます。 （後で知ったのですが、最小全域木というそうです。）

$M$が小さいので、どの頂点を使うかを全探索することで、この問題全体での最小コストを計算できました。

M

未提出。

N 整地 / Land Clearing

幅 $W$ の線分上に、区間 $(l_i, r_i)$ を占有する撤去コスト $p_i$ の石 $N$ 個が入力されるので、石が存在しない長さ $C$ の区間を作るためのコストの最小値を求める問題。 石の両端の座標（とコスト）をソートした配列について、しゃくとり法の要領で、条件を満たす区間を探しました。

O

未読。 （自分にはM問題より簡単に見えたので、ここまで時間を残せなかったことを反省。）

感想

AtCoder初級者にとっては、後半に並ぶ500点、600点級問題の連続は険しく、あっというまに5時間が過ぎてしまいました。 エキスパート（90点以上）を得るにはAtCoder黄程度の実力が必要だったと思います。 （あるいは、問題数に動じず最後まで考察を鈍らせない持久力が求められたのでしょうか。）

受験費用の8,800円は高額だと思いました。 （例えば某謎解きの検定は3,200円。） 学生が趣味で参加するコンテストではなく、企業の団体受験を主要な対象に据えたコンテストであると伺えます。 すでに日常的にコンテスト参加している人にとっては、検定をきっかけに競プロの認知度が向上することが一番の恩恵になりそうです。

オンラインで自由に解ける以上、コンテスト名にある「検定」としての信頼性には懸念が残ります。 競争やレーティング以外の報酬によって競プロerを惹きつけるコンテンツになりそうだと思いました。