概要

第一回アルゴリズム実技検定(PAST)を受験して満点を取ったので、どんな解法で解いたかをざっくりまとめる。

アルゴリズム実技検定(PAST)とは

無料の競技プログラミングのコンテストを毎週のように開催しているAtCoderが実施する、
プログラミングの能力を測る検定。
有料。 (第一回は8,000円+税、団体割引あり)

第一回は2019年12月に開催され、制限時間5時間で15問が出題された。

以下は第一回の情報である。

開始時の罠

この検定は、シリアルコードを購入し、それを入力して受験をする形式である。
開始時刻が1点に決まった「リアルタイム受験」と開始時刻の範囲が決まった「通常受験」がある。
まず、「リアルタイム受験」の前にシリアルコードを入力すると、
「リアルタイム受験」をするということで登録されてしまい、
「通常受験」のつもりで放置すると受験料をドブに捨てることになってしまうらしい。
(この罠は踏んでいないので、伝聞である)

次に、自分が踏んだ罠について述べる。
「通常受験」のためにPASTのページからログインし、
検定の情報の画面からシリアルコードを入力して受験を開始しようとした。
すると、検定のページに遷移するはずが、遷移先は404 Not Foundであった。
システムの障害か、問い合わせを投げようかと思ったが、
よく見るとさっきログインしたはずなのにログインしていない状態の画面であることに気がついた。
どうやら、PASTのページとは別に、AtCoder本体にもログインしないといけないようである。
(これは自分の場合であり、トラッキング防止やウイルス対策ソフトなどの環境による可能性も考えられる)

各問題の解法

ここでは各問題の自分の解法をざっと述べる。
全てC言語を用いた。

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

与えられた文字列の文字を順に見ていって、数字じゃないものがあったらerrorを出して終了する。
この判定にはisdigit()を使う。
数字じゃないものがなかったら、sscanf()で数値に変換して2倍して出力する。

B. 増減管理 / Up and Down

入力されたデータに従って、問題文の通りの出力をする。

C. 3 番目 / The Third

昇順にソートして、N - 3番目(0-origin)の要素を出力する。
ただし、問題よりN = 6である。
なお、このやり方で大丈夫なのは「入力の数値がすべて異なる」という条件がついているからである。

D. 重複検査 / Duplicated?

それぞれの数値が何個あるかを数える。
0個しかない数値から複数ある数値に書き換えられたと判定する。
0個しかない数値がない場合、書き換えは無かったと判定する。

E. SNS のログ / Restore

フォロー関係を隣接行列的なやつで管理し、問題文の通りの処理を行う。
「フォローしている垢がフォローしている垢をフォロー」をする際、
フォロー関係を直接更新してしまうと、
処理中に新しくフォローした垢についても処理をしてしまうことがあることに注意する。

F. DoubleCamelCase Sort

「単語」の始まりと終わりの位置を構造体に入れ、その構造体をソートし、出力する。

G. 組分け / Division

再帰を用いて全探索する。評価も素直に二重ループを回す。

H. まとめ売り / Bulk Selling

「区間への一律の値の加算」と「区間の最小値の取得」ができるセグメント木を用意する。
カードの番号を変換する関数を用意し、奇数のカードを前半、偶数のカードを後半に持ってくる。
最初にカードの在庫量をセグメント木に加算する。
各クエリについて、売るカードの在庫数の最小値をセグメント木で求め、売れるかを判断する。
売れる場合は売った数をセグメント木に減算し、答えに加算する。

I. 部品調達 / Procurement

「今どの部品を買っているか」をビットで表して引数とし、メモ化探索を行う。
今持っている部品しかないセットは買おうとしないようにする。

J. 地ならし / Leveling

左下隅、右下隅、右上隅を起点とし、それぞれダイクストラ法で各マスへの最短経路を求めておく。
ただし、移動のコストは移動先のマスを整備するコストとする。
この最短経路を使って、各マスからスタートして左下隅、右下隅、右上隅に移動するとしたとき、
整備するマスを求め、そこから整備にかかるコストを求める。
その最小値を出力する。

K. 巨大企業 / Conglomerate

「直属の上司」を「親」とする木について、LCA(最小共通祖先)を求められるようにする。
「社員 a が社員 b の部下である」⇔「aとbのLCAがbである」となる。

LCAを求めるには、まず以下の準備をする。

