https://leetcode.com/contest/weekly-contest-134/problems/escape-a-large-maze/2次元グリッドがある。 縦も横も10^6である。 通れないマスの集合blockedが与えられる。 始点sourceから終点targetへ隣接するマスを移動して、到達可能か判定せよ。0≦blocked…

https://leetcode.com/contest/weekly-contest-134/problems/uncrossed-lines/2つの配列A,Bがある。 各配列の要素を横一列に並べる。 A[a]=B[b]となっている要素を直線で結ぶ。 直線が公差しないように結んだときの直線の最大数は？1≦配列サイズ≦500 1≦A[i],…

https://leetcode.com/contest/weekly-contest-134/problems/coloring-a-border/2次元グリッドがある。 各要素には数が書いてある。 同じ数で隣接している要素は連結成分になる。 ある要素(r0,c0)に色colorを使って数を変更する。 (r0,c0)と連結な成分の要素…

https://leetcode.com/contest/weekly-contest-134/problems/moving-stones-until-consecutive/数直線の上に3つの石がある。 3つの石がa,b,cの位置にある。 以下の操作を任意回できる。 「石がx＜y＜zの位置にあるときに、x,zの石をxとzの間の空いている位置…

https://yukicoder.me/problems/no/823 前提知識 二項係数mod素数 解説 こういう系に初めて取り掛かる人はどこから手をつけていいか分からないと思うが、 まずは弱そうな条件を探してみる。 見ると、入力がN≦10^5となっている。 しかも、得点の計算方法がマ…

https://yukicoder.me/problems/no/822 解説 https://yukicoder.me/submissions/343382よくよく考えると、(x,y)のペアは全探索ができる量である。 まず、xは[0,2^17)の範囲で考えればいい。 これは、2^17=131072であり、2進数表記すると1000000000000となる…

https://yukicoder.me/problems/no/821 解説 https://yukicoder.me/submissions/343365☆の割には難しい問題に見える。順位表を見てみると、プロが5分とかで解いている。 ここから導けるのは、エスパーが必要であるということである。 プロが一瞬で思いついた…

https://yukicoder.me/problems/no/820 解説 https://yukicoder.me/submissions/343360パット見難しそうに見えると思う。 例えば、Nが3のときは、 1 2 3 4 5 6 7 8 となり、Kが2のときは、 4 8 となって、2が答え。 これは最大が8で4で割り切れる個数なので…

https://atcoder.jp/contests/abc125/tasks/abc125_d 解説 https://atcoder.jp/contests/abc125/submissions/5169416ときにはエスパー力も必要であると教えてくれる問題。 （証明の仕方を知らないので、エスパーと表現してるだけだけど） だいぶ自明っぽいエ…

https://atcoder.jp/contests/abc125/tasks/abc125_c 解説 追記: GCDの計算をO(1)で計上して書いてありますが、実際はO(log10^9)が最終的な計算量に追加されます。 今回はそんなに問題にならないですが、たまに事前計算とかでこの計算量も削る必要のある問題…

https://atcoder.jp/contests/abc125/tasks/abc125_b 解説 今回の問題は解法が2つあるので、どちらも紹介する。 解法2の方が計算量が軽くておすすめだが、 解法1の全探索もやり方としては必ず覚えておく必要がある。 解法1 : 全探索 https://atcoder.jp/cont…

https://atcoder.jp/contests/abc125/tasks/abc125_a 解説 https://atcoder.jp/contests/abc125/submissions/5169262何回ビスケットが生成されるかというのを考えると、T/A回になる。 実際は切り捨てなのだが、C++ではint/intは切り捨てしてくれるので、これ…