[AtCoder] ABC 187 C – 1-SAT
英小文字からなる文字列を \( t \) として、\( S_i = t \wedge S_j = !t\) を満たすような \( i, j \) が存在するとき \( t \) は不満な文字列となります。したがって、\( ! ...
[AtCoder] ABC 186 E – Throne
王座の座席番号を \( 0 \) とします。移動した回数を \( x \) と置くと、\( x \) 回移動したときの座席の位置は \( (S + Kx) \bmod N \) となるので、
\
を求め ...
[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 \) とすると、
[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 ...
[AtCoder] ABC 009 C – 辞書式順序ふたたび
\( T_i \) の先頭から貪欲に辞書順の最小の文字から構成できるかを調べます。これは文字の頻度を管理することで、高速に計算することができます。文字列 \( S \) の \( i \) 文字目から \( j \) 文字目ま ...
[AtCoder] ARC 110 C – Exoswap
\( 1 \) から \( N \) まで順番に交換ソートしていくことを考えます。自然数 \( i \) がどの場所にいるかという配列を管理することで効率よくソートできます。
コード#include <bits/s ...
[AtCoder] ARC 110 B – Many 110
\( N \geq 4 \) について考えます。\( S \) に \( T \) が含まれる場合、\( T \) は、
\
のどれかである必要があります。これらは、\( 110, 101, 011\) ...
[AtCoder] ARC 110 A – Redundant Redundancy
結論からいうと、\( 2 \) から \( N \) までの最小公倍数を \( l \) とすると、\( l + 1 \) となります。以下では、このように考えつかなかった場合を考えます。
\( N! + 1 \) ...