1 プログラミング能力向上

Euler-1：3 または 5 の倍数#

思考
- ①通常の解法：1-1000 を走査し、3 または 5 で割り切れるか判断し、割り切れる場合は sum に加える
  - 時間計算量：O (N)
- ②より良い解法：3 または 5 の倍数の和を直接計算
  - 等差数列を利用し、重複計算に注意
    - 公式：（初項 + 末項） * 項数 / 2
  - 3~999 の 3 の倍数の和 + 5~1000 の 5 の倍数の和 - 15~985 の 15 の倍数の和
  - 時間計算量：O (1)
コード

Euler-2：偶数フィボナッチ数#

思考
- 通常の解法：配列を使って前の値を保存し、再帰的に偶数のときに sum に加える
  - 空間計算量：O (N)、大量の追加スペースが必要
- より良い解法：2 つの変数を使って往復する（先生は 3 つと言ったが、実際には a は使わない）
  - b、c：各イテレーションで、c = c + b; b = c - b;
  - 空間計算量：O (1)
コード

Euler-4：最大回文積#

思考
- 回文数の判断方法
  - 2 つのポインタをそれぞれ先頭と末尾から対応させて比較
  - √より便利：数字を反転させて再度比較
    - 実際には半分だけ反転させれば良い、ループ成立条件は反転した数字 < 残りの反転した数字
      - 注意：奇数桁のケース；末尾に 0 が含まれるケース
- すべての 3 桁の数を列挙し、回文数を判断し、最大を探す
コード
- time *./a.out でそれぞれの組み合わせの時間を計算

time	① 半分の桁数だけ反転	② 全ての桁数を反転
A 先に回文数を判断	0.013	0.017
B 先に大きさを判断	0.005	0.005

- j は i から始めることで、重複積を避けることができる
- C++ には max 関数が組み込まれている
- さらに、ショートサーキット原則を利用して B を最適化でき、速度も向上：0.004s

Euler-6：和の平方と平方の和の差#

思考
- 簡単なループ：1~100 の平方和と和をそれぞれ計算し、和の平方 - 平方和を求める
コード

Euler-8：連続数字の最大積#

思考
- まずデータをコピーし、ローカルに文字列として保存
  - コピー後の形式を確認：空白や改行を削除
  - 読み込む際は配列に保存し、各桁を数字に変換する必要がある（- '0'）
- スライディングウィンドウ法
  - 静的ウィンドウ：固定ウィンドウサイズ
  - 動的ウィンドウ：一般的に 2 ポインタと呼ばれる
- 解法：スライディングウィンドウ法を使用 ——静的ウィンドウ
  - ウィンドウに入る数と出る数だけを考慮すれば、計算回数を減らすことができる
    - 出：割る
    - 入：掛ける
    - 値が 0 でないか注意
- コード
  - 最初の 13 桁に 0 が含まれない場合、直接 now を計算できる
  - ウィンドウ内の 0 のケースに注意
    - ❗0 のカウンターを定義する
    - ❌0 に出会ったら積を 1 にすることはできるか？
      - できない、0 以外の数の積を保存する必要がある
    - ❌0 を直接 1 に変えることはできるか？判断回数を減らすために、入ってくる値だけを判断すれば良い
      - しかし、これはできない。なぜなら、満たない 13 桁の 2 つの 0 の間の数が非常に大きい可能性があるから
      - 例えば 11022340111111111111111111
  - 実行時にエラー：浮動小数点例外
    - 0 で割ることが原因でこのエラーが発生する可能性がある
  - 上界を誤って推定したため、9^13 は確実に int 型の上界を超えるので、long long を使用

Euler-11：行列の最大積#

思考
- 方向配列
  - 行列内のある数の座標を通じて、特定の方向の数の座標を推算
