問題：F - Sugoroku2 解答：Submission #19664058 - AtCoder Beginner Contest 189 解法：M個以上の連続した「スタートに戻る」マスがあればゴールに到達不可能であり、その場合は-1を出力する。それ以外はゴールに到達可能となる。 期待値の独立性より、あ…

問題：E - Rotate and Flip 解答：Submission #19699054 - AtCoder Beginner Contest 189 解法：与えられた4種類の座標変換は、tT = [x, y, 1]に対し、3×3の行列Aを左から乗じることで計算することが出来る。具体的には下記の通りである。 [[0, 1, 0], [-1, …

問題：E - ∙ (Bullet) 解答：Submission #19557514 - AtCoder Beginner Contest 168 解法：美味しさA、香り高さBのイワシを(A, B)と表記する。 (0, 0)のイワシはどのイワシとも一緒にクーラーボックスに入れない。よって(0, 0)のイワシは別に考え、最終的な…

問題：F - Contrast 解答：Submission #19529927 - AtCoder Beginner Contest 178 解法：AとB合わせてN+1個以上含まれる数字がある場合は、どのように並べ替えてもAとBとでかぶる場所が生じてしまうためNoを出力する。実はそれ以外の場合はBを適切に並べ替え…

問題：C - Robot on Grid 解答：Submission #19484879 - KEYENCE Programming Contest 2021 解法：空白マスの取扱いが難しい。(1, 1)から(r, c)までの1つのパスを考える。通常このパスは1通りであるが、パス中に空白マスがある場合、この空白マスはXまたは(R…

問題：F - Rook on Grid 解答：Submission #19457973 - Panasonic Programming Contest (AtCoder Beginner Contest 186) 解法：右→下と動く場合と下→右と動く場合に分けて考える。 ①右→下と動く場合：各列ごとに最初に当たる障害物の行座標を覚えておき、そ…

問題：F - Close Group 解答：Submission #19455050 - AtCoder Beginner Contest 187 解法：元のグラフをG = (V, E)とする。S ⊂ Vに対し、f(S)を誘導部分グラフ(S, Es)に対する元の問題の答えとすると、f(S)はSが完全グラフ（すべての頂点間に辺が張られたグ…

問題：F - Close Group 解答：Submission #19454159 - AtCoder Beginner Contest 188 解法：解説どおりに逆から考える。下記が言える。 「+1, -1」、「-1, + 1」は意味がない 「+1,+1,/2」よりも「/2, +1」の方がお得 「-1,-1,/2」よりも「/2, -1」の方がお…

問題：B - Reversible Cards 解答：Submission #19370578 - AtCoder Regular Contest 111 解法：解説通り、カードに書いてある数字を頂点、カードの数字の組み合わせを辺とするグラフを考えるのがミソ。すると問題は各辺のうち片方の頂点に色付けし、色のつ…

問題：Aizu Online Judge 解答：Aizu Online Judge 解法：一点更新区間加算のセグメント木を使う。タイプ0のクエリ(u, v)は、オイラーツアーとセグメント木を対応させ、オイラーツアーでvが最初に出てくるところに+wし、最後に出てくるところの次で-wする。…