アルゴリズム実技検定(PAST)について 並びに 第11回A〜C問題 Python解答例

[Supership](https://supership.jp/) VPoEの名畑です。

昨年末に[採用活動のために競技プログラミング（AtCoder）を始めて一年経ったので感想を書きます](https://qiita.com/nabata/items/44fa3995e476b12b9860)という記事を書きました。

それをAtCoderの社長である高橋様に褒めていただけたのは2021年の私的良かったことニュース上位です。本当にありがとうございます。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">AtCoderの温度感とかいろんなものが分かるだいぶ良い記事だった。AtCoder分からんけど興味ある人におすすめ。<br><br>採用活動のために競技プログラミング（AtCoder）を始めて一年経ったので感想を書きます <a href="https://t.co/8NTPMTt3pC">https://t.co/8NTPMTt3pC</a> <a href="https://twitter.com/hashtag/Qiita?src=hash&amp;ref_src=twsrc%5Etfw">#Qiita</a></p>&mdash; chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) <a href="https://twitter.com/chokudai/status/1465996604465303555?ref_src=twsrc%5Etfw">December 1, 2021</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

しかし、目標である緑到達を成して以降、あまり競プロをできていませんでした。

勘を取り戻すべく、[アルゴリズム実技検定](https://past.atcoder.jp/)の過去問題を最近解いています。
弊社Slackの競プロchannelでちょくちょく話題に出る検定なんですよね。**P**ractical **A**lgorithm **S**kill **T**estで略して**PAST**。

それで、誰かのお役に立つかもしれませんし、私の解答例(Python3)を今後、公開していきます。
私のレベル的に難易度低めな問題中心になるとは思いますが。

今回の記事では、そもそもとしてアルゴリズム実技検定とはどういうものなのかという説明と、過去問題が公開されている範囲では直近の開催である第11回のA問題〜C問題の解答例を掲載します。

後述しますがA問題〜C問題がとければ等級が**エントリー**となります。この3問を見れば、どのような試験か、なんとなく肌感はつかめるのではないかと思います。

## アルゴリズム実技検定


アルゴリズム実技検定について[公式サイト](https://past.atcoder.jp/)を読みますと下記の概要が書かれています。
（公式サイトに実はしれっと弊社ロゴもございます）

> IT人材のプログラミングスキルを可視化できる検定

> 世界最大級の競技プログラミングコンテストサイトを運営するAtCoder社による、1からプログラムを作成する能力を問う、実践を想定した日本初の検定です。

オンライン受験です。
[AtCoderで利用できる全プログラミング言語](https://atcoder.jp/contests/abs/rules)が使えます。
結果は受験後即時発表です。

費用は一般受験だと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）とは](https://past.atcoder.jp/feature)に記載されております。
認定の有効期限は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回でも参加すればつきます）。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">アルゴリズム実技検定について<br>・５段階評価は灰・茶・緑・水・青に近い評価です。<br>・普通に受けたら１色下がると思います。5時間コンテストはおよそコンテスト3回分であり、3回分のレート補正値は500近くあるので。<br>・それでも一発受験で認定出来るのが大きなメリットだと思ってます。</p>&mdash; chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) <a href="https://twitter.com/chokudai/status/1196371845563346944?ref_src=twsrc%5Etfw">November 18, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

2019年のつぶやきなので、今のレベルとは異なるかもしれませんが。

また、ターゲットはどちらかといえばAtCoderの非参加者だって投稿もありました。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">昨日偶然アルゴリズム実技検定の話を見たんだけど、「お布施以外に受ける意味がない」というのは、AtCoder参加者についてはその通りで、どちらかというとAtCoder非参加者がターゲットだよ。レーティングを持ってない人が、レーティングと同等の価値の資格を取ることで代替できるよ、ってコンセプト。</p>&mdash; chokudai(高橋 直大)🍆@AtCoder社長 (@chokudai) <a href="https://twitter.com/chokudai/status/1505408225646063617?ref_src=twsrc%5Etfw">March 20, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

[第3回アルゴリズム実技検定（PAST）結果発表　〜5087名が受験〜](https://prtimes.jp/main/html/rd/p/000000028.000028415.html)で第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からです。

## 現時点で公開されている過去問題

- [第1回](https://atcoder.jp/contests/past201912-open)
- [第2回](https://atcoder.jp/contests/past202004-open)
- [第3回](https://atcoder.jp/contests/past202005-open)
- [第4回](https://atcoder.jp/contests/past202010-open)
- [第5回](https://atcoder.jp/contests/past202012-open)
- [第6回](https://atcoder.jp/contests/past202104-open)
- [第7回](https://atcoder.jp/contests/past202107-open)
- [第8回](https://atcoder.jp/contests/past202109-open)
- [第9回](https://atcoder.jp/contests/past202112-open)
- [第10回](https://atcoder.jp/contests/past202203-open)
- [第11回](https://atcoder.jp/contests/past202206-open)

第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点)

- [問題はこちら](https://atcoder.jp/contests/past202206-open/tasks/past202206_a)

```
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点)

- [問題はこちら](https://atcoder.jp/contests/past202206-open/tasks/past202206_b)

```
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点)

- [問題はこちら](https://atcoder.jp/contests/past202206-open/tasks/past202206_c)

```
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](https://qiita.com/organizations/supership-inc)を合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方は[Supership株式会社 採用サイト](https://supership.jp/recruit/)よりご確認ください。

是非ともよろしくお願いいたします。