考え方 回答例 考え方A, B, Xは少なくとも1つの黒マスを含むため，A, BはXと必ず重なる． Xの左上のマスの座標を(9, 9)として，A, Bそれぞれの左上のマスが(0, 0)〜(19, 19)となる場合を全探索する．全部の黒マスを使ったかどうかをsetで管理する．回答例 HA…

解法1：DP 考え方 回答例 解法1：DP考え方dp[i][j] = i品目を食べて状態がj(0:お腹を壊していない/1:壊している)のときの食べた料理の美味しさの総和の最大値回答例 N = int(input()) XY = [list(map(int, input().split())) for _ in range(N)] dp = [[0]*2…

解法1：DP 考え方 回答例 解法1：DP考え方dp[i][j] = i個目まで決めて，capslockON(j=1), OFF(j=0)のときの最小値回答例 X, Y, Z = map(int, input().split()) S = input() dp = [[0]*2 for _ in range(len(S) + 1)] dp[0][1] = 1 << 60 for i in range(len(…

解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方$f(n)=$1から初めて最終的にピッタリ$n$になる確率． $n=1$：$f(1)=1$ $n\neq 1$：$\displaystyle f(n) = \frac{1}{6} \sum_{k} f(n/\!/k)$（$(n\% k =0$かつ$k \in \{1,2,\ldots,6\})$） $n\neq 1$…

考え方 回答例 考え方素数はエラトステネスの篩（ふるい）で列挙できる．$a^{5} $2^{2}\times 3 \times c^{2} \leq 10^{12}$より$c \leq 10^{6}/\sqrt{12} この範囲で全て調べれば良い．回答例 N = int(input()) MAX = 300000 prime = [] is_prime = [True] …

解法1 考え方 回答例 解法2：深さ優先探索 解法1考え方サイズ1のバツの中心をメモしておく．その後，それぞれの中心に対し，サイズがどれだけか調べる．回答例 H, W = map(int, input().split()) C = [list(input()) for _ in range(H)] N = min(H, W) ans =…

考え方 回答例 考え方隣接頂点との距離が1なので，BFSで最短距離を求められる． 最短経路問題 - 競プロはじめました各$p_{i}$からの各頂点の最短距離$d$を求めて，$d 各$i$について$p_{i}$からの最短距離が$d_{i}$に等しい頂点の集合をbとする．bがwhiteに包…

考え方 回答例 考え方両端にある0と1の位置を，二分探索の要領で隣り合うまで寄せていけば良い． 回答例 N = int(input()) zero = 1 one = N while one - zero > 1: mid = (zero + one) // 2 print('?', mid) ans = int(input()) if ans == 1: one = mid eli…

解法1：DP 考え方 回答例 解法2：再帰 考え方 回答例 解法1：DP考え方 後退解析をする（先手の勝ち負けが確定している最終状態から，逆に考えていく）． modの逆数：modの逆数 - 競プロはじめました youtu.be 回答例dp[i][j][k] = 先手がiにいて, 後手がjに…

考え方 回答例 考え方 余りだけを管理する． $10^n$の計算は，先に計算しておくか，繰り返し二乗法（繰り返し二乗法 - 競プロはじめました）を使う． ※Python の剰余演算子%は，除数（割る方の数）と同じ符号の結果を返す．回答例 from collections import d…