LowLinkを実装してみた。自分用の詰まった部分のメモも含む。 どういう問題をやるの グラフが与えられて 関節点 その点を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる) 橋 その辺を取ってしまうと、グラフの連結成分は増えてしまう(バラ…

ABC273-E 問題概要 クエリが$ Q $個、以下の形式で与えられ、最初は空列を1つ持ち、$ 10 ^ 9 $ページあるノートの各ページには空列が初めから入っている。 ADD x 列にxを末尾に追加する。 DELETE 列の末尾から1つ削除する。空列の場合は何もしない。 SAVE x …

ABC277-D 概要 カードが$ N $枚で$ A _ i $である。最初はすべて手札。次のようなことをして、手札に残るカードの和を答えよ。 手札からカード1枚を選ぶ。 次の行為を好きなだけ繰り返す。 場にあるカードの値が$ X $なら、元のカードを捨てて、$ X $か$ (X …

Notionで造ろうと思ったけどNotion操作下手なんで...... Diffは下位はマイナス、中位は無印、上位は+をつける。具体的な境界はない。 木系 Title Diff タグっぽいの 簡単な説明 ABC202-E Blue- 木 クエリ 先読み 木の上のオイラーツアー(記事に詳細ある) Low…

ABC202-E 問題概要 サイズ$ N $の木が与えられる。次のクエリを$ Q $個処理せよ。 $ U, D $という値が与えられる。頂点$ U $を取って、根から距離が$ D $の頂点の個数を答えよ。 制約: $ N, Q \in [2, 2 \times 10 ^ 5], U \in [1, N], D \in [0, N - 1] $ …

ABC202-E 問題概要 サイズ$ N $の木が与えられる。次のクエリを$ Q $個処理せよ。 $ U, D $という値が与えられる。頂点$ U $を取って、根から距離が$ D $の頂点の個数を答えよ。 制約: $ N, Q \in [2, 2 \times 10 ^ 5], U \in [1, N], D \in [0, N - 1] $ …

6th editionについての解答。 解答がおかしいとかがありましたらSen(@nonpro3)のTwitterアカウントにDMやリプライ飛ばしてください。 大体ここにある。ほとんどそろっている。先駆者様ありがとうございます！ 上で事足りると思うが、ここにもあるよ！ ただし…

第1章 第2章

6th editionについての解答。 解答がおかしいとかがありましたらSen(@nonpro3)のTwitterアカウントにDMやリプライ飛ばしてください。 大体ここにある。 ただし、これは最新の6th editionではないので、下に対応表と乗ってない問題の回答を載せる。 6th editi…

Androidアプリの開発で、ListViewにCheckBoxやButtonを入れて、OnItemClickListenerを設定したが働かないという問題にであいました。 結構な既出問題でしたが、日本語情報ではなかなか十全な記事がなかったです。そして、自分のFocus、TouchModeの理解なども…

https://atcoder.jp/contests/abc194/tasks/abc194_e 問題概要 $ mex(a, b, c\cdots) $は$ a, b, c\cdots $のうちに含まれていない、最小の0以上の整数とする。 数列$ {A _ i} $と$ M $が与えられる。すべての$ A _ i $の連続した$ M $個の部分について、そ…

先日のABCで中国剰余定理による連立合同式が出たことでまた冷えたのでこれをきっかけに中国剰余定理を勉強しました。

https://atcoder.jp/contests/abc189/tasks/abc189_f 概要 マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。 マス目$…

https://atcoder.jp/contests/abc191/tasks/abc191_f 概要 黒板にN個の数字${A[i]}$が書かれている。以下の操作をN-1回行って、最後に残った数は何通りあるでしょう？ 2つの数字$a, b$を選び、それらを黒板から消す。代わりに、$\min(a, b)$もしくは、$\gcd(…

https://atcoder.jp/contests/arc112/tasks/arc112_c 概要 サイズがNの根付き木が与えられる。木の根は頂点1。 AliceとBobはこの木でゲームをする。 木の各頂点には最初はすべてコインが1枚ずつ置かれている。最初に駒を用意し、頂点1(根)に置く。手番はAlic…

https://atcoder.jp/contests/abc191/tasks/abc191_d 概要 座標平面上で、$ (X, Y) $中心で半径が$ R $の円の内部や辺上に、何個の格子点(座標がすべて整数の点)がある？ 制約：$ 0 \leq |X|, |Y|, R \leq 10 ^ 5 $。$ X, Y $は小数点以下4桁まで与えられる …

https://atcoder.jp/contests/abl/tasks/abl_f 問題概要 $ 2N $人の人がいて、それぞれ身長が$ h[i] $である。 この人たちで、ペアを$ N $組作っていく。(任意の人は1つのペアにしか属してはいけない) ここで、すべてのペアのうちの2人で、お互いの身長が異…

https://atcoder.jp/contests/arc059/tasks/arc059_c 問題概要 N人の子どもがいる。それぞれ、はしゃぎ度という整数値A[i]があるとする。 この時、それぞれの子どもが飴をB[i]個もらっているとき、全体の活発度は以下のように求められる。 $$ \Pi _ {i = 1} …

この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$ 10 ^ 9 + 7 $じゃダメなのか 原始根って何？ とかについてもこれを…

atcoder.jp 概要 以下の問題がTケース与えられるので、それについてT回回答すること。長さNの配列{A_i}が与えられる。そして、もう1つ長さNの文字列Sが与えられ、それは0と1のみに構成される。0さんと1さんの2人はこの数列を使って、次のようなルールでゲー…

自分向けのメモ。たぶん新入生教育にも開発仲間にも役に立ちそう。(あくまで自分向けのsummaryだが)動的な部分 sen-comp.hatenablog.com

https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b 概要 長さNの数列{a}が与えられる。K あなたは次の操作を好きな回数だけ行うことができる。 連続するK項を選び、それらの値をすべて0にする。 この時数列{a}…

atcoder.jp 概要 N , Bで、次の条件を満たすようなものが何通りあるかを求めよ。ただし、非常に大きくなる場合があるので、で割ったあまりを求めること。 AとBの要素は、[1, M]の任意の整数 A[i] != B[i] (1 A[i] != A[j] (1 つまり、同じindexでのAとBの要…

atcoder.jp 概要 N個の文字列S[i]が与えられる。それぞれのS[i]は'(' or ')'で構成されている。これらの{S}を好きな順番でつなげ合わせた時、正しいかっこ列を作ることができるのだろうか？できるならYes、できないのならNo。制約： 1

atcoder.jp 概要 ある小文字アルファベットから構成される文字列Sが与えられる。これにK文字の任意の小文字を任意の位置にするとき、何通りの文字列が作れるのだろうか？制約：1 今回は自分用をメインに書いてるためかなり雑。わかりづらいかもしれない。

自分向けのメモ。たぶん新入生教育にも開発仲間にも役に立ちそう。(あくまで自分向けのsummaryだが)動的な部分 sen-comp.hatenablog.com

自分向けのメモ。たぶん新入生教育にも開発仲間にも役に立ちそう。(あくまで自分向けのsummaryだが) 静的な部分 sen-comp.hatenablog.com

F - Knapsack for All SubsetsABC実質初全完を祝って解説記事。 概要 長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。 f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とす…

atcoder.jp 概要 最初にx=0という数字を持っている。あなたは、次の操作のうち任意のものを任意の順番で、任意の回数回だけ行える。 (操作1)xを2xで置き換える。 (操作2)xを3xで置き換える。 (操作3)xを5xで置き換える。 (操作4)xを+1もしくは-1する。 操作1…

codeforces.com 概要 H*Wの盤面が存在していて、それぞれのマス(i, j)ごとにはa[i][j]という高さがある。 Senくんははじめ(1,1)にいて、(H, W)まで行きたい。(i, j)にいるとき、次に行ける場所は(i+1, j)と(i, j+1)のうち、高さが(i, j)よりちょうど1だけ高…