- 特定の数の各方向の連続 4 つの数の積を計算し、最大値を見つける
  - 計算問題：連続した 4 つの方向だけを取れば計算できる。重複計算を避ける
  - 境界問題：①境界を判断；√②境界に 0 を補充（少なくとも 3 周の 0）。越境問題を解決
コード
- 方向配列を定義することを学ぶ
  - 変数 l を利用して特定の方向の l 番目を制御
- C 言語のループ内で変数宣言の文を書くと、コンパイラは 1 回だけ作成する。例えば 32、33 行
  - 参考C 言語の変数の再宣言-CSDN

Euler-14：最長コラッツ列（メモリ配列）#

フィボナッチ数列
- 2 つの方法：再帰、再帰的推進
- 再帰
  - 通常
    - 非常に遅い、重複計算があるが、最適化版がある👇
  - メモリ配列を使用
    - 再帰 + メモ化 ≈ 再帰的推進
    - メモ化前→後：1.804s→0.002s
- 再帰的推進：速度が速く、スペースも占有する。euler2 の 2 つの変数を往復させることができるか？
  - 配列に保存；num [i] = num [i - 1] + num [i - 2];
思考
- 同様に再帰 + メモリ配列を利用
- 問題文の注：列が生成され始めた後、項が 100 万を超えることを許可
- 追加のカウンターは必要なく、次の数を計算するたびに + 1 することができる
コード
- 詳細は注釈を参照
  - num 配列の長さが大きいほど、速度が速く、スペース消費も大きい
  - t を使用して関数の結果を記録し、配列に保存する前に判断を行う
  - main 関数内で func (ans) の値を先に保存することで速度を向上させる

Euler-13：大和（大整数加算）#

思考
- 大整数加算を参照
コード
- 大整数加算を参照

➕大整数加算#

大整数：long long でも収まらない、一般的に文字列で保存
⭐配列方法
- 2 つの配列で逆さまに大数を保存し、配列の第 0 位に大数の桁数を保存👉
  - 逆さまに保存しないと、最高位で繰り上がると処理が難しい？そのまま出力しても処理しなくても良い
  - しかし、逆さまに保存しないと、低位の整列の問題が発生し、処理が難しい
- 各インデックスの値を合計し、合計の桁数は 2 つの大数の最大桁数を取る👉
- 繰り上がりを処理し、最後の桁で繰り上がった場合は、合計の桁数を + 1 することを忘れない👉
- 逆さまに出力
コード
- 最高位の繰り上がりのケースを処理しなくても良い。最高位に繰り上がりがある場合は、最初に 2 桁を出力する
  - 例えば：入力 888 + 222；出力 11 1 0
  - ただし、複数の数を加算する場合は普遍性が悪いかもしれない！1 つのインデックスに 1 桁の数字を保存するのが最も安全

Euler-25：1000 桁のフィボナッチ数（大整数加算）#

思考
* 2 つの変数の大整数をループで加算するだけ
* int num [2] = {1}; // 残りは自動的に 0 で埋められる
コード

✖ 大整数乗算#

思考
- 大整数加算と同様
- 各桁の積の結果を加算する位置：i + j - 1
コード
- 答えの配列の要素タイプは少なくとも int である必要がある
- 答えの配列の長さは、可能な結果の短い長さを取る
- 積の計算を累積する位置に注意～
欧ラープロジェクトの 16、20 の問題を試してみてください

➗大整数除算#

除数と被除数はどちらも大整数
思考
- まず被除数が除数より大きいか判断
- 次に、待ち受ける数から除数を引き続け、引けなくなるまで、最大で 9 回引く
- 除数も大整数である可能性があるため、待ち受ける数も大整数：これによりコードが非常に複雑になる
hzoj 475、476 の問題を試してみてください

Euler-15：グリッドパス（再帰、一般式）#

