加賀一稿一記

心は戦国

アルゴリズム実技検定PASTを受けてみました

AtCoderが始めたアルゴリズム実技検定，PASTを受けてみました．
past.atcoder.jp
出題された問題の難易度感などを振り返ってみます．


PASTとは？？
試験期間内であれば，8800円を払うことで5時間15問の試験を受験できて，その結果からランクが付きます．
点数を元に５段階評価され，AtCoderの灰〜青あたりに相当するとchokudaiさんがツイートしてます．


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円の価値があるかは今のところよく分からない．今後統計データ公開とかによって価値が付与されていく？