解いてないけど、この問題で出てきたよくある貪欲法の正当性について書く。

D - Manga Market

2つの店をi, jに訪れると仮定して、i->jの順に訪れた時にかかる時間をt1、j->iで訪れた時にかかる時間をt2とする。 この時 t1 < t2 なら i->j の順番に店を訪れた方が得、t1 > t2 なら B->A という順番に訪れた方が得であると言える。 (この問題ではどの店からどの店への移動も1単位時間で終わるため、今どの店にいるかはその後に影響を及ぼさないことに注意)

t1 < t2 という式を具体的に計算すると aj / (bj + 1) < ai / (bi + 1) という式になる。
よって f(i) = ai / (bi + 1) とした時に f が降順となるように i, j を訪れれば良い ... (1)

さてここからが本題。2つの店 i, j を訪れると仮定した場合に、どちらを先に訪れるべきかは f(i) が降順となるように並べれば良いことが分かったが、n店ある場合に f(i) が降順となるように sort し、その順に回るのが最適なのか。

これは実際最適で以下のように証明できる。

簡単のため、任意のiについてf(i)が異なると仮定する。

まず f(i) が最大となるような i を最初に訪れないような最適な訪問順が存在すると仮定する。 すると i の前に別の店 j を訪れることになるが、(1)より店 i, j の訪問順を j->i の順で訪問するよりも i->j の順番で訪問する方が速いことが分かっているので、これは最適な訪問順という仮定に矛盾する。 よって最適な訪問順では f(i) が最大となる i は最初に訪れる。

元の店の集合からf(i)が最大となるiを取り除いた集合についても同じことがいえて、これを繰り返すことで結局 f(i) を降順で並べた訪問順が最適となる。

よって、n店ある場合にもf(i)が降順となるような訪問順が最適であることがいえた。

これが正しい証明になっているか、また日本語として読めるものになっているか自信がない。まあどうせ誰も読まない馬末のブログだから気軽にかいて文章や証明を書く練習にしていきたい。 とはいえ今回は流石に殴り書きすぎるので今後はもうちょっと整理したいな。 帰納法で証明するなら店1つの集合から始めて店を増やしていく方向で証明した方がよかったかも。

短時間マラソンでこういう立ち回りをしたい

  • 目的
    • 長時間のマラソンは初動が多少悪くとも時間をかければなんとかなってしまうが、短時間マラソンではそうもいかない
    • よく短時間マラソンで迷走するので言語化して整理する
  • 問題理解
    • 問題を読む
    • できれば簡単な貪欲法、それが難しいなら何の工夫もないランダムでいいので初期解を作る
      • 問題を正しく理解することが重要なので、この段階では重い考察や重実装をするべきではない
    • スコア計算がジャッジと合うことを確認
      • 誤差が出る場合は誤読の可能性が高いので問題を読み直す
      • 場合によってはスコア計算の誤差を許容することもある(ケースバイケース)
  • 入力を確認する
    • テストケースが公開されている場合、テストケースに特化した方針を考えるのが効果的な場合がある
    • 特に去年のHash Codeでは5つほどのテストケースがありそれぞれ特徴的な入力になっていた
      • 制約によっては最適解求まるかも、ということは頭の片隅にいれておきたい。
  • 改善
    • 基本的には普通のマラソンと一緒だと思う
      • ただし、短時間マラソンでは焼きなませば高スコアという問題はあまり出題されない傾向な気がする(経験則)
      • 短時間なので重たい実装はなるべく避ける
  • 気を付けること
    • 変に作り込みすぎない
      • 本質的な改善がしにくくなりがち
      • 細かいところの改善をしても焼け石に水なことが多いので、大きな改善を考えた方がいい
    • 高速化するとそれなりにスコアの改善が見込める場合に限り高速化する
      • 高速化によりスコア改善が見込めるかどうかは、実行時間をn倍にすることでわかる
    • パラメータ調整に時間をかけすぎない
      • 短時間だとパラメータの調整よりも方針の違いで勝負が決まるため
      • ざっくりグリッドサーチをするというのを自動化できていると嬉しい(とはいえ手動でざっくり調整でも十分戦える)
    • バージョン管理というほどではないが、よかった解と今の解の差分くらいは確認できるようにしておいた方がいい
    • 短時間なので多少のリスクを負って実力に見合わない順位を狙う戦略は(個人戦なら)ありかなという気がする

普通のマラソンと変わらないところが多い気がする