[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 ...
[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 \) ...
[Codeforces] Codeforces Round #688 (Div. 2) B. Suffix Operations
まず初めに、\( a_1 \) に対して操作する必要はありません。\( a_1 \) に対して操作を行うということは、全ての配列に対して \( 1 \) を加算または減算をするためです。操作の前に配列の値を変えない場合に必要な ...
[AtCoder] ABC 030 D – へんてこ辞書
\( k \) 回シミュレーションを行うことはできないので、シミュレーションを高速化の考えます。\( k \) が十分大きければ、探索の過程で同じ単語を調べることになるので、閉路が存在することになります。下記の問題がこの問題と ...
[Codeforces] Codeforces Round #687 (Div. 2) D. XOR-gun
排他的論理和の問題です。最上位のビットが同じ \( 1 \) である自然数を \( a_{i}, a_{i + 1}, a_{i + 2} \) とすると、
\
となります。配列 \( a \) の連続 ...
[Codeforces] Educational Codeforces Round 99 (Div. 2) C. Ping-pong
自分の勝利の最大化が一番優先されるので、ボブの勝利数が \( y \) となるかを考えます。もしアリスのサーブを全て返さずに、アリスのスタミナが \( 0 \) となったとき、ボブとアリスの勝利数は、\( x, y \) とな ...