Educational Codeforces Round 181 (Div. 2) の A〜D 問題の解法
問題リンク: https://codeforces.com/contest/2125
A. Difficult Contest
解法
「NTT」と「FFT」はどちらも部分列として T が後ろに来る必要がある。したがって、まず F と N 以外の文字をすべて出力し、その後で F と N を出力すればよい。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
...
10月5日 11:00 投稿
桁の和がsとなるn桁の正整数の個数を求める
これは条件付きの正整数分割問題であり、直接的な計算式は存在しません。
小規模な場合は全探索が可能です。数百桁規模になると動的計画法が有効です。しかし数千桁規模では動的計画法でも数十分から数時間要します。さらに万桁規模になると、時間・空間的な制約によりPCでの計算は不可能になります。
「挿入法と包含排除原理の組み合わせ」が強力な手法です。
核心となる ...
5月12日 17:53 投稿