Bo2SS

シンプルなアルゴリズム、複雑な一面もある～

二分探索#

①素朴な二分#

• 正確に対応する値を探す

• 浮動小数点数の状況は②、③でも成り立つ

②⭐特殊な二分#

• 0 と 1 の境界にある 1 を探す

• C++ にはこの機能を実装する関数が実際にある
  • lower_bound、upper_bound
  • 参考lower_bound () と upper_bound () の一般的な使い方-CSDN

③⭐⭐二分の答え#

• 特殊な二分+func (答え)
  • 答えに基づいて更新条件の値 func (答え) を得る
  • 更新条件の値は一般的に順序の条件を暗示している
    • したがって、ソートするかどうかは func の解決のしやすさに関係しており、必須ではない

HZOJ-380：大統領投票（sort）#

サンプル入力

3
123456799
123456789132456789123456789
11111111111111

サンプル出力

2
123456789132456789123456789

• 考え方
  • 投票数が非常に大きいため、文字列として読み込む必要があり、string クラスを使用
    • string クラスは＞をオーバーロードしており、辞書順の比較が自動的に行われる
  • struct クラスを利用し、対応する番号と組み合わせる
  • sort を利用
    • まず長さを比較し、strlen
    • 長さが一致する場合は辞書順を使用
• コード
  • 
  • const node &a の & は参照渡しであり、削除可能だが const を追加する必要がある～
  • 長さを判断しなければならない、さもなければ 53 は 12345 の辞書順より大きい
  • インデックスは 1 から始まる、さもなければ (0, 0) が導入される

HZOJ-381：誰が最も多くの奨学金を受け取ったか（sort）#

サンプル入力

4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

サンプル出力

ChenRuiyi
9000
28700

• 考え方

  • 奨学金が同点の場合、最初に出現したものを出力する
    • したがって、番号を記録する必要があり、sort は不安定である
  • 奨学金計算ルールの詳細に注意するだけでよい

• コード

• 

HZOJ-386：観衆（①）#

サンプル入力

5 3
1 3 26 7 15
26 99 3

サンプル出力

3
0
2

• 考え方
  • ソート + 素朴な二分
  • スイカの数と番号を struct にまとめる必要がある
• コード
  • 
  • mid 計算式、オーバーフローを防ぐ
    • = ((long long)l + r) / 2
    • = l + (r - l) / 2
  • 見つからなければ 0 を出力、f は初期値 0

HZOJ-387：観衆のアップグレード版（②）#

サンプル入力

5 5
1 3 26 7 15
27 10 3 4 2

サンプル出力

0
5
2
4
2

• 考え方
  • 0 の束と 1 の束を抽象化し、最初の 1 の状況を探す
  • 0 を出力する状況を考慮する
• コード
  • 
  • 0 を出力する状況を二つ処理する
  • 000000011111111

Leetcode-278：最初の悪いバージョン（②）#

例

n = 5が与えられ、version = 4が最初の悪いバージョンです。
isBadVersion(3)を呼び出す -> false
isBadVersion(5)を呼び出す -> true
isBadVersion(4)を呼び出す -> true
したがって、4が最初の悪いバージョンです。 

• 考え方
  • 特殊な二分探索を使用する
  • 000000011111111
