第四回アルゴリズム実技検定（A～L）

A - 中央値

解答：Submission #17975213 - 第四回アルゴリズム実技検定

解法：ソートして2番目のものを答える。解答はA, B, Cで出力する必要があるため、元の添え字を覚えておき、charとして出力する。

B - 電卓

解答：Submission #17976377 - 第四回アルゴリズム実技検定

解法：y = 0 ならERRORを先に出力してしまう。そうでない場合、100倍してintの切捨除算を行った後、double型で小数表示すればよい。計算誤差も大丈夫そう。

C - 隣接カウント

解答：Submission #17978357 - 第四回アルゴリズム実技検定

解法：#の数を愚直に数える。外側に1マスずつ.のマスを追加しておくと境界条件を減らすことができる。

D - 分身

解答：Submission #19195860 - 第四回アルゴリズム実技検定

解法：タイプAとタイプBの操作はそれぞれ結果が順番によらず回数のみによる。そのため(タイプAの操作回数, タイプBの操作回数)の操作回数の和の小さい順にBFSで実際に操作をシミュレーションすればよい。

E - アナグラム

解答：Submission #18024607 - 第四回アルゴリズム実技検定

解法：next_permutationを使い、文字列の並べ替え全てで条件に合致するかを確認する。

F - 構文解析

解答：Submission #18024607 - 第四回アルゴリズム実技検定

解法：mapを使って文字列ごとの出現回数を調査し、Ｋ番目に大きいものを解答すればよい。ただし、タイがある場合にはAMBIGUOUSを出力する。タイの判定方法は、K-1番目とK番目の文字列の出現回数が同じ、もしくはK番目とK+1番目の文字列の出現回数が同じ場合、かつその時に限りタイになるとすればよい。

G - 村整備

解答：Submission #18041579 - 第四回アルゴリズム実技検定

解法：#のマスごとに、そのマスを.に変えた場合に「全てのマスから全てのマスに行き来できるか」を確認し、行き来できたマスの数をカウントする。「」部分の確認は、.であるマスからDFSを開始し、1回の探索で全てのマスに行けることを確認すればよい。

H - マス目のカット

解答：Submission #18163458 - 第四回アルゴリズム実技検定

解法：先に正方形として抽出する範囲を決め、「その正方形の数字を同じ数字にするために変えるべき数字の最小値」がK以下である場合に、そのときの正方形の1辺の長さを出力すればよい。

解法：取りうる（連続した）添字集合を $S$ 、a[i]の合計を $Sum$ とすると、 $|2 \sum_{i \in S} ai - Sum |$ を最小化すればよい。これは連続した添え字のうち左端を固定すると右端はざっくり $\sum ai$ が $Sum/2$ 以下となるもの、または $\sum ai$ が $Sum/2$ より大きくなるものの2種類を調べればよく、これはしゃくとり法で実装できる。