[AtCoder] ABC 186 E – Throne
王座の座席番号を \( 0 \) とします。移動した回数を \( x \) と置くと、\( x \) 回移動したときの座席の位置は \( (S + Kx) \bmod N \) となるので、
\
を求め ...
ユークリッド互除法
整数 \( a, b, n \) に次の一次不定方程式を満たす整数 \( x, y \) を求めます。
\
ここで、\( a., b \) の最大公約数を \( g ...
[AtCoder] ABC 186 D – Sum of difference
\
上式において、\( i = k \vee j = k\) となる \( k \ (1 \leq k \leq N)\) は \(N – 1\) 回現れます。つまり、\( A_k \) と固定したとき ...
[AtCoder] ABC 186 C – Unlucky 7
\( n \) 進数に変換したときに \( 7 \) が現れるかを見たいので、繰り返して剰余を計算すれば良いです。自然数 \(x \) を \( n \) 進数で表した時、各位の数字を \( a_i \) とすると、
[Codeforces] Codeforces Round #690 (Div. 3) E1. Close Tuples (easy version)
\
\( (1)\) を満たすような \( a_i, a_j, a_k \) は、\( i, j, k \) を交換することによって、\( i < j < k \) を満たすことができます。つまり、\( ...
[AtCoder] ABC 185 D – Stamp
数列 \( A_i \) の順序を変えても影響はないので、\( A_i \) を昇順に並び替えて考えます。\( k \) の最大値は、各マスの差の最小値なので、
\
となりますが、\( A_{1} \n ...
[AtCoder] ABC 185 C – Duodecim Ferra
鉄の棒を \( 12 \) 本に分割したとき、棒 \( i \) の長さを \( l_i \) とすると、
\
となります。ここで、\( a_i \) を非負整数として、\( a_i = l_i ...
[Codeforces] Codeforces Round #689 (Div. 2) B. Find the Spruce
高さが \( k \) の木を作れるかどうかは、連続する ‘*’ の数が分かればいいので、連続する ‘*’ を累積和を用いて数えます。あるマスから下に向かって順番に高さ \( k ...
[AtCoder] ABC 009 C – 辞書式順序ふたたび
\( T_i \) の先頭から貪欲に辞書順の最小の文字から構成できるかを調べます。これは文字の頻度を管理することで、高速に計算することができます。文字列 \( S \) の \( i \) 文字目から \( j \) 文字目ま ...
[Codeforces] Codeforces Global Round 12 C1. Errich-Tac-Toe (Easy Version)
市松模様はマス \( i, j \) の色を \( (i + j) \bmod 2 \) の値で分けていますが、この問題では \( (i + j) \bmod 3 \) の値で分けるようです。整数 \( k\) を \( k ...