エキスパートです#PAST受験結果 pic.twitter.com/0e8l183xRV
— ひとあれ (@hitoare1) December 14, 2019
12月14日にAtCoder社のアルゴリズム実技検定(PAST)をリアルタイム受験しました。
結果は満点でエキスパート認定を獲得できました。
受験時の実力
受験当日のレートは1911、青上位でした。
11月辺りからかなり熱心に過去問埋めをやっていて、受験日には青問題*1が半分くらい埋まっていたと思います。
直前対策
サンプル問題が新ABCの過去問(A1問、B2問、C~Fが3問ずつ)でした。まだ解けていない問題もあったのですが、「似ている問題を見たことがある」というだけでもアドバンテージになると思い、新ABCの過去問に一通り目を通しておきました。
試験中の動き
問題の内容、解法に関するネタバレを含みます。あと若干の記憶違いがあるかもしれません。興味のない方は飛ばしてください。
まずG問題あたりまでは普通に順番通りに解いていきました。途中急にお腹が痛くなってめちゃくちゃ焦りました(昼に食べたセブンイレブンのスタミナラーメンが効いたらしい)。ここまでで多分40～50分くらい。
Hを解きます。サンプルがなかなか合わずに焦りました。管理する値が多いので途中で足すべき値を足していなかったようです。
Iを解きます。典型なのですぐに解けました。
Jに取りかかります。一見シンプルですが、解法がなかなか思いつきません。後回しにします。
Kに取りかかります。「最小共通祖先だ！」と思い、Google検索します。かなり面倒そうなので、後回しにします。
Lの問題文を見ます。「最小全域木だ！」と思いますが、小さい塔の扱いが厄介そうなので、後回しにします。
Mの問題文を見ます。数日前に解いた食塩水のやつだ！と嬉しくなりました。ウキウキで実装し、ACしました。
Nの問題文を見ます。後回しにします。
Oを見ます。後回しにします。
とりあえず一周したので、残っているJ・K・L・N・Oのうち考えやすそうなものから手をつけます。
J。サンプル1を睨んだり、自分で例を考えているうちになんとなく「三叉路の中心を考える」解法が浮かんできました。はっきりとした証明はできていなかったのですが、とりあえず実装して提出するとACできました。
L。制約のM≦5に気づいた瞬間、全探索が思いつきました。Nも≦30と小さいので実行時間には余裕がありそうです。提出してACしました。
N。はじめ累積和やimos法を考えましたがWが≦10^9と大きいのでどうにもきつそう。ならばLiとRiだけ考えるか…と方針を切り替えたらイベントソートが浮かんできました。少々WAハマりしましたが、なんとかAC。
K。ここまでで2時間くらいだったので、他のサイトを参考にしつつ最小共通祖先(LCA)を求めるプログラムを実装します。ここでかなり時間を使い、またバグハマりもなかなか抜け出せませんでした。ACしたころには残り1時間くらいだったと思います。
O。最後の問題です。とりあえず考察すると「数の大小関係以外関係ない」とわかるので、座標圧縮ができます(まだすると決まったわけではない)。N=1の場合を手計算したりしましたが、最終的に期待値DPに行き着きました。添字が多くかなり混乱しましたが、なんとかACしました。
最終的に、20分ほどを残して全完することができました。
問題解説
問題の内容、解法に関するネタバレを含みます。
A - 2 倍チェック / Is It a Number? (9点)
3桁の整数が与えられるのでその2倍を出力する。しかし英小文字が含まれている場合はerrorと出力する、という問題です。
文字列として受け取った後、適当な処理をするだけです。1問目にしてはちょっと面倒かな、と思いました。
ABCだと200点くらいだと思います。
B - 増減管理 / Up and Down (8点)
N日間の売上が与えられるので、前の日との差に応じた処理をする問題です。
これも配列に入れてループを回すだけなので難しくないです。
ABCだと200点くらいだと思います。
C - 3 番目 / The Third (8点)
6個の整数が与えられるので、3番目に大きいものを求める問題です。
配列に入れてソートするだけです。
ABCだと200点くらいだと思います。
D - 重複検査 / Duplicated? (7点)
この辺から難易度が少し上がります。
1～Nまでの整数が1個ずつ含まれているデータがあるが、そのうち1個が別の整数に書き換えられた可能性があるので、何が何に書き換えられたか、もしくは書き換えが行われていないかを判定する問題です。
B[i]＝(数字iの登場回数)として、B[i]=0となるiとB[j]=2となるjが存在すればiがjに書き換えられたと判定するのが一番オーソドックスかなと思います。
ABCだと300点くらいだと思います。
E - SNS のログ/ Restore (7点)
「フォロー」「フォロー返し」「フォローフォロー」の3種類のクエリをQ個処理した後、各ユーザーのフォロー状況を出力する問題です。
フォローしている=trueとする二次元配列を用意して、書かれた通りの処理を行うだけですが、フォローフォローの実装がやや面倒です。
ABCだと難しめの300点くらいだと思います。
F - DoubleCamelCase Sort (7点)
最初と最後が英大文字、間が全て小文字の単語(FisH、AbC、AAなど)を1つ以上連結した文字列Sが与えられるので、単語ごとに分解した後辞書順にソートし (大文字小文字の違いは無視する)、再び連結した文字列を出力する問題です。
まず単語ごとに分解することからスタートします。
Sの先頭から順に見ていって、1個目の大文字から2個目の大文字、3個目の大文字から4個目の大文字、5個目の大文字から6個目の大文字…が1つの単語になります。
ただしこのままソートすると文字コードの関係で正しくソートできません。(小文字が大文字より常に後に来るので、AD < AbCみたいになります)
全部小文字に直してからソートして連結する時に最初と最後を大文字に戻す、などの方法があります。
ABCだと400点くらいだと思います。
G - 組分け / Division (6点)
N人の社員を３つのグループに分けます。社員のペア(i,j)を同じグループに入れた時の幸福度をAijとした時、幸福度の総和の最大値を求める問題です。
Nが10以下と小さいので全探索が使えます。DFS(深さ優先探索)をするか、bit全探索のように0～(3^N-1)までの3進数表記を用いる方法があります。
また、Rubyだとrepeated_perumutation、Pythonだとitertools.combinations_with_replacementを使うと楽に全列挙できます。
ABCだと400点くらいだと思います。
H - まとめ売り / Bulk Selling (6点)
最初に1～Nの番号がついたカードの在庫数Ciがそれぞれ与えられていて、「カードxをa個販売」「番号が奇数のカードをa個販売」「全種類をa個販売」(ただし、全てにおいて1種類でも在庫が足りなければ処理は行わない)の3種類のクエリをQ個処理した後の合計販売枚数を答える問題です。
N、Q≦200000なので、セット販売と全種類販売に在庫を1つずつ確認していると間に合いません。
「セットで販売した個数」「全種類で販売した個数」「番号が奇数の中で最小在庫数」「全種類の中での最小在庫数」を記録しておくことで、在庫が足りているかどうかの確認がスピーディにできます。
ABCだと400～500点くらいだと思います。
I - 部品調達 / Procurement (6点)
部品セットがいくつかあるので、N種類の部品を全て入手するための最小金額を求める問題です。
いわゆるbitDPです。
ABC142-Eとほぼ同じ問題です。
J - 地ならし / Leveling (6点)
グリッド上の各マスにコストが与えられていて、左下→右下→右上と移動する時に通過するマスのコストの合計(ただし、同じマスを何度通過してもコストは1回分)の最小値を答える問題です。
正直正攻法の解き方がわからないのですが、僕の解き方は
「ルートの中で、そのマスから左下・右下・右上に行く3つのルートが交わらないようなマスが存在する」と考えました(サンプル1でいうと(3,5))。そこで全てのマスに対し左下・右下・右上から到達するための最小コストを求めて、それらの和-2*(そのマスのコスト)の最小値を解答としました。
ABCだと400～500点ぐらいだと思います。
K - 巨大企業 / Conglomerate (6点)
N頂点の根付き木が与えられるので、「点aから親を辿っていって点bに辿り着くか」というQ個のクエリに答える問題です。
1個ずつ素直に辿ると間に合いませんが、問題を言い換えると「点aと点bの最短共通祖先は点bか」という問題になります。今回の中では割と知識よりな気がします。
ABCだと600点ぐらいだと思います。
L - グラデーション / Gradation (6点)
二次元平面上にN本の大きな塔、M本の小さな塔があり、できるだけ少ないコストで全ての大きな塔を橋で連結させたいです(小さな塔は連結させてもさせなくても良い)。ただし、各塔は赤、緑、青いずれかの色に塗られて、同じ色の塔を繋ぐ場合はユークリッド距離がそのままコストになり、異なる場合はその10倍のコストが必要になります。この時の最小コストを求める問題です。
いわゆる「最小全域木」問題です。小さな塔の扱いが厄介ですが、M≦5と少ないので、各部分集合に対してそれらを全て連結すると仮定すると通常の最小全域木問題に帰着できるので、その最小コストを求め、それらの最小値をとれば良いです。
ABCだと500～600点ぐらいだと思います。
M - おまかせ / Auto Choice (6点)
N体のモンスターとM体のお助けモンスターがいて、各モンスターに質量と魔力が定められています。このうちちょうど5体(ただしお助けモンスターは1体まで)を合成した時の強さを(魔力の和)/(質量の和)とした時の最大値を求める問題です。
先程も書きましたが食塩水がかなり近い問題なので、そちらを先に解くといいと思います。
二分探索で最大値を求めます。合成後の強さXを達成するためには、大体X*(質量)の魔力が必要です。よって(魔力)-X*(質量)の順にソートし、その値が大きい方から5体選べば良いです。
ABCだと500点ぐらいだと思います。
N - 整地 / Land Clearing (6点)
幅Wの門(座標0～Wの線分とみなす)の中にN個の石があります。石iは区間(Li,Ri)を占有していて、撤去するのにpi円のコストがかかります。石が存在しない幅Cの区間を作るための撤去コストの最小値を求める問題です。
W≦10^9と非常に大きいので、区間を全探索するのは難しそうです。しかし、考察すると区間の右端の候補は石の左端+門の右端だけを考えると十分だということがわかります。
あとは座標xを0から大きくしていって、区間(x-C,x)の中にある石の撤去コストの総和を求めます。イベントソートを利用します。コストの初期値を0として、石iに対し
- 座標Liで、Li≧Cならば現時点のコストを求めた後、コストをpi増やす
- 座標(Ri+C)で、コストをpi減らす
という2種類のイベントを用意し、座標が小さい順に処理します。門の右端のパターンも忘れずに求めます。
ABCだと500～600点ぐらいだと思います。
O - 持久戦 / Endurance (6点)
N個のサイコロがあり、サイコロiにはA_i1、…A_i6の数字が書かれています。書かれている数字は6N個全て相異なります。これらを、前の数字と同じ又は小さい数字が出るまで好きな順番で振れる(同じサイコロを何度振っても良い)時、サイコロを振る回数の期待値を最大にする戦略をとった時の期待値を求める問題です。
最終問題だけあって難しいです。まず、数は大小関係しか意味がないので1～6Nに座標圧縮します。
dp[i]を「目iが出た時、あと振れる回数の期待値」とします。(まだ1度も振っていない状態をdp[0]とします)目iが出た次、サイコロdを振った時の残り回数の期待値はE_d = Σdp[A_dj]*(1/6) (ただし1≦j≦6かつA_dj>i)です。よってdp[i]はこの値が最大のものに1足した値になります。
条件が複雑そうですが、1～6Nに対してその数字がどのサイコロに書かれているかをメモしておいて、iが大きいものから順にEdを更新させつつdpを遷移させていくとdp[0]が答えになります。
ABCだと600点ぐらいだと思います。
全体感想
まず初めに全体的に実務を意識した問題なのかな？と思いました。クエリ系の問題が多い、実装が若干複雑な問題が多い、社員管理やSNSといった題材、など。
一方で数学的なひらめきが必要な問題は少ないので、純粋にアルゴリズムの知識が問われる問題群だったと思います。
あと試験前は5時間は長いと思っていたのですが、途中で勝手に休憩をとっていいので予想していたほど疲れませんでした。
年4回を予定しているらしいので、今後受ける人の為の対策を挙げておきます。まず、基本的にはABCの過去問を一通りやるのがいいと思います。difficulty青までの問題は大体役に立つと思います。面倒でもしっかり実装しきる(慣れてきたらスピードも)能力が必要とされます。
あと重要なことですが、試験中にアルゴリズムに関してネットで検索することが許されています。実際に僕も最小共通祖先問題を解いたことが無かったので、先人の解説を参考にしつつ解きました。(試験時間が5時間もあるので、他の問題を早めに解けば余裕はあります)
なので、難しい問題でも「なんかこういう問題見たことがあるな～」ぐらいの認識でも持てているとかなり違うと思います。もちろん実際に解いておいた方が良いのは言うまでもないです。
また受けるかどうかはわかりませんが、新鮮で面白かったので今後も続けばいいですね。
*1:AtCoder Problemsでdifficultyが1600～2000と判定されている問題。大体500～700点付近