各ノードについて、1回親に移動した時のノードを求める。
ただし、親が無いノード(根)については、このノードは自分自身とする。
各ノードについて、2回、4回、…$2^n$回親に移動した時のノードを求める。($2^n \geq N$)
$2^n$回親に移動した時のノードは、$2^{n-1}$回親に移動した時のノードから$2^{n-1}$回親に移動した時のノードである。
これらの情報を使うと、0以上N以下の整数nについて、
各ノードからn回親に移動した時のノードを効率よく求めることができる。
また、二分探索により、ノードの深さ(根に到達するまでに親に移動する回数)を求められる。

この準備のあと、aとbのLCAは以下のように求められる。

aとbの深さが違う場合は、深さが大きい方のノードをそこから深さの差だけ親に移動した時のノードに替える。
各ノードから親に移動する回数を二分探索し、同じノードになる最低限の回数を求める。
この最低限の回数親に移動した先がLCAである。

L. グラデーション / Gradation

問題文の通りコストを設定し、最小全域木を求める。
小さい塔を使うかどうかを全探索する。
最小全域木は、以下のように求められる。

Union-Find木を用意する。
使う可能性があるエッジを、コストの昇順でソートする。
エッジを順番に見ていき、両端が同じグループかをUnion-Find木で判定する。
違うグループなら、それらを同じグループにし、そのエッジのコストを加算する。
同じグループなら、何もしない。

M. おまかせ / Auto Choice

選んだモンスターの魔力を質量で割ったものを最大化したい。
これは濃度のようなものなので、D - 食塩水の解き方をする。
すなわち、目標の強さを決めると、各モンスターについて
「目標の強さの時と比べて多い魔力の量(少ない時はマイナス)」
が定義できるので、この値の降順に貪欲で採用することで、目標の強さにできるかがわかる。
これを利用し、目標の強さで二分探索する。
お助けモンスターについては、どれを使うか、もしくは使わないかを全探索する。

N. 整地 / Land Clearing

座標圧縮を行う。
このとき、座標のクエリについて「指定以下で一番大きい座標」のIDを得られるようにしておく。
座標0、もしくは各石の端から始めるのが最適になるはずである。
そこで、これらの座標から石を撤去するコストを求める。
各石の範囲の座標の小さい側を「始まり」、大きい側を「終わり」とすると、
撤去する必要がある石は、
「始まりの座標が開始座標+C未満」かつ「終わりの座標が開始座標より大きい」石である。
また、これらの条件を満たす石は撤去する必要がある。
そこで、始まりの座標と終わりの座標それぞれについて石を撤去するコストの累積和を用意し、
「開始座標+C-1までに始まる石の撤去コスト」-「開始座標までに終わる石の撤去コスト」
を求めることで、この開始座標を用いた時のコストがわかる。
あとは、開始座標を候補から全探索する。

O. 持久戦 / Endurance

「要素1個への加算」と「範囲の最大値の取得」ができるセグメント木を用意する。
前に出た値以下の値を出したら終了なので、無限に続くことは無い。
そこで、「0」と出る可能性のある目を昇順にソートしておく。
後ろの要素から、以下の処理を行うことで、
前に出た値がその値のときに操作ができる回数の期待値を求める。

セグメント木の0以上N未満の範囲から最大値を求める。
これは前に出た値がこの値の時から各サイコロを振ったあと、操作ができる回数の期待値である。
なぜなら、各サイコロについて、この値より大きい目が出た時の期待値は加算されており、
小さい目が出た時の期待値はまだ加算されていないからである。
求めた最大値に1を足した値が、前に出た値がその値のときに操作ができる回数の期待値である。
「前に出た値がこの値の時に操作をする」という前提なので、まず1回操作ができるためである。
求めた期待値を6で割った値を、セグメント木のこの値が出る可能性があるサイコロを表す要素に加算する。
目は全て異なるという性質があるため、加算対象は1個だけである。
また、6個が等確率で出る目のうちの1個なので、6で割った値を加算する。

出る可能性のある目は全て正なので、前に出た値「0」の時の期待値が求める期待値である。

他の人たちの解法など

今まで見たものを挙げる。
載せられたくないのに載せられている人、載せられたいのに載せられていない人については申し訳ない。

とゆーかさ、書いといてなんだけど

注意

この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

(A - 2 倍チェック / Is It a Number?より引用、ほか各問題ページに同様の記載あり)

( ^o^)＜期限を過ぎたから解法公開するぞおおおお

（ ˘⊖˘）。o(待てよ、「この日時以前に」言及がなされた場合、とは書かれてないな…)

|AtCoder| ┗(☋｀ )┓三

( ◠‿◠ )👉そこに気付いてしまったか…悪いが賠償を請求させてもらう

▂▅▇▓▒░(’ω’)░▒▓▇▅▂うわあああああああ

第一回アルゴリズム実技検定(PAST)でやったこと

概要