Supership VPoEの名畑です。
昨年末に採用活動のために競技プログラミング（AtCoder）を始めて一年経ったので感想を書きますという記事を書きました。
それをAtCoderの社長である高橋様に褒めていただけたのは2021年の私的良かったことニュース上位です。本当にありがとうございます。
AtCoderの温度感とかいろんなものが分かるだいぶ良い記事だった。AtCoder分からんけど興味ある人におすすめ。
— chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) December 1, 2021
採用活動のために競技プログラミング（AtCoder）を始めて一年経ったので感想を書きます https://t.co/8NTPMTt3pC #Qiita
しかし、目標である緑到達を成して以降、あまり競プロをできていませんでした。
勘を取り戻すべく、アルゴリズム実技検定の過去問題を最近解いています。
弊社Slackの競プロchannelでちょくちょく話題に出る検定なんですよね。Practical Algorithm Skill Testで略してPAST。
それで、誰かのお役に立つかもしれませんし、私の解答例(Python3)を今後、公開していきます。
私のレベル的に難易度低めな問題中心になるとは思いますが。
今回の記事では、そもそもとしてアルゴリズム実技検定とはどういうものなのかという説明と、過去問題が公開されている範囲では直近の開催である第11回のA問題〜C問題の解答例を掲載します。
後述しますがA問題〜C問題がとければ等級がエントリーとなります。この3問を見れば、どのような試験か、なんとなく肌感はつかめるのではないかと思います。
アルゴリズム実技検定
アルゴリズム実技検定について公式サイトを読みますと下記の概要が書かれています。
（公式サイトに実はしれっと弊社ロゴもございます）
IT人材のプログラミングスキルを可視化できる検定
世界最大級の競技プログラミングコンテストサイトを運営するAtCoder社による、1からプログラムを作成する能力を問う、実践を想定した日本初の検定です。
オンライン受験です。
AtCoderで利用できる全プログラミング言語が使えます。
結果は受験後即時発表です。
費用は一般受験だと8,800円です。
団体受験はその人数に応じて金額が変わり、30名以上だと一人当たり7,040円、100名以上だと一人当たり6,160円です。
すべて税込です。
試験時間は300分、15問(A〜O)100点満点です。
- A問題：9点
- B問題〜C問題：8点 × 2
- D問題〜F問題：7点 × 3
- G問題〜O問題：6点 × 9
獲得点数に応じて5段階の等級が認定されます。
- エントリー：25点
- 初級：40点
- 中級：60点
- 上級：80点
- エキスパート：90点
各等級が示す具体的な実力や出題範囲についてはアルゴリズム実技検定（PAST）とはに記載されております。
認定の有効期限は2年間と設定されています。
正解までの時間や不正解の回数は点数に影響しませんが、同じ問題には1分に1度しか解答提出できません。これはAtCoderとの大きな違いですね。
A問題からどこまで解けばどの等級に達するかは下記の通り。別にA問題から順番に解く必要はないという前提ではありますが。
- エントリー：C問題までの3問（25点）
- 初級：F問題までの6問（46点）
- 中級：I問題までの9問（64点）
- 上級：L問題までの12問（82点）
- エキスパート：N問題までの14問（94点）
それぞれAtCoderでは灰・茶・緑・水・青ぐらいのレベルらしいです（茶は上位50%、緑は上位30%、水は上位15%、青は上位7%です。灰は1回でも参加すればつきます）。
アルゴリズム実技検定について
— chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) November 18, 2019
・５段階評価は灰・茶・緑・水・青に近い評価です。
・普通に受けたら１色下がると思います。5時間コンテストはおよそコンテスト3回分であり、3回分のレート補正値は500近くあるので。
・それでも一発受験で認定出来るのが大きなメリットだと思ってます。
2019年のつぶやきなので、今のレベルとは異なるかもしれませんが。
また、ターゲットはどちらかといえばAtCoderの非参加者だって投稿もありました。
昨日偶然アルゴリズム実技検定の話を見たんだけど、「お布施以外に受ける意味がない」というのは、AtCoder参加者についてはその通りで、どちらかというとAtCoder非参加者がターゲットだよ。レーティングを持ってない人が、レーティングと同等の価値の資格を取ることで代替できるよ、ってコンセプト。
— chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) March 20, 2022
第3回アルゴリズム実技検定（PAST）結果発表 〜5087名が受験〜で第1回〜第3回の受験者の情報が公開されているのですが、第3回だと初級がボリュームゾーンで、全体の28.3%でした。第2回だと中級がボリュームゾーンで、全体の24.7%。
リアルタイム受験と通常受験があり、リアルタイム受験はAtCoderのABC(AtCoder Beginner Contest)やARC(AtCoder Regular Contest)同様で決まった時間の一斉受験です。通常受験は一定期間（今は3ヶ月）の中で受けるものです。
リアルタイム受験の場合は時計マークが認定証に付与されます。
第12回は2022年12月2日(金) 23:59までで、第13回は2022年12月3日(土)の13:00からです。
現時点で公開されている過去問題
第12回は通常受験が2022年12月2日までなので、それより後のどこかのタイミングで過去問題として公開されることでしょう。
解答例
第11回のA問題からC問題の私の解答例です(D問題から先は次回以降)。
冒頭に記載しましたが、この3問が解ければエントリーとなりますね。
私が解いた感覚では、A問題はABCのA問題(100点)同様の難易度、B問題とC問題がABCのB問題(200点)とC問題(300点)の間ぐらいの難易度でしょうか。
公式の解説との一致は求めないでください。いつも解説を読む前に解き始めるので。
私の言語
- Python (3.8.2)
A問題 うさぎとかめ(9点)
X, A, B, C = map(int, input().split())
if X / A + C < X / B: # うさぎの勝ち
print("Hare")
elif X / A + C > X / B: # かめの勝ち
print("Tortoise")
else: # 同着
print("Tie")
距離/秒速が走っている秒数になるわけですが、Xの距離を走る中でX/2を必ず一度だけ通るので、うさぎは走っている最中に絶対にC秒眠ります。なので比較時にうさぎの秒数には必ずCを加算する。
B問題 2文字(8点)
S = input()
len_s = len(S)
dict_s = {}
for i in range(len_s - 1):
tmp = S[i:i + 2] # i番目とi+1番目の文字を取得
if tmp not in dict_s: # まだ辞書になければ1を初期値
dict_s[tmp] = 1
else: # すでに辞書にあれば1を加算
dict_s[tmp] += 1
max_count = max(dict_s.values())
dict_s = sorted(dict_s.items()) # 辞書順にソート
for v in dict_s: # 辞書を走査
if v[1] == max_count: # valueを最大値と比較
print(v[0]) # keyを出力
exit()
先頭から2文字ずつを愚直に取得し、それぞれが何回登場したかをカウントしておきます。
取得済みの2文字の集合を辞書順に並べて、カウント数を一つずつ見ていく。その数値が最大値であれば対象の2文字を表示して終了。
もっと速い手法はあるのでしょうが、Sの最大値が2*10^5なのでこれでも100msec以内で終わります。
C問題 オーダー(8点)
import math
N, M = map(int, input().split())
s = ""
if N == 1: # 何乗しても1のためoで埋める。
s = "o" * M
else:
# 何乗すれば10^9を超えるか計算
k = math.log(10 ** 9 + 1, N)
k = math.ceil(k)
if k - 1 <= M:
s = "o" * (k - 1) + "x" * (M - k + 1)
else: # M桁の間に10^9を超えないためoで埋める
s = "o" * M
print(s)
10^9を超える境界値を求めて、そこまでをoで、そこから先をxで埋めているだけです。
条件分岐はもっと整理できそうな気もしています。
最後に宣伝
SupershipのQiita Organizationを合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。
Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方はSupership株式会社 採用サイトよりご確認ください。
是非ともよろしくお願いいたします。