はじめに 本記事は、競プロアドベントカレンダー2020 の12/15分の記事です。ネタに困っていたんですが、Twitter上でクエリ平方分割に関する記事がほとんどないという声を見て、殴り書きではありますが本記事を作成することにしました。易しい問題を例にクエ…

公式解説とは異なる、経路数を考えることによる導出を紹介する。 考察 とりあえず、各を固定して考えよう。というのは、縦がマス、横がマスのグリッドにおいて、左下から右上に右移動と上移動だけで向かうときの経路の数に等しい。この値を掛け算するので、…

idsigmaです。HUPC2020 Day3の運営側の感想を書いていきます。 ちなみに解説リンクは以下になります。 https://drive.google.com/drive/folders/1zkt1cO4580zyypgXHAyxdIxiBBRM7TbZ?usp=sharing A この位置に何置くか難しいよね 大学合宿をテーマにしてみた …

公式解説とは異なる解法を紹介。典型的な考え方を知っていると頭をあまり使わずに済むかも。 問題 atcoder.jp 考察と解法 とりあえずを止めておく。区間]と重なる名産品の区間の数が答えなわけだが、異なるの値について同じ区間が重なると数えるのが面倒であ…

ある意味有名な(?)問題。解説と少し違ったので思うので書いてみる。 問題 atcoder.jp 考察 とりあえず、xorと和の関係を表す式であるところのを書いてみる。この式は、2つの自然数の足し算というのは、桁ごとの和(xor)と繰上がりに分解できるということを言…

解けたけど、コンテスト中のACは遠い...。 問題 codeforces.com 考察と解法 期待値の代わりに総和を考えることにする。スコアが和の形をしているので、2つの数の積が足される集合はいくつあるかを考えよう(0-indexedとする)。といってもこれは簡単である。あ…

こういうやつの定跡を知っているかが重要そう。 問題 onlinejudge.u-aizu.ac.jp 解法 木から頂点を取り除いていくので、森を扱うことになる。森の連結成分の数は、頂点の数から辺の数を引いたものである。これは期待値にしても変わらず(期待値の線形性)、を…

これが解けないのは悔しいんだけど、まあ難しいね...。 問題 codeforces.com 考察と解法 まず、どの3つのスイッチを取っても、その3つに関わるランプは存在しないという条件に注目する。これは、各ランプについて、押すと影響のあるスイッチは高々2つしかな…

こういう非自明な例が出てくると理解が進んで助かる。(間違ってたら教えてください) 問題 B - Hawker on Graph 解法 解説の議論を追っていくことにしよう。 単に足していくだけだったら... まず最初に、重みの辺を通るごとに所持金がだけ増え、負になること…

遅延セグ木で殴るのは、気持ちがいい。 問題 https://codeforces.com/contest/1285/problem/E 解法 座標について、その座標を覆う区間の数をとする。求めるものは、(考えるべき座標の両端のの値が0であることにすると)上でが連続している部分(つまり区間)の…