この記事は，以下から該当箇所を抜き出したものです：Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました （蟻本p. 114-）【注】Pythonでは繰り返し二乗法を実装しなくても，pow(base, exp[, mod])により，pow(base, exp) % modが効率よく計算…

解答の補足事項のみ書いておく．以下では，$l, m,n\in \mathbb{Z}$とする．はじめに$A_{i_{1}}$を選び，辺を張れるだけ張ったすると，$x$と同じ連結成分にできる頂点は\begin{aligned} & x + l A_{i_{1}} \pmod N \\ & \Leftrightarrow x + l A_{i_{1}} + m …

解法1. 式変形参考記事[1]の方法． すべての料理の集合を$\Omega$，先手が選ぶ料理の集合を$X$，後手が選ぶ集合を$Y$とする．先手が最大化したいのは\begin{aligned} & \sum_{i\in X} A_{i} - \sum_{i\in Y} B_{i} &= \sum_{i\in X} (A_{i} + B_{i}) - \sum_…

B - アリの高橋くん 考えたこともっと簡単な方法があるんだろうな，とは思いつつも，計算で解が出せるので解いてしまった．現在地$(x_{0}, y_{0})$を中心とする円で各辺に接するものの半径を求め，それらのうちの最小値が答えになる．隣り合う頂点の座標を$(…

E - Divide Bothもう少し簡単な類題で慣れないと解けないなぁ，という感想． とりあえず約数で考えて，余分なものを差し引いて最大公約数の寄与だけ取り出す方法は汎用性がありそう．考えたこと与えられている条件は $x,y$が互いに素ではなく 一方が他方の倍…

D - KAIBUNsyo考えたこと $A$を両端から，ペアとなる文字を中心に向かって順に見ていく． もし「異なる」場合は，その時点で置き換える． でできる．ここで問題になるのは，ある2つの数字を等しいとみなす処理を繰り返すため，「数字が異なる」という状態が…

C - Swappable考えたこと典型例としてまとめていた次がほとんどそのまま使える． AtCoder - 解法の整理 - 競プロはじめました上では$A_{i}=A_{j}$の個数を数えているのに対し，今回は$A_{i}\neq A_{j}$の個数を求める点が違う．よって，総数（$N (N - 1)/2$…

B - Savings考えたこと\begin{aligned} \sum_{i=1}^{k} = \frac{k(k+1)}{2} \end{aligned}だから，\begin{aligned} \frac{k(k+1)}{2} \geq N \end{aligned}を満たす最小の正整数$k$を求めれば良い．２次方程式\begin{aligned} & \frac{k(k+1)}{2} = N \\ &\L…

A - Maxi-Buying$\lfloor 1.08\times N\rfloor$は int(1.08 * N) 108 * N // 100 math.floor(1.08 * N) などで計算できる．

C - Many Formulas考え方文字列$S$の長さを$N$とすると，$N-1$箇所に$+$を入れる方法を全通り試せばよい．これはbit全探索で実現できる．最終的に求めたいのは総和なので， $+$の直後の文字列から次に$+$が出るまでの文字列を記憶し， $+$が出たら，それまで…