アルゴリズム実技検定PASTを受けてみました
AtCoderが始めたアルゴリズム実技検定,PASTを受けてみました.
past.atcoder.jp
出題された問題の難易度感などを振り返ってみます.
PASTとは??
試験期間内であれば,8800円を払うことで5時間15問の試験を受験できて,その結果からランクが付きます.
点数を元に5段階評価され,AtCoderの灰〜青あたりに相当するとchokudaiさんがツイートしてます.
アルゴリズム実技検定について
— chokudai(高橋 直大)🌸🍆🍡 (@chokudai) 2019年11月18日
・5段階評価は灰・茶・緑・水・青に近い評価です。
・普通に受けたら1色下がると思います。5時間コンテストはおよそコンテスト3回分であり、3回分のレート補正値は500近くあるので。
・それでも一発受験で認定出来るのが大きなメリットだと思ってます。
AtCoderの青評価を1回のコンテスト(?)でもらえるならお得な感じがしますね.
(通常のコンテストでは,参加回数をこなさないとレートが上がりきらないため)
試験問題は↓で解けます.
atcoder.jp
難易度感
ABCDEFGHI
実装問題セット
最初のうちはループやソートが書けたら解けますが,そのうち3^N通りの全列挙,bitでのフラグ管理などが要求されます.
競プロ的実装方法を知っていると素早く書けると思いますが,知らなくても5時間あるしゴリ押しでどうにかなるかも.
問題サンプルとほぼ同じ問題が出題されたりしている.閃きより実装力重視?
(実装問題と書きましたが,アルゴリズムを考える部分もちゃんとあります)
ここの問題を解いていくとエントリー→初級→中級になります.
JKL
グラフアルゴリズム問題セット
Jは中間地点を全探索した上でのダイクストラ法.
KはLCAそのもの.
Lは使うノードを全探索した上での最小全域木.
グラフアルゴリズムの実装は有志が公開していたり,蟻本で紹介されていたりするので,意外と実装は楽.
ただ,知らないとどうしようもないので知識が必要ですね...
ここまで全部解くと上級.
MNO
難しい問題セット.
Mは数式を変形させて二分探索.
Nは尺取り法.
Oは期待値.
ABCのEFにいてもおかしくない難易度.
試験時間の半分以上をこの3問に使って,結局Oは解けなかった...
今まで全てと,ここから2問以上解くとエキスパート.
感想いろいろ
- 5時間は長いので時間と体力の管理は重要.(N分かけて分からなかったら飛ばす.水分補給をちゃんとする.など)
- いつでも受験できるので,やる気が高まった時に受験できて最高.
- 実装問題が多い.ABCの実装問題パートが3倍になった感じ.嫌いではない.
- ABCDEFGHIで,実装に慣れてないと無限にバグらせそう.この辺りの対策は精進ですかね...
- JKLでグラフアルゴリズムを要求してくる.対策として蟻本やAOJのコースとかをやっておくといいかもしれない.次はUnion-Findが出そう(?)
- MNOはABC全部解くと対策になる(???)
- トリッキーな問題はなかったし,難易度と等級はマッチしてそう.
- 受験料8800円の価値があるかは今のところよく分からない.今後統計データ公開とかによって価値が付与されていく?