【ネタバレ注意】AHCの天才貪欲練習にオススメの問題まとめ

AtCoder Heuristic Contestにおいて上位を狙うには、ビームサーチや焼きなましなどの典型的な手法を適用するだけではなく、深い考察や賢い発想によって問題の本質を突くことが（問題によってその傾向の強弱はあるものの）求められ、ときに「天才貪欲」と呼ばれます。

いったいどうやって練習をすれば天才になれるのか…というのはヒューリスティック勢共通の悩みだと思うのですが、そこでオススメなのが、（以前の予選・本戦形式だった頃の） 日本橋ハーフマラソン本戦の問題 です。

本戦なので、細かい調整だけで上位が決まらないよう、良い方針を発想できた人が上位に来るようになることを考えて作られている
4時間で2問解く超短期コンテストなので問題がさほど重くなく、短いサイクルで練習できる
- （【ネタバレ注意】AHCの焼きなまし・ビームサーチ練習にオススメの問題まとめ - TERRYのブログからのコピペ）
AHCが始まる前は今ほど人々がヒューリスティックコンテストに慣れていないため、高順位相当の得点が取りやすくモチベになる

解説が見つかりづらいというデメリットはあるのですが、この記事である程度補完できればと思います。

それでは問題の紹介です。上位を取れる解法を発想するのにどれくらい飛躍がありそうかに応じて 天才度 を★で付けています。

石油王Xの憂鬱（天才度 ★☆☆☆☆ ）

第1回日本橋ハーフマラソン本戦A問題です。 atcoder.jp

スコアが売った量の2乗であることから、基本的には要求量が多い人だけを相手すれば良いことがわかります。要求量が少ない人がいる間に、要求量が多い人に売りやすい形を作れるよう準備しましょう。

この問題のように、何かを推定して答えるわけではないインタラクティブ問題では、（プレイアウトで評価するといったことをやるにしても）貪欲の良さが重要です。

Twitterまとめ: RCO presents 日本橋ハーフマラソン本戦 - posfie

ゲーム実況者Xのデフラグ（天才度 ★★☆☆☆ ）

第2回日本橋ハーフマラソン予選 B問題です。 atcoder.jp

座標が4万個・データのあるセクタが16000個あって操作回数が4000回と、対象全てに対して操作ができるだけの回数がなく、収束しないことが前提というこのようなケースも、良い貪欲を設計できたかが特に重要になるパターンです。
1手ずつ、できるだけ大きくスコアを改善できる操作を探すのが良いです。

ちなみに延長戦トップスコアは焼きなましのようです。遷移を限定することで操作順依存を無くして差分計算できる形になるのかな？

Twitterまとめ: 第2回 RCO日本橋ハーフマラソン予選 - posfie

ファーマーXの収穫計画（天才度 ★★☆☆☆ ）

第3回日本橋ハーフマラソン予選 B問題です。 atcoder.jp

いろいろな貪欲が考えられると思います。

「0回以上手入れして収穫するという一連の行動についての、得られるスコア/操作回数」のコスパが高い操作を選ぶ、という貪欲が有効でした。このような操作回数に制限のある設定の場合に、一般的に使える考え方だと思います。

Twitterまとめ: 第3回 RCO日本橋ハーフマラソン予選 - posfie

3-SAT（天才度 ★★★☆☆ ）

yukicoderで出題されたスコア問題です。 yukicoder.me

状態がただのbool配列で表せることからシンプルな焼きなましがまず見えるかもしれませんが、評価基準がSAT全体に対してのものではなく前からどれだけ満たせたかなので、前から順番に条件を満たせるように貪欲に状態を変更していく方針が有効でした。

コンテスト後のコメント

めくってそろえる（天才度 ★★★☆☆ ）

第3回日本橋ハーフマラソン本戦 A問題です。 atcoder.jp

まず基本的な方針（順位表のまんなか辺りに716992点で同点が並んでいるところ）を合わせられないと全くスコアが出ません。

そこまで行ければあとはボーナスステージ的に、妥当な考察を積んでいければスコアが上がっていくと思います。

解説スライドがあります。

Twitterまとめ: 第3回 RCO日本橋ハーフマラソン本戦 - posfie

まわしてそろえる（天才度 ★★★★☆ ）

第3回日本橋ハーフマラソン本戦 B問題です。 atcoder.jp

アルゴ的に構築をしていく実装が重い方針もありますが、そうではなく、ヒューリスティックに揃えるにはどうやればよいかを考えてみるとためになりそうな問題だと思います。上手い評価を設計しましょう。

詳しくは解説スライドに。

Twitterまとめ: 第3回 RCO日本橋ハーフマラソン本戦 - posfie

日本橋大渋滞（天才度 ★★★★☆ ）

第1回日本橋ハーフマラソン本戦B問題です。 atcoder.jp

シンプルな貪欲をやると大渋滞になって身動きが取れなくなるのをどう解決しますか、という問題です。
渋滞を回避してそれぞれの車がするする動いてくれる賢い戦略があります（ただし実装がそこそこ大変で、4時間とかでやろうとするものではないかもしれません）。

koyumeishiさんの解説が詳しいです。めちゃくちゃ詰めきっててすごい…

それ以外の解法として、乱択を使って徐々に合わせていくヒューリスティックな方法もあります。コンテスト時間内にやるならこちらの方針が本線になると思います。

Twitterまとめ: RCO presents 日本橋ハーフマラソン本戦 - posfie

ぐるぐる庭園（天才度 ★★★★★ ）

第2回日本橋ハーフマラソン本戦 A問題です。 atcoder.jp

（解法の全体像を映すとビジュアライザがあまりにネタバレ過ぎるので1ターン目の画像で…）

なんとなくジグザグに動くように道を作るんだろうなというのは想像できるところで、けど良いスコアを狙うにはその中にクリティカルな天才気付きが1つ必要です。（出題者の私は3日くらい取り組んだ時点でやっと気付きました…）
そしてそこから本番トップを超える点数を出すには、もう1つ重要な天才ポイントがあります。

簡単に解説スライドに記載あり。

Twitterまとめ: 第2回 RCO日本橋ハーフマラソン本戦 - posfie