3 OJ問題解説

HZOJ-599：二数の和 1#

サンプル入力

6 15
1 5 6 7 10 26

サンプル出力

1 4

考え方

方法	説明	時間計算量	空間計算量
暴力	二重ループ	O(N^2)	O(1)
暴力	一つの数を固定し、もう一つの数を二分探索	O(NlogN)	O(1)
ハッシュテーブル	最初のループで保存し、二回目のループで探す	O(N)	O(N)
⭐二重ポインタ	両端からポインタを加算し、常に更新	O(N)	O(1)

二重ポインタ
配列はソートされている
同様に、三数の和、四数の和...
- ループを一つ追加
コード

HZOJ-600：ヤンシー行列#

サンプル入力

サンプル出力

2 3

考え方
- 左下から出発するか、右上から始める
  - 横座標または縦座標を 1 単位ずつ移動
  - 時間計算量：O (n + m)
- 前の問題の二重ポインタの考え方に非常に似ている～
  - 二次元空間と一次元空間の変換！
コード
- 提出時に 2 つのテストがタイムアウト、もっと速い方法はあるのか？
  - ない、OJ プラットフォームの変動性によるもの

HZOJ-477：母音#

サンプル入力

ABCDEFGIKJUMNBZZ

サンプル出力

考え方
- 前の母音の位置を見つける
- 次の母音の位置を走査
- 距離を計算し、答えを更新
コード
- s [i] が \0 のとき停止
- last は初期値 - 1、最初の母音を見つけたときに距離を計算せず、last を更新する

HZOJ-479：卓球#

サンプル入力

WWWWWWWWWWWWWWWWWWWW
WWLWE

サンプル出力

11:0
11:0
1:1
21:0
2:1

考え方
- スコア結果を与え、11 点制と 21 点制の試合結果をそれぞれ出力
  - 各ゲームのスコアを出力
- 入力データは各行最大 25 文字、最大 2500 行
  - 2500 * 25 点を得て、/11 または / 21
  - 11 点制で最大6000ゲーム、21 点制で最大3000ゲーム
  - 開く配列のサイズを判断
コード
- cin の読み取りルール
  - スペース、改行、タブに出会ったら入力を終了し、バッファに終了符号（Enter、Space、Tab）を残す
  - EOF に出会うと 1 を返す

HZOJ-480：ボウリング#

サンプル入力

/ / / 72 9/ 81 8/ / 9/ / 8/

サンプル出力

考え方
- 重要なのは赤枠の部分
- 3 つのスコア計算の状況
  - 直接クリア：このラウンド 10 点 + 次の 2 球の得点
  - 間接クリア：このラウンド 10 点 + 次の 1 球の得点
  - クリアしなかった：このラウンドの得点
- 一局十ラウンド
- 👌構造体を使用
  - 文字配列：各ラウンドの得点文字列 8/
  - 最初の得点
  - 二回目の得点：このラウンドの最終得点、ここが巧妙で、問題の意図に基づいて設定
  - フラグ：上記のどの状況に属するか
コード
- ルールを理解し、構造体を巧妙に利用することが重要！
- s 配列は 4 を開く、最大で 2 文字 +\0 だが、バイトアラインメントのため、3 または 4 を開いても同じ、ここは 4 を開く
- ターミナルでは ctrl + d を使用して cin の for ループを終了する必要がある

HZOJ-481：カーリング#

サンプル入力

8
5 20 18 19 3 15 13 3
20 2 17 12 5 18 10 11
20 3 4 1 2 11 9 2
1 15 19 9 8 14 11 10
15 2 10 1 19 14 3 18
15 17 21 19 24 32 19 26
-1

サンプル出力

0:1
0:0
3:0
3:1

考え方
- 誰が得点できるか：すべてのカーリングが円の中心に最も近いチームが得点できる
- どれだけ得点するか：半径 r 内で、相手が円の中心に最も近いカーリングが構成する⚪内で、得点チームが持つカーリングの数
  - 緑チームは 2 点を得る
  - 田船長の筆から～
- 最大 10 局、20 行 + 1
- 各ラウンドのスコアを出力し、総スコアを出力
コード
- sort を利用して勝者と得点を見つけるのが便利で、消費も少ない

HZOJ-484：柱状統計図#

サンプル入力

ABC ABC.DEF()G GCC XY
354342aaaCaa aaaaaaaabcdbcd

サンプル出力

    *
    *
    *
* * *       *
* * * * * * *                                 * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

