/ 最近 .rdf 追記 編集 設定 本棚

log[20201107] AtCoder Beginner Contest 015D 問題 高橋くんの苦悩



20201107()

最終更: 2021-05-07T15:06+0900

[AtCoder] AtCoder Beginner Contest 015D 問題 高橋くんの苦悩

DP の基本形といっていいほど典型的な DP見え見えの誘いに乗りたくなくて他の解法を考えてみたけど思い付かなかったそれに心配しなくても Ruby ならではのお楽しみポイトがちゃんとあった

実行時間の変遷が見どころ

 提出 #17933561 (TLE×7 / AC×40)

N×K×W のループは上限が2500万回でありRubyTLE を避けようと思ったら桁を1つ減らさないといけない予想された結果

 提出 #17934141 (AC / 1033 ms)

N のループが K 回に達するまでは K のループを K 回まわす必要がないよねっていう節約作戦で AC になった制約は K <= N <= 50

 提出 #17934762 (AC / 554 ms)

提出一覧1000 ms を超えるグループと超えないグループに分かれていたので中を見たら添字と値が入れ違っていた

  • 遅い方 - Array[K][W] = sum of B (K<=50, W<=10000)
  • 速い方 - Array[K][sum of B] = W (N<=50, B<=100, sum of B<=5000)

B の値域が(W にくらべて)かなり狭い範囲に限定されているのがポイトで速い方はループで走査する DP 配列のサイズがおよそ半分で済む

 提出 #17935118 (AC / 111 ms)

2番手以降の集団をダブルスコアで突き放す zazaboon さんの提出 #11417636 (150 ms) を調べた結果

  • DP 配列のサイズを制約上の上限ではなくトケースに応じた必要最小限のサイズにする
  • B を小さい順に処理することによりープの初期に更新する DP 配列の範囲を限定する
  • 答えを見つけたら即終了する

以上の点を真似したのに加えて考えられるこちらのドバンテージが

  • Ruby のバージョンが上がっている(2.32.7)
  • 最初に簡単なチックで N を減らした
  • 初期値を整数にした(とりあえず大きな数としての初期値に Float::INFINITY を使うと10**9 のような整数型を使うより比較にコトがかかる)
  • 演算子を極力書かないようにした(vsum+1 は美意識とボキャブラリに起因する例)
  • 配列参照を極力書かないようにした特に二重のものはひとつも書かなかった
  • 見た目がださくても a = [a,b].min と書くより a = b if b < a と書いて代入を省略できる方が速い(だけど本当は宣言的な変数定義がしたい操作ではなく結果について書きた)
  • よくわからない処理を真似しなかった41 行目の if44 行目

前後のリトを比べると後ろは問題と関係のない比較的どうでもいい内容が並んでいるね

 Python のこの提出 #287540 (AC / 66 ms)

いまのところの Python 最速AB 配列を幅対重要度比でソトしてからの DFS なんだけどすごいのが _greedy_by_width_greedy_by_num という先読み関数で探索の打ち切りを判断しているところそれでペイするんだってところと1枚のスクリーンシトを刻む発想が(って刻んだ画像の価値はゼロですよ常考)

使う使わないの二択だと比率がちっと悪くても残った隙間にぴったり収まる方が重要度を高められることがある先読みでその可能性を取りこぼしては答えを誤るだからあくまでも比率のいいスクリーンシトから使うったり収まらないなら切り取って収まる分だけ使うそういう考え

最近別の問題を自分が DFS で解いたときのことだけどっきの TLE 提出を微修正したら AC になった事前に XY 配列をソトするだ二択による手戻りを最小限にするために選択肢の優劣が明らかで覆りにくいものを最初に選ぶようにしたなんてぬるいやり方よりずっと突き詰めているすごいなあ