思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 127 D - Integer Cards

f:id:hiro_kato:20190526161433j:plain

目次

結論

  1. すべての数字(書き換えの前後を区別せず)に対して,大きいものから N個を選んで合計を取る.

  2. 計算量を減らすための工夫として,各数字とその個数をペアで管理するようなデータ構造(プライオリティ・キュー,辞書(連想配列)など)を用いる.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

  • AtCoderのレートで緑下位

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

D - Integer Cards (400点)

発想・解法とそれらを引きだすための方法・解釈

最初の一歩は?

  • サンプルにしたがって,手元で計算してみる.

  • 整数 C_{j}が整数 A_{i}より大きく,かつ,使った回数が B_{j}回より少なければ書き換えることができ,整数の合計値の最大値を大きくできる.

  • 書き換えるときは, C_{j}が大きなものから順番に使うとよさそう(貪欲法のアプローチ).

考察のキモ(Key Insight)は?

  1. すべての数字(書き換えの前後を区別せず)に対して,大きいものから N個を選んで合計を取る.

  2. 数字をそのまま配列などで管理するとデータ量が多くなる(最大で O(N + BM)=10^{10}).このため,各数字とその個数をペアで管理するようなデータ構造(プライオリティ・キュー,辞書(連想配列)など)を用いるとよい.

どうしたら思いつけそうか?

  1. ある値 iから別の値 jに「書き換える」という操作を,数字の集合全体から「選択」する,という視点の転換.

  2. データのうち,重複している部分はないか?(=何かの方法でまとめられないか?)

解法の妥当性は?

  • 操作の順番そのものは,結果に影響しない.

  •  A_{i}を小さな値で2回以上書き換えるくらいなら,最初から大きな値を使えばよい.

  • 使える回数(枚数)が, 0からB_{j}回までとなっているところがミソ.ちょうど B_{j}回という条件なら,別解を考える必要がありそう(要検証)

実装のポイントは?

  • データの管理にcollections.Counter()を使用.数字をキーに割り当て,個数を値として保持している.

  • 数字(キー)で降順に並び替えるため,Sorted()とlambda式を併用.

docs.python.org

docs.python.org

docs.python.org

Python3による回答例

# -*- coding: utf-8 -*-


def main():
    from collections import Counter

    n, m = map(int, input().split())
    a = Counter(list(map(int, input().split())))

    for i in range(m):
        bi, ci = map(int, input().split())
        a[ci] += bi

    cards = sorted(a.items(), key=lambda x: x[0], reverse=True)
    ans = 0

    for number, count in cards:
        if n > count:
            ans += number * count
            n -= count
        else:
            ans += number * n
            print(ans)
            exit()


if __name__ == '__main__':
    main()

試行錯誤した過程

  • 書き換えの条件を列挙して,書き換える部分だけを切り出そうとした

    •  max(C_{j}) min(A_{i})よりも小さければ,そのまま.
  • 書き換える個数と合計を条件分岐で管理しようとした(考察と実装それぞれに時間を要した)

    • 数列 Aに対して,ある数字 C_{j}が入る位置を二分探索で調べようとした.

    • また, B_{j}回, Aの書き換えていない回数との最小値を取れば,書き換えられる回数を求められると思ったが,条件の考慮が不足していた.

得られた知識・知見

  • 数列で並び順が結果に影響しないときは,ソート済みとして考える.

  • 「書き換える」という操作を別の視点(今回の場合は,集合全体から選択)からみてみる

  • 対象データについて,操作の前後を区別せずに一つの集合として考えられないか?

  • 重複したデータ・操作をまとめられないか?

  • 標準ライブラリで,便利なデータ構造や関数がないか?

感想

  • 2,000人以上がACしており,参加者のレベルが加速度的に高まっているのを感じました.

  • 貪欲法に気がつけたところまでよかったです.ただ,実装で置き換える数字の個数の扱いを,条件式や二分探索などを使って自ら複雑にしてしまったところが反省点です.

  • すぬけさんの解説の丁寧さと明快さに感動しました.

参考

tayama-2.hatenadiary.org

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/05/26 作成
  • 2019/0x/xx 更新