考え方
- 簡単：大文字の個数を数える
- 難点：各行に余分な空白を入れない；列ごとに出力
- 流れ
  - 最大の文字出現回数に基づいて行数を数える必要がある
  - 外側のループ：mmax から 1 まで、条件を満たす文字位置に * を出力
    - 最後の出力 * の文字を得るために、Z から A まで判断して条件を満たすか確認
  - 内側のループ：A から ind まで、各行の最後の文字がどれかを数える
- * と空白の出力条件に注意
  - 文字の統計数がその行で出力 * が必要な数を満たすかどうかを判断するだけ
コード
- 論理を整理することが重要～
- num 配列を 130 ビット開くのは巧妙で、ASCII コードの範囲に対応し、統計時に判断が不要
- 最初の判断：余分な空白を避ける

HZOJ-485：均等に分けるカード#

サンプル入力

4
9 8 17 6

サンプル出力

考え方
- 隣接するカードの山にしか移動できない
- まず平均を計算し、各山の期待数を得る
- 一方向から平均に合わせるだけで良い
  - 左から右へ
  - 不足分を借り、右側が負になっても問題ない
  - 本質的には二つの方向を合わせるのと同じ！
コード
- 最後の山は考慮する必要がない
- 右側の一つの数を更新するだけで、公式は加減に関わらず成り立つ

HZOJ-503：カヌー（自作）#

サンプル入力

サンプル出力

考え方
- ソートしてから判断する
コード

HZOJ-504：数を削除⭐#

サンプル入力

179566
4

サンプル出力

考え方
- 大きな整数
- 本質：前の数が小さいほど、全体が小さくなる
  - 大きな数が前、小さな数が後の場合、大きな数を削除
  - しかし直接大きな数を削除することはできない
  - 単調スタックの知識？参考単調スタックとは？- 五分でアルゴリズムを学ぶ
- 流れ：
  - 大きな整数をスキャンし、文字列を得る
    - string クラスを使用、数を削除するのが便利
    - string.replace()
  - 2 桁ごとに走査
  - 削除する回数 s 回ループ
  - 出力
    - 先頭の 0 を無視し、フラグを持つ必要があり、先頭の 0 を判断するだけで、他の 0 を省略しない
- 拡張：文字を削除して辞書順をできるだけ小さくする
コード
- ind はデフォルトで最後の桁！つまり最大の数、なぜなら小から大に並んでいるから
- str.replace 操作、参考std::string::replace-cplusplus
- 先頭の 0 の処理：フラグを定義

HZOJ-505：最大整数#

サンプル入力

3
121 12 96

サンプル出力

考え方
- ⭐文字列を接続したときの辞書順を最大に保証する
  - 任意の 2 つの要素の接続が、前の辞書順が後より大きいことを保証する
  - sort を使用
- うまくいかない方法
  - 辞書順でソート 121 12 96 👉 9612112
  - 高い桁が同じ場合、長さで判断し、短いものを前に 129 12 96 👉 9612129
コード
- string クラスは + を使って自動的に接続できる
  - 文字列形式で読み込む
- ❗> を >= に変更すると oj で 2 番目のテストがタイムアウトする
  - 両者の違いは = の場合に true または false を返すかどうかで、sort の安定性には関係ない～
  - ⭐cmp 関数は簡単ではない
    - 厳密弱順序を満たす必要がある
    - 簡単な参考STL sort の comp 関数の注意点-CSDN
    - 詳細参考一次 stl sort 呼び出しによるプロセスのクラッシュ- ブログ

HZOJ-508：二人の渡河#

サンプル入力

サンプル出力

考え方
- まずソートする
- 4 つのケース
  - 1 人
  - 2 人
  - 3 人：最も速い人を道具として使う
  - 4 人
    - ①ランプを持つ速度を最も速くする
    - ②橋を渡る効率を最大にする（今回速い人が速く、次に遅い人が遅い場合）
    - 毎回2 人を渡す最も速いケースを見つける
コード
- 2 人ずつ計算することが巧妙で、2 つの方法の中から最小を取る

HZOJ-509：知能大サーフィン#

サンプル入力

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

サンプル出力

考え方
- ソート：コスト、時間←構造体
  - まずコストでソート（多い方が前）、次に時間でソート（少ない方が前）
- 時間帯のマーク配列：特定の時間帯の占有状況を記録
  - 各タスクをできるだけ後ろに完了させる
コード

HZOJ-518：コイン#

サンプル入力

