はてなブックマーク

E.Simple String Queries 問題ページ 難易度 : 1443 考察 type1 は 一点更新、type2は 区間取得 問題です。したがって、このクエリを高速に処理するためには Segment Tree を利用するのが良さそうです。 あとは、区間に登場するアルファベットの種類をどうやって管理するかを考えます。これにはいくつかの手段があります。 解法➀ アルファベットごとにセグ木を持つ 欲張って全てのアルファベットについて同時に考えようとするから状況が難しくなっています。 それよりも、アルファベットごとに独立に考えるほうが簡単です。つまり、区間 $[l,r)$ 内に対象のアルファベットが含まれるか(存在するか) を求めることにします。 そのためにはアルファベットごとに管理仕分ける必要があるので、26本のセグメントツリーを作成します。 $S[i] = a $ なら $a$ に

ABC 254 のA,B,C,D,E問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。 この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。 また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。 質問やご指摘はこちらまで Twitter : Waaa1471 作者プロフィール Atcoder ：緑色 882 20221231 現在 目次 はじめに A.Last Two Digits B.Practical Computing C.K Swap D.Together Square E.Small d and k はじめに 特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的