【AtCoder】アルゴリズム実技検定受けてみた

お疲れ様です。
しらせです。

新年あけましておめでとうございます。
今年もよろしくお願いいたします。

昨年12月の下旬に開催された「第一回 アルゴリズム実技検定」に参加してみました。
ちょっと遅いですがレビューを書いてみます。

もくじ

アルゴリズム実技検定とは

AtCoder株式会社が2019年12月から開催しているプログラミング能力を図るための実技検定です。
詳しくは、AtCoder株式会社の「AtCoder アルゴリズム実技検定」のページをご覧ください。

受験方法は2種類あり、全員同一の時間で参加するリアルタイム受験と、リアルタイム受験終了後自分で開始時間を選択して参加できる通常受験です。

仕事もしている傍ら、なかなか都合が合わない人もいると思います。
検定時間はいずれも5時間と長丁場ですが、開始時間を選べるのはうれしですね。

ここで注意なのが（もちろん検定ページにも記載はありますが）リアルタイム受験者と通常受験者で有利不利が発生しないよう、問題や内容に関する事についてはSNSも含めて指定された日時まで口外してはいけないルールになっています。

受験結果

いつものコンテストではC#を使っていたのですが、文字列の操作や大きな数値の計算、Linqを知らないなどで時間を使ってしまうことがネックでした。
そこで今回は志向を変えてPython3(3.4.3)で挑戦しました。

5時間みっちり使って回答に専念しましたが結果は…

「　初級　」

46点でした。

配点を見るとわかりますが、問題A～Fの6問が正解でした。（Gを解くかHを解くかブレているうちに時間が終わってしまいました。。。

第一回の過去問もすでに公開されていますので、内容についてはこちらから確認できます。
第一回 アルゴリズム実技検定 過去問

問題の手ごたえ

A - 2 倍チェック / Is It a Number?
入力値を文字コードに変換して比較すればOK
単なる文字列の操作。

B - 増減管理 / Up and Down
1つ前に入力された数値と今入力されている数値を比較するループを作ればOK
特に引っかかるポイントは無かった。

C - 3 番目 / The Third
入力された値を配列に入れて数値にしてソートするだけ。
ソートをどうやるか、言語によって変わる気がする。

D - 重複検査 / Duplicated?
１から順に格納された数値の１つが変わってしまっている問題。
順番もバラバラに入力されているのでちょっと面倒。
この辺りから問題の質が変わりました。
入力された数値を集合で考えないとダメですね。ここも選択する言語によって難易度が変わる気がします。

　＜私の考え方＞
　１．入力値をすべて数値にして配列に入れ、事前にソートしておく。ー配列A
　２．入力された値と同じ個数で１から順に正しく格納された配列を作っておく。ー配列B
　３．配列Aと配列Bが同じならCorrectを表示して終了。そうでなければ処理４以降へ
　４．配列Bから配列Aを引いた残りを求める（setを使って抜けている数値が出る）ーx
　５．配列Aの合計＋xの合計からから配列Bの合計を差し引くと配列Aに余分に追加されている数値が出る。ーy
　
E - SNS のログ / Restore
この問題は正直力業でした。
2次元配列を作ってフォローしている場合を1していない場合0としてifelif分岐で計算し尽します。
Pythonの配列初期化で時間をつぶすというミスをしましたが、引っかかるとすると「フォローフォロー」の処理かと思います。

自分がフォローしていないけど、今フォローしている相手がフォローしている人を1つのループでフォローの処理をしてしまうと、以下の制約に違反します。
「その時点でユーザ x がフォローしているすべてのユーザ (ユーザ a 自身を除く) をフォローする」
なので、フォローフォローの処理の際はいったん新たにフォローするユーザを数値2（仮フォロー）として設定し、最後の処理で数値1(フォロー）に変えるという手間がありました。

F - DoubleCamelCase Sort
正規表現の問題でした。
import re　の使い方を学びました。

G - 組分け / Division
H - まとめ売り / Bulk Selling
この2問を残して2時間弱の余裕があったのですが正解には辿りつけませんでした。

問題Gは行列？の問題でしょうか？数学を知らない私の頭では解にたどり着けませんでした。結局スキップしました。
問題Hにも1時間弱時間を使いましたが、テストケースの19番以降で時間超過になってしまいどうしても無理でした。

問題Hは1つの配列で処理すると時間が掛かるとわかったので途中で奇数と偶数用の配列を用意する方向にしました。
これで、セット販売の際には奇数の最小値（Min）を引っ張ってくるだけで計算が終わると考えました。

ですが、これでも実行時間超過でテストケースは満たせませんでした。

まとめ

アルゴリズム検定という名前だけあって、もっとソートアルゴリズムとか二分探索とか再帰とかを使うような問題を期待していたのですが、AtCoderのいつものコンテストみたいにプログラミングというかテクニックに偏っている気がして期待外れでした。（もしかしたら後半の問題で出ていたのかもしれませんが。
結局最後まで問題にたどり着けていないし実力が無いと言われればそれまでなのかもしれません。

あとは数学をちゃんと勉強していないとダメですね。
出直してきます(;^ω^)

受験された皆さん
おつかれさまでした。

以上
お疲れさまでした。

2020/01/07追記
認定証が届きました。