• コード

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;  // バージョン番号は1から始まる
        while (l != r) {
            int mid = ((long long)l + r) / 2;  // オーバーフロー防止方法1
            // int mid = l + (r - l) / 2;  // オーバーフロー防止方法2
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

HZOJ-390：木材の切断（③）#

サンプル入力

3 8
6
15
22

サンプル出力

5

• 考え方
  • 左界→右界：1→max (Xi)
  • 111111110000000
  • ③ = ② + func(mid)
    • func (mid)：mid に基づいて切り出せるセグメント数を求める、長さ mid が求める答え
• コード
  • 
  • 右界を確定する必要があり、入力時に確定する

HZOJ-389：イライラしたプログラマー（③）#

サンプル入力

5 3
1
2
8
4
9

サンプル出力

3

• 考え方
  • 距離の上下界：1→max (Xi)
    • 簡単にするため、1 と最大の作業位置番号を取る
    • より詳細にする場合は、最小と最大の作業位置番号の差を取る
  • 答え→判断基準：距離→配置できる人数
  • 111111100000
• コード
  • 
  • ソートしてから距離に基づいて配置できる人数を計算する
  • func()
    • 前回配置した人の位置 last を記録する必要がある
    • 配置できる人数 s を求める
    • 初期化：配置できる人数 s は 1、前回配置した人の位置 last は num [0]

HZOJ-393：ロープを切る（小数③）#

サンプル入力

4 11
8.02
7.43
4.57
5.39

サンプル出力

2.00

• 考え方
  • 木材の切断に似ているが、データは浮動小数点数である
    • 条件、更新式が異なる
  • 探索する左右の境界を決定し、答えに基づいて判断基準を得る
• コード
  • 
  • 浮動小数点数の二分探索
  • 小数点以下 2 桁を超える数字を直接捨てる考え方
    • 考え方 1：*100→int に変換→100.0 で割る→精度を %.2f に設定
    • 考え方 2：-0.005→精度を %.2f に設定
    • 参考：C++ の整数化：切り捨て、切り上げ、四捨五入、直接小数点を切り捨てる-CSDN
      • %.2f、は四捨五入のメカニズムである
      • int に変換：小数点とその後の小数を直接取り除いて整数化

HZOJ-82：伐採#

サンプル入力

4 9
20 17 15 10

サンプル出力

14

• 考え方
  • 木材の切断に似ているが、判断基準は切り取った木材が必要な木材の長さを満たすかどうかである
  • 上下界：0→max ()
  • データ範囲が非常に大きいため、加算がオーバーフローする可能性があるため、long longを使用する
    • long long の位置を考慮する必要がある、考えがまとまらない場合はすべて使用することができる
• コード
  • 
  • 答えと判断基準の関係を明確にする

HZOJ-391：数列の分割#

サンプル入力

5 3
4
2
4
5
1

サンプル出力

6

• 考え方
  • 最小の最大和
  • 0000000111111、最初の 1 を探す
    • 答え（セグメント数の和）mid 小→判断基準（セグメント数）s 多く、不満足な条件に対して 0
    • 答え（セグメント数の和）mid 大→判断基準（セグメント数）s 少なく、条件を満たす、1 に対応
    • 最小の最大和を探しているため、境界を考慮する
    • ❓❗最大の最大和を探す場合、111110000 の状況に変わる
  • 左右界：max (Ai)→sum (Ai)
• コード
  • 
  • 
  • ⭐func 関数をよく考えること！
  • long long 型に注意

HZOJ-394：石を跳ぶ#

サンプル入力

25 5 2 
2
11
14
17 
21

サンプル出力

4

• 考え方
  • 最短跳躍距離の最大値
  • 起点と終点は暗黙的に存在する：min (D (i+1) - Di)→L（起点から終点までの距離）
  • 111110000
    • 最大値を探しているため、右に行くほど値が大きくなるので、最後の 1 を探す
• コード
  • 
  • 起点と終点を保存することを忘れない！
  • 終点の石に到達しても終点の石を移動しないことを考慮する
    • 前の石を移動することと等価である

HZOJ-392：瓶のキャップを捨てる#

サンプル入力

5 3
1
2
3
4
5

サンプル出力

2

• 考え方
  • 上述のイライラしたプログラマーと全く同じ！
• コード

HZOJ-395：原稿をコピーする#

サンプル入力

9 3
1 2 3 4 5 6 7 8 9

サンプル出力

1 5
6 7
8 9

• 考え方
  • 各人の写経速度は同じで、数字は時間に対応する
  • 連続している必要があり、本は分割できない
  • ステップ
    • 最初のステップ：最大値を求め、上述の数列の分割と全く同じ！
    • 二番目のステップ：各人の写経の開始と終了の番号を配列に保存する
      • 最大値を取得した後、後ろから前に数列をスキャンする
        • 複数の解がある場合、前の人に少なく書かせる
      • やや面倒で、コードのスキルを試す
• コード

追加の知識点#

• C++ の struct はクラスである
  • メンバーアクセス権はデフォルトでプライベートであり、struct はデフォルトでパブリックである
• sort <algorithm> の使用

int num[105];
sort(num, num + n, cmp); 

• • num：ソートする範囲の先頭アドレス；num + n：範囲の末尾アドレスの次のアドレス；cmp：
  • ⭐デフォルトでは不安定である
    • 基本的にクイックソートを使用し、挿入ソートとヒープソートを組み合わせている
    • 参考C++ の深い落とし穴：STL の sort アルゴリズムはどのようなソートアルゴリズムを使用しているか？- 知乎
  • int、string の場合：直接大小を比較でき、デフォルトで小さい順にソートされる
  • 自作構造体の場合
    • 小なり記号をオーバーロードする
    • 自分でソートメソッド cmp を書く

bool cmp(node a, node b) {
  return a.x > b.x;  // nodeのxに基づいて大きい順にソート
}

考察ポイント#

ヒント#

コースの速記#