無料回だったので参加してみました。

結果

リアルタイム受験をしました。

結果は94点で、エキスパートに認定されました。やったね。

やったぜ#アルゴリズム実技検定 pic.twitter.com/hSCpQq6gqY
— takumi152 (@takumi152) 2020年5月23日

各問題を解くまでの時間はこんな感じでした（開始=13:00、終了=18:00）。

pic.twitter.com/EckIFHMMjf
— takumi152 (@takumi152) 2020年6月6日

以下に各問題について書いていきたいと思います。

※どう解いたかうろ覚えな状態で書いているので、説明が雑な部分があります。予めご了承ください

結果
A - ケース・センシティブ
B - ダイナミック・スコアリング
C - 等比数列
D - 電光掲示板
E - スプリンクラー
F - 回文行列
G - グリッド金移動
H - ハードル走
I - 行列操作
J - 回転寿司
K - コンテナの移動
L - スーパーマーケット
M - 行商計画問題
N - 入れ替えと並び替え
O - 輪投げ
最後に

A - ケース・センシティブ

問題文はこちら

文字列をそのまま比較した場合と、小文字に変換してから比較した場合を見るだけです。

ちなみにですが、最初はsameかdifferentを出せばよいと誤読して1WAを出しました（え？）

提出したコード(Python)はこちら

B - ダイナミック・スコアリング

問題文はこちら

序盤の重実装その1。

各参加者がどの問題を解いたかと、各問題の現在の得点を管理すればよいです。

提出したコード(Python)はこちら

C - 等比数列

問題文はこちら

$R = 1$ なら $A$ をそのまま出力するだけです。

$R \ge 2$ なら愚直にやって、答えが $10^9$ を超えたらその時点で計算を打ち切ればよいです。

ループ回数は高々 $\lceil \log_{2}{10^9} \rceil = 30$ 回程度なので、十分間に合います。

提出したコード(Python)はこちら

D - 電光掲示板

問題文はこちら

序盤の重実装その2。

サンプルから各数字の見本を持ってきて、見本の状態と現在見ている数字の状態が全て一致しているかどうかを確認しました。

提出したコード(Python)はこちら

E - スプリンクラー

問題文はこちら

問題文の通りにグラフを作って解くだけです（雑）

$N, Q \le 200$ なので、愚直に $O(NQ)$ で解いても十分間に合います。

提出したコード(Python)はこちら

F - 回文行列

問題文はこちら

行列の $i$ 列目と $N-i$ 列目の両方に存在する文字があるかどうかを調べればよいです。

setで出現した文字を管理すれば $O(26 \cdot N^2)$ ～ $O(26 \cdot N^2 \log{N})$ 程度ですが、愚直に全ての組を調べても $O(N^3)$ なので間に合うと思います。

提出したコード(Python)はこちら

G - グリッド金移動

問題文はこちら

最初の位置からBFSをすれば解くことができます。が、負の座標が存在するので少し厄介です。

自分の場合は、全ての座標を+1000だけずらしてからやることで負の座標を気にする必要が無くなると思ったので、そうしました。

提出したコード(C++)はこちら

H - ハードル走

問題文はこちら

各行動を行った後、位置 $L$ まで到達するのに必要な最小時間をDPで求めればよいです。

$dp[i] := (位置iに到達するのに必要な最小時間)$ 、 $h[i] := (位置iにハードルが存在するかどうか)$ とすれば、遷移式は次のようになります。

$dp[i+1] = \min(dp[i+1], dp[i] + t1 + (h[i+1] ? t3 : 0))$ （行動1を行った場合）
$dp[i+2] = \min(dp[i+2], dp[i] + t1 + t2 + (h[i+2] ? t3 : 0))$ （行動2を行った場合）
$dp[i+4] = \min(dp[i+4], dp[i] + t1 + t2 * 3 + (h[i+4] ? t3 : 0))$ （行動3を行った場合）

ただし、空中にいる状態でゴールする場合（行動2や行動3を行っている途中で位置 $L$ に到達する場合）があるので、そこの場合分けが必要になります。この場合の遷移式は、

$dp[L] = \min(dp[L], dp[i] + t1 / 2+ (t2 / 2) * ((L - i) * 2 - 1)$

となります。

提出したコード(C++)はこちら

I - 行列操作

問題文はこちら

行列の現在の行と列の並び順を管理すればよいです。

また、転置の操作も存在しますが、これは行と列が入れ替わるという操作なので、

転置が行われた回数が偶数の場合は行（または列）に対する操作をそのまま行って、
奇数の場合は行（または列）に対する操作の行と列を入れ替えて操作を行う

とすればよいです。

提出したコード(C++)はこちら

J - 回転寿司

問題文はこちら

便宜上、まだ寿司を1つも食べていない子供が食べた寿司のおいしさの最大値を $0$ とすると、

子供が食べた寿司のおいしさの最大値は、常に降順になっている

という性質があります。

これは、ある子供（ $a$ とする）が食べた寿司のおいしさの最大値が、その前の子供（ $b$ とする）が食べた寿司のおいしさの最大値よりも大きいと仮定すると、 $a$ が食べた寿司の中でおいしさが最大のものは $b$ が食べているはずなので矛盾する、という背理法的なやり方で示すことができます（本番では~~もちろん~~無証明で、多分そうだろうなと信じてやりました）。