数論・組み合わせ・対頂ヒープを用いた競技プログラミング問題の解析と実装
問題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 投稿
一月の競技プログラミング問題解説
### \[ABC154F\] Many Many Paths
この問題は組み合わせ数を使用します。簡単な問題ですが、詳細な解説は後日行います。
### CF1542D
この問題では動的計画法（DP）を使用します。問題文を変換すると、各操作 \(+x\) に対して、その操作が加算されるためには、それより小さい操作が必要であることがわかります。つまり、操作の具体的な値ではなく、その大小関係に注目 ...
8月5日 01:57 投稿
CF251A 直線上の点の解説
問題文
Petyaは点が大好きです。彼の母親は彼に数直線OX上のn個の点を与えました。Petyaは、最も遠い2点間の距離がd以下となるような3つの異なる点を選ぶ方法がいくつあるか知りたいです。3つの点の順序は関係ありません。
入出力形式
入力
最初の行には2つの整数n (1 ≤ n ≤ 105) と d (1 ≤ d ≤ 109) が含まれます。次の行には、Petyaが持つ点のx座標を表すn個の整数x1, x ...
6月27日 00:38 投稿
アルゴリズム問題 - バックトラッキング手法
1.バックトラッキングの理論的基礎
1.1バックトラッキングとは何か
バックトラッキングは探索アルゴリズムの一種であり、再帰処理に基づいて動作します。
再帰呼び出しの結果としてバックトラッキングが発生するため、再帰があれば必ずバックトラッキングも存在します。
1.2バックトラッキングの性能
バックトラッキングは計算効率が悪いという特徴があります。これは、す ...
5月20日 01:32 投稿