サンプル出力

考え方
- 二重ループ：いくらお金を出すか（1 ~ x）；日数（1 ~ i）
コード

HZOJ-513：階層番号#

サンプル入力

14 3

サンプル出力

考え方
- 偽の階層（1 ~ m）を列挙し、実際の階層番号として存在すれば加算
- 非暴力的な解法もある
コード
- ans は初期化を忘れずに～
- if の中に ++ 操作だけがある場合、統合できる

HZOJ-514：マッチ棒の等式#

サンプル入力

サンプル出力

考え方
- 各数字に対応するマッチ棒の数は固定されている
- 範囲の推定（最大 24 本のマッチ棒）
  - 111 + 111 左側の最大の数？
  - 実際には 0、1 とも組み合わせることができる
  - 範囲はさらに大きくなる：0 ~ 2000
  - 加数 1、加数 2 は繰り返し可能
- 暴力的な列挙
  - 2 つの加数を列挙し、和が条件を満たすか確認👈中継関数 + 苦力関数
コード
- 列挙👉中継👉苦力

HZOJ-515：比率簡略化#

サンプル入力

1498 902 10

サンプル出力

5 3

考え方
- 範囲は大きくなく、L の上限は 100
- 小から大に列挙
  - 二重ループ
  - 互いに素であるかどうかを判断する必要はなく、存在すれば、前に条件を満たす互いに素の答えが必ずある
- 列挙→判断→保持→最も適した答えを出す
コード

HZOJ-516：牛の碑文#

サンプル入力

6
COOWWW

サンプル出力

考え方
- 方法 1：直接列挙、三重ループ？❌過度に暴力的、O (N ^ 3)
- 方法 2：空間を時間に変える
  - 各 O に対して、COW の数 = 前の C の数 * 後の W の数
  - 配列を 2 回走査し、O (N)
    - 前方和：この位置までに C が何個あるか
    - 後方和：この位置までに W が何個あるか
  - 配列をもう一度走査し、O を見つける O (N)
    - ans + 前 C 数 * 後 W 数
  - 時間：O (N) 空間：O (N)
- 引き伸ばし：PUSH を数える、時間計算量 O (N ^ 2)
  - 2 回走査し、前方和 P、後方和 H を数える
  - U を見つけた後、S を見つけてカウント
  - 後のコードにある「同時に探す」テクニックを参考にすれば、後方和配列の空間を省略できるはず
コード
- 後方和を「同時に探す」O で、後方和配列の空間を節約した
- int 型の掛け算はオーバーフローに注意

HZOJ-517：三角形の数#

サンプル入力

サンプル出力

考え方
- 重要なのは重複する三角形がないこと
  - 列挙方法を決定し、辺の大きさに基づいて列挙
  - 短辺 i：1 ~ n / 3
  - 中辺 j：i ~ (n - i) / 2
  - 長辺：n - i - j < i + j が成立すれば ans++
- 大きさの辺を決定すれば、重複を避けることができる
コード
- 最短辺→次短辺を列挙し、重複しないことを保証

HZOJ-519：優雅な数#

サンプル入力

110 133

サンプル出力

考え方
- 優雅な数：一つの数字だけが異なり、他はすべて同じ
- 列挙問題
- ❌直接列挙して優雅な数かどうかを判断すると、量が大きすぎる！10 ^ 16
- まず優雅な数YYXYYYYY を列挙し、その後区間内にあるか判断
  - 5 重ループ
  1. Y を列挙（一群の数）
  2. X を列挙（一つの数）：X が Y と等しい場合は continue
  3. 数の長さ：3 ~ 17
  4. X の位置：1 ~ 数の長さ
    - X、Y のいずれかが 0 の場合、先頭 0 があってはならない
    - X が 0 の場合、X は最初の位置にあってはならない；Y が 0 の場合、X は必ず最初の位置にある
  5. 優雅な数を構築し、区間内にあるか判断
コード
- 別の角度から列挙するのは非常に巧妙
- 一つの数は数字、数字の長さ、数字の位置によって決まる

追加知識点#

超大配列を定義する必要がある場合や他の関数でその配列を使用する必要がある場合、グローバル変数として定義し、ヒープスペースを開くのが最善です

考察点#

string str; //cin >> str は cin >> &str [0] と等価
❓オブジェクトに関わる場合、取址操作は使用しない方が良い
- これについては後で注意

ヒント#

コースの速記#

HZOJ-506
- 出力時 1.0 の型を上げる