思考
- 方法 1：再帰的推進（動的計画法）
  - 現在の方案数 = 上から来た方案数 + 左から来た方案数
  - 0 を補充する方法：点 (1, 1) から保存を開始
  - 境界に注意：2 * 2 のグリッドでは、左上と右下は点 (1, 1)、点 (3, 3)
  - PS：再帰 + メモ化を使用することもでき、いくつかの類似点がある
- 方法 2：一般式を使用して、組み合わせ！
  - 2 * 2 のグリッドの場合
  - 下に行く総ステップ数と右に行く総ステップ数は 4 であり、そのうち下に 2 歩、右に 2 歩
  - 実際には組み合わせであり、C (4) 2 = 4! / [2! * (4 - 2)!]
  - したがって、この問題は C (40) 20 です
コード
- 方法 1 では最初の点 (1, 1) を特別に判断することを忘れないでください
- 方法 2 では、掛け算と割り算を同時に行うことで越境を防ぎ、先に掛けてから割ると小数の状況は発生しません

Euler-18：最大パス和（木塔問題）#

思考
- 再帰的推進（動的計画法）
  - 上から下へ
    - dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[i][j]
    - 最後の行を走査し、最大値を出力
  - 下から上へ
    - dp[i][j] = max(dp[i + 1][j + 1], dp[i + 1][j]) + num[i][j]
    - 最後に走査する必要はなく、最上部が最大値
- 0 を補充！
コード
- 第 i 行には i 個の値がある
- 上から下へ、下から上への方法の主な違いは最大値の位置の決定

HZOJ-590：木塔狂想曲#

サンプル入力

サンプル出力

17
22
-1

思考
- ❌毎回特別に 1 つの点を処理した後、再計算する
- 各点に対応する最大パス和と次最大パス和を記録
  - 特定の点を通過することで得られる最大値：上から下へ + 下から上へ - 現在の値
  - 時間、空間のオーバーヘッドは O (N^2)
  - 思考図は以下の通り
コード
- 特定の点を通過する最大パス和の規則を見つける
- 次最大値の更新状況を十分に考慮する
- 最大値の座標と次最大値を記録するだけで良い
- ban されているのが最大点か左上の最初の点かを判断
- scanf を使用
  - cin より速い、詳細は追加知識点 2 を参照

Euler-22：名前のスコア#

思考
- まず txt ファイルを処理
  - 文字はすべて大文字
  - グローバルに「,」を「空白」に置き換え、データの読み込みを便利にする

:%s /","/ /g

- 文字列を読み込む→sort で辞書順にソート→各名前の文字値を計算し、その順位を掛けてスコアを得る→スコアを累積
コード
- cin の戻り値
  - istream & 型
  - 大多数のケースではその戻り値は cin 自身（非 0 値）であり、EOF 入力に遭遇したときだけ戻り値は 0
  - 参考について C++ cin の戻り値
- string クラス
  - 小なり記号をオーバーロードしているため、直接 sort で昇順にソートできる
  - scanf をサポートしていない
  - .size () を使用して文字列の長さ = 文字数 = バイト数を取得できる
- 終了条件は.size () を使用することもでき、name [i] が "\0" であるかどうかを判断することもできる
- 2 つの関数は 2 つの for ループで直接置き換えることができる

Euler-32：全数字の積#

思考
- 全数字の概念：xx * xxx = xxxx、1~9 の各数字が 1 回ずつ存在
  - 0 は含まれない！
- 重複計算を避ける
  - 最初の数字は 2 番目の数字より小さい
  - 最初の数字：範囲 1~100、100 のとき、2 番目の数字は少なくとも 100、3 つの桁数の合計が 9 を超える
  - 2 番目の数字：停止条件は 3 つの数字の桁数の合計が 9 を超える
  - log10 を使用して桁数を判断：log10を下に切り捨て+ 1
    - 正の数を int に変換するのと切り捨てるのは効果が同じで、切り捨てた後に得られた double を int に変換する必要がある
- 全数字を判断する方法
  - <9 は判断する必要がなく、=9 のときだけ判断し、>9 のときは停止
  - num [10] を使用して 9 つの数字の状態を保存
