「ABC 401-500/ABC403C - 403 Forbidden」の編集履歴（バックアップ）一覧はこちら

「ABC 401-500/ABC403C - 403 Forbidden」(2025/05/16 (金) 00:50:15) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

#contents
----

*問題
[[ABC403C>>https://atcoder.jp/contests/abc403/tasks/abc403_c]]
元ネタは、[[RFC9110で規定されるHTTPコード>>https://ja.wikipedia.org/wiki/HTTP%E3%82%B9%E3%83%86%E3%83%BC%E3%82%BF%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89]]の[[403 Forbidden>https://ja.wikipedia.org/wiki/HTTP_403]]。

*必要知識
B以下レベルの内容は省略
-[[set]]

*考え方
単純にやると、N×Mのbool型二次元配列を用意することになるが、NやMの値が大きくてTLEしてしまう。
そこで、権限がないものについてはわざわざデータを用意せず、「権限があるという情報がなければ権限がないと判断する」という方針を取ることで高速化する。

権限があるものだけを管理するには、飛び飛びの値を管理するのが得意なmapやsetなどを用いるのがよい。
今回は同じ人に複数の権限が与えられる可能性があるので、mapでは難しい。
vector<set<int>>かset<pair<int,int>>を使うのがよい。

クエリ2で全体権限を与える場合に、個別ページ全部に権限を与えていくと、クエリ2を連打される最悪の入力に対してQ×Mの処理時間がかかってTLEする。
全体権限は全体権限として管理し、クエリ3のときに「個別ページ権限か全体権限があればOK」と判断する。

*解答例
[[解答例>>https://atcoder.jp/contests/abc403/submissions/65814151]]

*注意点

*別解

#contents
----

*問題
[[ABC403C>>https://atcoder.jp/contests/abc403/tasks/abc403_c]]
元ネタは、[[RFC9110で規定されるHTTPコード>>https://ja.wikipedia.org/wiki/HTTP%E3%82%B9%E3%83%86%E3%83%BC%E3%82%BF%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%89]]の[[403 Forbidden>https://ja.wikipedia.org/wiki/HTTP_403]]。

*必要知識
B以下レベルの内容は省略
-[[set]]

*考え方
単純にやると、N×Mのbool型二次元配列を用意することになるが、NやMの値が大きくてTLEしてしまう。
そこで、権限がないものについてはわざわざデータを用意せず、「権限があるという情報がなければ権限がないと判断する」という方針を取ることで高速化する。

権限があるものだけを管理するには、飛び飛びの値を管理するのが得意なmapやsetなどを用いるのがよい。
今回は同じ人に複数の権限が与えられる可能性があるので、mapでは難しい。
vector<set<int>>かset<pair<int,int>>を使うのがよい。

クエリ2で全体権限を与える場合に、個別ページ全部に権限を与えていくと、クエリ2を連打される最悪の入力に対してQ×Mの処理時間がかかってTLEする。
全体権限は全体権限として管理し、クエリ3のときに「個別ページ権限か全体権限があればOK」と判断する。

*解答例
vector<set>でやる場合　[[解答例>>https://atcoder.jp/contests/abc403/submissions/65814151]]
set<pair>でやる場合　[[解答例>>https://atcoder.jp/contests/abc403/submissions/65814280]]

*注意点

*別解