[AtCoder] AGC 041 A – Table Tennis Training
両者の距離が \( 2 \) の倍数のとき、向かい合うように進む事が最適です。また、卓 \( 1 \) または \( N \) に留まり続けることは最適ではありません。
\( (B – A) \bmod 2 ...
[AtCoder] ABC 148 E – Double Factorial
\( N \) が奇数の場合、\( f(N) \) は奇数となるので、答えは \( 0 \) となります。ここで、\( N ! \) の末尾に続く \( 0 \) の個数を考えます。
これは、\( N! \) の ...
[AtCoder] ABC 148 D – Brick Break
どのようにブロックを叩いても不可能な数列は、数列の要素に \( 1 \) が無い場合です。それ以外の数列は、少なくとも \( N – 1 \) 個のレンガを壊すことで条件を満たします。最終的に条件を満たす数列は、\ ...
[AtCoder] ABC 148 C – Snack
必要なお菓子の数を \( n \) とすると、\( n \) は \( A\) と \( B \) で割り切ることができる数なので、\( A, B \) の最小公倍数が答えになります。
コード#include <b ...
[AtCoder] 第二回全国統一プログラミング王決定戦本戦 B – NIKKEI String
\( n = |S| \) とします。\( S_3 , \ S_4 \) を固定して考えます。\( S \) の \( i \) 文字目から \( j \) 文字目までの部分文字列を \( S(i, j) \) \( (0 \ ...
[AtCoder] 第二回全国統一プログラミング王決定戦本戦 A – Count Triplets
\( A_i < A_j \) を満たす \( (i, j) \ ( i < j ) \) の数を \( l_j \) とし、\( A_j < A_k \) を満たす \( (j, k) \ ( j < ...
[AtCoder] ABC 146 D – Coloring Edges on Tree
必要な色の数は、頂点の最大次数となるので、任意の頂点から幅優先探索を行い、色を振り分けていきます。辺の色を順番に出力する必要があるので、マップを使って管理します。また、色を分けるときに使用できない色を管理するためにセットを使い ...
[AtCoder] ABC 147 D – Xor Sum 4
整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_ ...
[AtCoder] ABC 147 C – HonestOrUnkind2
ある人は正直者か不親切な人かの \( 2 \) 通りなので、全体で \( 2^N \) のパターンがあります。なので、ビット全探索を行います。人 \( i \) が正直者としたとき、その証言が現在のビットの状態と同 ...
[AtCoder] 三井住友信託銀行プログラミングコンテスト2019 D – Lucky PIN
長さが \( N \) の文字列から \( 3 \) 文字取り出すことを考えると、計算量は \( {}_{N} \mathrm{ C }_{3}\) となってしまうので、別の方法を考えます。考えられる文字列は \( 1000 ...