問題：D - Project Planning 解答：Submission #27305078 - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) 解法：何となく部署の人数が多い方から一人ずつ集めるとよさそうだが、a[i]を減らしていって新たにタイが発生するところからわ…

問題：F - Blocked Roads 解答：Submission #25886274 - AtCoder Beginner Contest 218 解法：各辺を除いて逐一最短経路の算出をやると、辺の数がN2のオーダーなので、例えばダイクストラならO(N3logN)で間に合わないっぽい。 ここで一つ最短経路が見つかっ…

問題：E - Safety Journey 解答：Submission #24919698 - AtCoder Beginner Contest 212 解法：DP。 dp[i][j]：i日目に都市jにいるときの場合の数とする。答えはdp[K][0]である。 Eを使える道の集合とする。 dp[i][j] = Σdp[i-1][k] ( (k, j) in E) = Σdp[i-…

問題：E - Stronger Takahashi 解答：Submission #24895895 - AtCoder Beginner Contest 213 解法：01BFSが使える。 移動先をdequeに格納する。通常の移動はpush_front、パンチ後の移動をpush_backするとよい。

問題：F - GCD or MIN 解答：Submission #20060874 - AtCoder Beginner Contest 191 解法： 「最終的に残る数」の構成 gcd(a, b) ≦ min(a, b) より、最終的に残る数はmin(A)以下である（以降min(A)をAminと呼ぶ）。また、あるAi1, Ai2, ..., Aixに対し、gcd(…

問題：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する。…