SMU Summer 2024 Contest Round 6 問題解説
Many Formulas
問題概要
ある整数が与えられます。この整数の任意の桁と桁の間に + 記号を0個以上挿入することで式を形成し、形成可能なすべての式の合計値を計算します。
解法
1 ≤ |S| ≤ 10 であるため、全探索が現実的です。n桁の整数では、n-1箇所の隙間に加号を挿入するかどうかを決定できます。バイナリビットマスク用于枚举所有可能的加号插入位置。
実装
#include & ...
5月16日 16:51 投稿
競技プログラミング向けアルゴリズム備忘録
メモリ使用量の見積もり
プログラムが使用するメモリ容量を概算する方法：
1 MB = 1024 × 1024 バイト
int 型は 4 バイト
→ 必要メモリ (MB) = (int の要素数 × 4) / (1024 × 1024)
他のデータ型も同様に、各要素のバイト数を掛け合わせて計算する。
実行時間の計測（C++）
CPU時間を用いてコードの実行時間を計測する例：
#include <ctime>
#include <iostream ...
5月16日 05:33 投稿
動的計画法による部分列問題の解法
問題1：最長増加部分列
最長増加部分列（Longest Increasing Subsequence, LIS）問題は、与えられた数列から、要素が厳密に増加する順序で並んでいる最長の部分列を見つける問題です。
class Solution {
public:
int lengthOfLIS(vector<int>& arr) {
// 1. DPテーブルの作成
int size = arr.size();
vector<int> dp(size, 1) ...
5月15日 12:10 投稿
Pythonでフィボナッチ数列を応用した階段の登り方を求解する
問題概要と考察
この問題では、n段の階段を1段または2段ずつ登る場合の、登り方の総数を求める必要があります。各段数における解を観察すると、フィボナッチ数列と同じパターンに従っていることが分かります。
1段：1通り
2段：2通り（1+1 または 2）
3段：3通り（1+1+1、1+2、2+1）
4段：5通り（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）
つまり、n段目までの登り方の総数 ...
5月14日 19:00 投稿
動的計画法入門：基本概念と実践
動的計画法(DP)は前の状態から次の状態を導き出す手法であり、貪欲法が局所的に最適解を選択するのとは異なります。アルゴリズム学習において、この違いを理解することが重要です。
動的計画法問題を解決するため、以下の5つのステップを確実に理解する必要があります。これら全てをマスターしてこそ、動的計画法を真に理解したと言えます。
DP配列（テーブル）と添字 ...
5月14日 05:35 投稿
AtCoder Beginner Contest 318 問題分析とC++解法
A - Full Moon (満月)
この問題は、N日目までの期間において、最初の満月がM日目に見え、その後P日ごとに満月が見える場合に、合計何回満月が見えるかを数えるものです。つまり、M, M+P, M+2P, ...という等差数列の項がN以下になるものがいくつあるかを求めます。
まず、N日目がM日目よりも前であれば、満月は一度も見えません。この場合、回数は0です。
N日目がM日目以降 ...
5月13日 23:06 投稿