[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 \) ...
[AtCoder] ABC 030 D – へんてこ辞書
\( k \) 回シミュレーションを行うことはできないので、シミュレーションを高速化の考えます。\( k \) が十分大きければ、探索の過程で同じ単語を調べることになるので、閉路が存在することになります。下記の問題がこの問題と ...
[AtCoder] ARC 109 C – Large RPS Tournament
参加者が出す手は周期性を持ち、最初に出す手は周期 \( n \) で変わります。ここで、\( T_0 = ss \) とします。ここで、\( f(t) \) を文字列 \( t \) を出す参加者で勝利した文字列とします。\( ...
[AtCoder] ARC 109 B – log
\( n + 1 \) の長さの丸太を切断することを考えます。
\
を満たす最大の \( m \) を求めると、\( n + 1 – m \) 本の丸太を買えば良いです。
コード#in ...
[AtCoder] ARC 109 A – Hands
廊下だけを使うか、廊下と階段を使うかの \( 2 \) 通りを考えます。階段を使う場合は、廊下を先に通り、残りは階段を使います。
コード#include <bits/stdc++.h>using namespace ...
[AtCoder] ABC 032 D – ナップサック問題
整数計画法である 0-1 ナップサック問題を線形計画法で解くことを考えます。線形計画法では、重さ当たりの価値が大きいものから取っていけば良いです。ここで、荷物を重さ当たりの価値の降順になるように並び替えます。
深さ ...
[AtCoder] ABC 184 F – Programming Contest
\( n = \min(20, N) \) として、問題を \( n \) と \( N – n \) 個に分けて考えます。前半の問題の集合を \( A \) とし、後半を \( B \) とします。\( ...