mod素数の逆数 $10^{9} + 7, 998244353$は素数． 素数$p$に対し，$X/ Y \pmod p=$(X * pow(Y, p - 2, p)) % p 【背景】 $p$を素数，$a$を$p$の倍数でない整数とすると\begin{aligned} a^{p-1} \equiv 1 \pmod p \end{aligned}が成り立つ（フェルマーの小定理…

解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，再帰的に計算できる． 回答例 import sys sys.setrecursionlimit(10 ** 6) from functools import lru_cache N, P = map(int, input().s…

考え方 回答例 考え方dp[i][j][k] = i個目までみてj個和をとったときのk (mod D)の最大値．回答例dのループ範囲に注意． N, K, D = map(int, input().split()) A = list(map(int, input().split())) dp = [[[-1] * D for _ in range(K + 1)] for _ in range(…

解法1： 考え方 回答例 解法2：二分探索 & ルジャンドルの定理 考え方 回答例 解法1：考え方Editorial - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280)素因数分解：Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめ…

考え方 回答例 考え方行列を転置→ソートして一致するかどうかを見れば良い． Pythonではリストの転置をzipを使って簡単に表現できる： Pythonで転置行列 - 競プロはじめました回答例 H, W = map(int, input().split()) S = [list(input()) for _ in range(H)…

連続部分文字列が含まれるかどうかの判定文字列Sに文字列Tが連続部分文字列として含まれるかどうか： if T in S: (処理) (【参考】Editorial - TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279))例題 B - LOOKUP

数列→順列の辞書順で何番目か 順列の辞書順で何番目か→数列 数列→順列の辞書順で1つ前の数列 例題 数列→順列の辞書順で何番目かEditorial - AtCoder Beginner Contest 276の方法です．数列$S = (S[0], S[1], ..., S[N])$が順列の辞書順で何番目かを返す関数…

考え方 回答例 考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，普通のDP．回答例dはゴールまでの距離． nxt(次の位置) = move(今いる位置，出目) dp[i回目に][位置jにいる] 確率． N, M, K = map(int, input().split()) mod = 998244353 i…

考え方 回答例 考え方メモ化再帰する．Pythonではlru_cacheで簡単に実装できる． functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.11.0b5 ドキュメント AtCoder - 解法パターンの整理 - 競プロはじめました 回答例 from functools impor…

Decimal 例題 自分で実装する 例題 参考記事 Decimaldecimal --- 十進固定及び浮動小数点数の算術演算 — Python 3.10.6 ドキュメント例題B - Broken Rounding from decimal import Decimal, ROUND_HALF_UP X, K = map(int, input().split()) for i in range(…

周回回数を効率的に求め，残り$N$個以下になったら愚直に数えることを考える． 解法1：二分探索 考え方 回答例 解法2：シミュレーション 考え方 回答例 解法1：二分探索考え方Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginn…

考え方 回答例 再帰関数 DP的 考え方残り$n$ターンのときの期待値を$f(n)$とすると，\begin{aligned} f(1) &= \sum_{i = 1}^{6} i \times \frac{1}{6} \\ f(n) &= \sum_{i = 1}^{6} \max\Bigl(i, f(n - 1) \Bigr) \times \frac{1}{6} \end{aligned}回答例再…

考え方 回答例 参考 考え方Editorial - AtCoder Beginner Contest 272 $N$個の整数に含まれない最小の非負整数は$0,1,...,N$のいずれか．各$i$を考える．$m$回目の操作のあとで$A_{i} \in [0, N]$となる$m$の個数は，\begin{aligned} & 0 \leq A_{i} + m i \…

考え方 回答例 考え方原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷…

考え方 回答例 考え方dp[i][j] = iコ目まですべてを使ってjにできる方法（HとTの文字列）．i + 1に遷移できるためには，dp[i][]が$i$コの文字列からなる必要がある．回答例初期化ではダミーの文字$X$を入れることで，遷移できるものを区別した． N, S = map(…

解法1：二分探索 考え方 回答例 解法2：消費する本の数に着目 考え方 解法1：二分探索考え方「$x$巻まで読むことができる」は， $x$巻以下で持っている本の種類の数 (↑以外の本の数) // 2 の和が$x$以上であることと同値．Editorial - KYOCERA Programming C…

考え方 回答例 考え方「$\mathrm{dp}[n] = n$個から開始したときの答え（先手が取れる最大数）」とすると，（$A_{1} = 1$よりすべての石を取り尽くすことでゲームが終了するので）後手が取る石の個数は$n - \mathrm{dp}[n]$となる． $n$個ある状態で，はじめ…

考え方 回答例 考え方以下を愚直にやってみた． 計算をミスらないように実装するのが大変．．．アライグマ「F問題は算数なのだ……。行ごとの和を考えると、奇数行目と偶数行目がそれぞれ等差数列になってるから、和の公式を使ってO(1)で求められるのだ！」htt…

考え方 回答例 考え方すべての点の組み合わせをみて，隣接しているものをUnionFind（UnionFind木 - 競プロはじめました）でマージすれば良い．2点$(x_{1}, y_{1}), (x_{2}, y_{2})$の隣接条件は\begin{aligned} \begin{cases} \, \max(|x_{1} - x_{2}|, |y_{…

考え方 回答例 考え方$i$軸のうち，どの$j$座標にもルークが含まれないのは1つだけである．したがって，「$(A, B, 1, N)$を聞いたときに$B - A - 1$が帰って来ること」が「$A \leq X \leq B$」の必要十分条件である．よって，二分探索で$X$を求めることがで…

考え方 回答例 考え方コスト最低の頂点から消す． 隣接頂点に対し，消した頂点の分のコストを修正してpushする． （ダイクストラに似ている）回答例 from heapq import heappop, heappush N, M = map(int, input().split()) A = list(map(int, input().split…

考え方 回答例 考え方dp[i][j]=$i$コ目まで決めて，$j$コ選んだ場合の最大値．回答例 N, M = map(int, input().split()) A = list(map(int, input().split())) dp = [[-1<<60] * (M + 1) for _ in range(N + 1)] dp[0][0] = 0 for i in range(N): for j in r…

考え方 回答例 考え方\begin{aligned} &\sum_{i = 1}^{M} i \times A_{k + i} \\ &=\sum_{i = 1}^{M} (k + i) \times A_{k + i} - k\sum_{i = 1}^{M} A_{k + i} \end{aligned}だから，累積和を2種類計算しておけば良い．回答例 N, M = map(int, input().spli…

考え方 回答例 考え方言われたことを愚直にやる．回答例 S = list(input()) row = [[7], [4], [8, 2], [5, 1], [9, 3], [6], [10]] if S[0] != '0': exit(print('No')) for i in range(7): if all(S[x - 1] == '0' for x in row[i]):continue for j in range…

考え方 回答例 考え方dpを使うことはわかる．ただし，（座標範囲がデカ過ぎるため）座標をindexにしたdp[x][y]は使えない．「3通りの移動の仕方を何回ずつ選んだか」が「最終的な座標」と1対1対応するので，これをindexとして使えばよい．回答例次がキレイ S…

解法：しゃくとり法 考え方 回答例 解法：累積和（+set） 考え方 解法：しゃくとり法考え方3回のしゃくとり法で，$x = P, Q, R$に対し 区間和が$\sum_{[l, r)} A_{l} = x$を満たす$l$の集合$S_{x}$ $l$を$r$に対応させる辞書$f_{x} (l)=r$ を求めておく．Yes…

解法1 考え方 回答例 解法2：BFS 考え方 回答例 解法1考え方頂点を大きい方から見ていけば，「各街から到達できる街での最高値」がわかる． 求めたい答えは，「(街$i$から到達できる街での最高値) - (街$i$での購入価格)」．回答例 N, M = map(int, input().…

考え方 回答例 考え方「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．UnionFindの初期化では， すべての発電所をつなぐ イベントで切られない辺をつなぐ とすればよ…

よく使う距離について．検索すれば，わかりやすい図が出てくる． Euclidean vs Manhattan vs Chebyshev Distance例チェビシェフ距離（チェス盤距離）B - Nice Grid

方法1：転倒数 考え方 回答例 方法2：BFS 考え方 メモ 方法1：転倒数考え方最近，以下の出題があったので，「転倒数」が最初に浮かんだ． ABC261F - Sorting Color Balls - 競プロはじめました「自分より小さいのに自分よりあとに現れる数」の（すべての「自…