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 で 2 つの組み合わせの時間を計算

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 言語のループ内で変数宣言文を書くと、コンパイラは一度だけ作成する。例えば 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 を使用するよりも速いのか？- 腾讯云

思考点#

ヒント#
使用言語は 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：各桁の数字の階乗#

追加知識点#

思考点#

ヒント#

コース速記#