AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）に参加しました。
結果
A,B,C,D問題の4問正解でした。
久々に4問解き切れた。
D問題の考察がちょっと間違っててWAだったけど、割とギリギリに勘違いに気づけて修正が間に合ったからなんとか解けた。
A - Odd Position Sum
数列が与えられるので奇数番目の項の値の和を答える問題。
何番目になんの数字が入力されたかを元に加算するしないを判断して、最終的に合計を出力すれば解ける問題。
A問題にしてはいつもよりちょっとだけ難しめ？
B - Four Hidden
ある文字列S（明示されていない）があって、そこから4文字だけ?に置き換えた文字列Tが与えられる。
また、別の文字列Uが与えられる。
この時UがSの部分文字列の可能性があるかどうかを判断する問題。
文字列Tの？となっている部分は無条件で一致していることにして、文字列Uが文字列Tの部分文字列かどうかを判定して答えれば良い。
文字数自体もそれほど大きくないので、 1文字ずつずらしながら順番に確認していけば良い。
C - 403 Forbidden
ユーザーがN人、権限がM種類ある。
この時3種類のクエリがQ個与えられる
- 人Xに権限Yを与える
- 人XにM種類の権限全部を与える
- 人Xが権限Yを持つかどうかを答える。
連想配列とかで人別権限別に権限を持っているかどうかを管理しつつ、 人別に全権限が付与されたかどうかのフラグを管理して解いていった。
権限を持つかどうかの判定は、全権限が付与されたかどうかと人Xが権限Yを付与されたかどうかのフラグを元に判定した。
クエリの数の制約的に各クエリを割と高速に処理しないとTLEになりそうな気がした。
人別権限別のフラグをあらかじめ2次元配列で管理しようとすると、制約上限的にメモリの上限を超えかねないなと思ったので、setの配列を用意して人Xに付与された権限をsetで管理することにした。
また、全権限を付与された際にsetにM種類の権限全部を追加していくとTLEすると思ったので、
全権限付与時は、全権限が付与されたかどうかのフラグを用意することにした。こうするとM回setに値を追加する処理が1回フラグを更新するだけで完了する。
D - Forbidden Difference
数列Aと非負整数Dが与えられるので条件を満たす部分数列Bを作成するために数列Aから最小でいくつ要素を削除すればよいかを答える問題。
条件
- すべての組み合わせで
とりあえず、Dが0の時は、数列Aに同じ値が2個以上有ってはいけないので、数列Aの要素数から数列Aの要素の種類数で引いた数だけ要素の削除が必要になる。
Dが0より大きい場合を考えると、
ある数字XとX+Dが数列Aにあったら、そのうちのどちらかは削除しないといけない。
どっちを消すのが良いかはすぐには判断できないし、X-D、X、X+Dがある場合は
X-D,X+D削除のパターンもあればX-D、XやX、X+Dを削除するパターンもある。
X、X+D、X+2D、・・・X+nDとD間隔の数値だけを考えればよくて、 X+1、X+2みたいな値はX、X+D、X+2D、・・・X+nDの中のどれを削除しようかなという問題には影響しない。
たぶんmod Dの値でグループ分けして考えれば良い。
とりあえず数列にはどの数字が何個あるのかをカウントしておいた。
私はX、X+D、X+2D、・・・の値が数列に存在するかどうかを確認しながら、 X+(n-1)D、X+(n+1)Dみたいに途中でX+nDがない部分をグループの切れ目としてグループ分けしていった。
あとはグループごとにDPでグループ内で条件を満たす状態にするには最小で何個要素の削除が必要かを計算して足していった。
