[AtCoder] ABC 009 C – 辞書式順序ふたたび
\( T_i \) の先頭から貪欲に辞書順の最小の文字から構成できるかを調べます。これは文字の頻度を管理することで、高速に計算することができます。文字列 \( S \) の \( i \) 文字目から \( j \) 文字目ま ...
[AtCoder] ARC 110 B – Many 110
\( N \geq 4 \) について考えます。\( S \) に \( T \) が含まれる場合、\( T \) は、
\
のどれかである必要があります。これらは、\( 110, 101, 011\) ...
[AtCoder] ARC 108 B – Abbreviate Fox
括弧の対応の問題で良く使うスタックを使います。スタックに \( s \) の先頭から入れていき、\( s_i = o \) のとき、スタックの先頭から “xf” と積まれていたら “fox& ...
[AtCoder] AGC 048 A – atcoder < S
\( S \) が ‘a’ だけの文字からなるとき、’atcoder’ \( < S\) とあることはありません。また、’atcoder’ R ...
[Codeforces] Codeforces Round #676 C. Palindromifier
どちらの操作も \( S \) の先頭または末尾の文字を含む部分列を選ぶことができないので、\( S \) の末尾が中心となるような回文を作ることを考えます。
まず初めに、”L 2″ という ...
[Codeforces] Codeforces Round #668 (Div. 2) C. Balanced Bitstring
k-balanced な文字列は次の条件を満たします。\( s_i = 0 \) のとき、\(a_i = -1 \) とし、\(s_i = 1 \) のとき、\(a_i = 1 \) とすると、
\begin{eq ...
[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) C. Binary String Reconstruction
文字列 \( w \) と自然数 \( x \) が与えられたとき次の条件を満たす文字列 \( w \) を答えます。
\( i – x \geq 0 \wedge w_{i-x} = 1 \) ならば \( ...
[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) A. String Similarity
同じ長さの文字列 \( s \) と \( t \) が ‘similar’ である条件は、\( s_i = t_i \) となる整数 \( i \) が存在することです。
長さ \( 2n ...
[AtCoder] パナソニックプログラミングコンテスト2020 D – String Equivalence
深さ優先探索を使うらしい。
コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int N;void dfs(string s) ...
[AOJ] No. 0341 繰り返す呪文
動的計画法を行います。\( d(i, j) \) を \( t \) の \( j \) 番目までの部分文字列において、\( b \) の \( j \) 番目までの部分文字列の出現回数とします。初期値は、\( d(i, 0) ...