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

考え方
- 左下から出発するか、右上から始める
  - 横座標または縦座標を一単位ずつ移動する
  - 時間計算量：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/

サンプル出力

考え方
- 重要なのは赤枠の部分
- 三つのスコア計算の状況
  - 直接クリア：このラウンド 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：二人の渡河#

サンプル入力

サンプル出力

考え方
- まずソートする
- 四つの状況
  - 1 人
  - 2 人
  - 3 人：最も速い人が道具として使われる
  - 4 人
    - ①ランプを持つ速度が最も速いことを保証する
    - ②橋を渡る効率が最高（この時速い人が速く、遅い人が遅い場合）
    - 毎回二人を渡す最も速い状況を見つける
コード
- 二人ずつ計算することが巧妙で、二つの方法の最小を取る

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 は繰り返し可能
- 暴力的に列挙する
  - 二つの加数を列挙し、和が要求を満たすかどうかを確認👈中継関数 + 苦力関数
コード
- 列挙👉中継👉苦力

HZOJ-515：比率簡略化#

サンプル入力

1498 902 10

サンプル出力

5 3

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

HZOJ-516：牛の碑文#

サンプル入力

6
COOWWW

サンプル出力

考え方
- 方法 1：直接列挙、三重ループ？❌過度に暴力的、O (N ^ 3)
- 方法 2：空間を時間で交換する
  - 各 O に対して、作成できる COW の数 = 前の C の数 * 後の W の数
  - 配列を二回走査し、記録する O (N)
    - 前缀和：この位置までに C がいくつあるか
    - 後缀和：この位置までに W がいくつあるか
  - 配列を再走査し、O を見つける O (N)
    - ans + 前の C 数 * 後の W 数
  - 時間：O (N) 空間：O (N)
- 引き伸ばし：PUSH を統計し、時間計算量 O (N ^ 2)
  - 二回走査し、前缀和 P、後缀和 H を統計する
  - U を見つけた後、S を見つけてカウントする
  - 後のコードの中の「同時に見つける」技術を参考にすれば、後の後缀和配列の空間を省略できるはず、S を見つけた後に U を見つける
コード
- 後の後缀和を「同時に見つける」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 の型を向上させる