- 積は複数の乗法等式から得られるが、1 回だけ求める
  - マーク配列を使用し、以前に保存した場合はスキップ
コード

Euler-33：消去数字の分数#

思考
- 面白い
- 4 つの非平凡な例があり、4 つの分数の積を最簡分数にした後の分母の値を求める
  - 平凡解は考慮しない、つまり 0 が存在する場合は考慮しなくて良いので、各桁が 0 でないことを直接要求できる
- 分子と分母は 2 桁の数であり、分母は分子より大きい
  - 分子：11 - 99；分母：分子 + i
- 4 つの消去方法
  - 分子 1 = 分母 1；分子 1 = 分母 2；分子 2 = 分母 1；分子 2 = 分母 2
  - 消去前後の判等：十字相乗
コード
- 十字相乗法で分数の等価性を判断
- 公約数を通じて最簡分数を得る

Euler-36：双進制回文数#

思考
- 前導 0：0012332100 のように、回文数とは見なされない

int num;
cin >> num;
// 00123は正常に読み込まれ、123になる

- 十進法と二進法は N 進法に統合可能
コード

Euler-30：各桁の数字の五乗#

思考
- 重要：五乗の和の最大範囲は？

ある X 桁数を仮定
その最大五乗の和は 9^5 * X
X 桁数の上界は 10^X
2 つの値の交点を推定、すなわち 9^5 * X = 10^X、X は約 5.xxx
したがって X の最大は 6

- - 10 ~ 1000000 を列挙
- ⭐1 ~ 9 の五乗を事前に計算し、保存！
コード
- 重要なのは列挙範囲！
- 1 ~ 9 の五乗の和を事前に保存し、重複計算を避ける

Euler-34：各桁の数字の階乗#

思考
- 重要：階乗の和の最大範囲は？

（前の問題と同様）
ある X 桁数を仮定
その最大階乗の和は 9! * X
X 桁数の上界は 10^X
2 つの値の交点を推定、すなわち 9! * X = 10^X、X は約 6.xxx
したがって X の最大は 7

- - 10 ~ 10000000 を列挙
- 同様に、⭐1 ~ 9 の階乗を事前に計算し、保存する！
コード

追加知識点#

グローバル変数は自動的に 0 で初期化される
scanf は cin より速い、参考
- cin、cout の性能は非常に遅い可能性があり、底層 C ライブラリとの同期を維持する必要がある
  - 同期をオフにすると速くなるが、C の入出力関数には及ばない
- アルゴリズムコンペティションの際に cin、cout を使用することは scanf、printf よりも遅いか？- 知乎
- C++ プログラムで scanf () を使用する方が cin を使用するよりも速いか？- 腾讯云

思考点#

Tips#
使用言語は C++ だが、C との違いは cin、cout にのみ関係する
time ./a.out でコードの実行時間を表示できる

Bo2SS

1 プログラミング能力向上

Euler-1：3 または 5 の倍数#

Euler-2：偶数フィボナッチ数#

Euler-4：最大回文積#

Euler-6：和の平方と平方の和の差#

Euler-8：連続数字の最大積#

Euler-11：行列の最大積#

Euler-14：最長コラッツ列（メモリ配列）#

Euler-13：大和（大整数加算）#

➕大整数加算#

Euler-25：1000 桁のフィボナッチ数（大整数加算）#

✖ 大整数乗算#

➗大整数除算#

Euler-15：グリッドパス（再帰、一般式）#

Euler-18：最大パス和（木塔問題）#

HZOJ-590：木塔狂想曲#

Euler-22：名前のスコア#

Euler-32：全数字の積#

Euler-33：消去数字の分数#

Euler-36：双進制回文数#

Euler-30：各桁の数字の五乗#

Euler-34：各桁の数字の階乗#

追加知識点#

思考点#

Tips#

コース速記#