ARC121E 解説: 包除原理と動的計画法を用いた解法
この問題は、「すべての要素が特定の条件を満たさない」ような場合の数え上げ問題であり、直接的に解くか、または「少なくとも1つの要素が条件を満たす」場合に包除原理を適用する方法があります。ここでは後者のアプローチを取ります。
(S(i)) を、「(i) 個の (k) について (a_k) が (k) に到達可能である」という条件を満たす順列の数と定義します。包除原理を使うと、以 ...
10月12日 23:04 投稿
配列と集合の問題解説: Codeforces Round 932 (Div. 2)
C. メッセンジャープログラム
2つの配列aとb、および整数Lが与えられます。aとbのインデックスのシーケンスpを見つけて、\(\sum a_{p_i} + \sum |b_{p_i}-b_{p_{i+1}}| \leq L\)を満たす必要があります。
解法
キー1：bを昇順にソートすることが最適です。
キー2：固定された\(b_l\)と\(b_r\)に対して、\(\sum^r_l |b_{p_i}-b_{p_{i+1}}| = b_r - b_l\)となり、これは固定 ...
9月28日 13:57 投稿
競技プログラミングにおける問題解決戦略
数理的考察に基づくアルゴリズム設計について議論する。以下に代表的な問題パターンとその解法を示す。
「CF1183F Topforces Strikes Back」
最大値選択問題の最適化戦略を検討する。以下の条件を満たす組み合わせを探索する：
単一要素：最大値を選択
二要素：最大値の因数である必要がある
三要素：最大値とその約数の組み合わせ
証明概要
最大値以外の要素を含む場合 ...
9月22日 08:08 投稿
数論・組み合わせ・対頂ヒープを用いた競技プログラミング問題の解析と実装
問題A：平方倍数の探索
問題概要
正の整数 k が与えられる。k | n^2 （n^2 は k の倍数）かつ n が k の倍数ではないという条件を満たす最小の正の整数 n を求める。
解法の考察
求める n^2 は k の倍数であるため、n^2 = m * k と表せる。ここで n は k の倍数ではないため、m は 1 以上 k-1 以下の範囲に存在する。m を直接全探索すると計算量が O(k) となりTLEする。
...
9月17日 20:44 投稿
競技プログラミングにおけるグラフ理論・組合せ数学・動的計画法の応用テクニック
弦なし閉路の検出と辺グラフ変換
長さ4以上の弦なし閉路を検出する問題では、頂点ベースの探索ではなく辺をノードとする線グラフへの変換が有効である。有向辺 $(u \to v)$ と $(v \to w)$ の間に、辺 $(u, w)$ が存在しない場合にのみ有向辺を張る。この変換により、元のグラフにおける三角形は新グラフで閉路を形成しなくなる。新グラフ上でDFSを実行し、最も深い返祖辺 ...
9月14日 12:35 投稿
競技プログラミング模試解説：数論・文字列・区間クエリ処理
本記事では、CSP（中国情報オリンピック予選）直前に実施された模擬コンテストの4問について、解法と実装を解説する。
A. 素因数分解による数字列変換
各桁の数字を素因数に分解し、大きい素因数から順に出力する問題。例えば「6」は2×3なので、最終的な出力では「3」より「2」が先に来る必要がある。
各数字の素因数の個数を前計算し、7, 5, 3, 2の順に貪欲に出力する ...
9月4日 02:09 投稿
貨積みの可否判定問題：棚の制約と配達順序
工場では、色番号1からNまでの異なる色の玉を各色1箱ずつ備蓄しており、作業員はそれらを決められた順序で出荷され、積み込む。作業員は以下の規則に従って作業を行う：
工場から運ばれてきた箱が、現在積み込みが必要な色（期待色）であれば、その箱を開封して直接積み込む。
そうでない場合、その箱を一時的な積み場（棚）の上に積み上げる。
ある色の積み込みが ...
9月4日 01:36 投稿
街路灯の消灯順序最適化 - 区間DPによる解法
街路灯の消灯問題
問題の概要
ある村では、一本の道に \(n\) 基の街路灯が設置されています。各街路灯には異なる消費電力があります（つまり、同じ時間あたりに消費する電力量が異なります）。張さんはこの道の途中にある街路灯のそばに住んでおり、毎朝夜明けになると一つずつこれらの街路灯を消す仕事をしています。
村の電気代を節約するため、張さんは各街路灯の位置と ...
8月22日 01:37 投稿
競技プログラミング・アルゴリズム問題解説：動的計画法、単調スタック、貪欲法の実装
問題概要と考察
本稿では3つのアルゴリズム問題を解くための手法について説明します。各問題で異なる技術が要求されています。
第1問：骨牌配置の最適化
n枚の骨牌を並べるとき、ある位置から倒すことで連続して倒れる骨牌の数を最小化する問題です。
考え方
最終的な回答は、末尾のいくつかの骨牌を削除した後の状態から計算できます。任意の位置まで考えた時の最適値を ...
8月21日 23:21 投稿
2022 ICPC アジア西安地区大会 問題解説と実装アプローチ
C. Clone Ranran
本問題は、自身のクローンを作成する時間と、問題を作成する時間のバランスを取って最小の総時間を求めるものです。
クローンを作成する回数を全探索します。クローンを作成するたびに人数は2倍になるため、対数オーダーの探索で済みます。各ステップにおいて、必要な問題数を現在の人数で割ったもの（切り上げ）を作成時間に乗算し、クローン作成時間と合 ...
8月18日 14:40 投稿