第一回 アルゴリズム実技検定
AtCoderが開催しているアルゴリズム実技検定 (PAST) というものがある。 今回はお金を払って検定として受けることはしなかったが、開催期間が終了し問題が公開されているので、少しずつ解いている。
やってみると解き方はわかって実装できたものの、WAやREに悩まされるパターンが何度かあり、詰まった部分について書いておく。
E - SNS のログ / Restore
「フォローフォロー」でユーザa自身を除くのを忘れて、WAの嵐に遭う。
H - まとめ売り / Bulk Selling
偶数と奇数に分けて管理する。 さらに「セット販売」と「全種類販売」については在庫を減らしていると計算量が大変なことになるので、別でカウントしておいて毎回在庫量から引いて計算するようにする。 あとは偶数と奇数の最小値をそれぞれ記録しておけば、各クエリで在庫が足りるかどうかを判断できる。 計算量はO(max(N, Q))となる。
自分は配列を0-originのまま実装してしまい、偶奇判定やカード番号と配列インデックスの変換でだいぶ辛いことになったので、この問題については0番目要素を追加してインデックスを揃えるのがいいのかも。
n = 1の場合については場合分けしておかないと、偶数のカード集合が空になってしまいREの原因になる。
所感
Iまで解いた感想としては、実装に迷うことがなくても細部の条件で弾かれることが多かった。 基本的なことだが、問題分をきちんと読まないといけないと再認識した。
