ヒューリスティックコンテストの紹介
>100 Views
July 14, 25
スライド概要
（ダウンロード不可）
関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.1M
各ページのテキスト
ヒューリスティックコンテストの紹介 kuradai
ヒューリスティックコンテストとは？ ● 最良の解を求めることが難しい複雑な問題に対して、 どれだけ良い解を求められるかを競うコンテスト ● AtCoderではAHCにあたる ● AHCは不定期で行われていて、 期間が「４時間」のものと「１週間程度」のものがある
問題の紹介 ● AHC023 A - Crops on Grid ● 問題の特徴 ○ 問題文が長く、問題設定が複雑 ○ 入力として受け取るデータが大きい ○ 得点の計算式が与えられている
問題の要約 ● 農地 ○ 各区画に１つの作物を植えることができる ○ 農地内に水路が通っている ○ 出入り口は１か所 ● トラクタ 農地の例 ○ 作物を植えることと収穫することを行う ○ 水路の上を通過することはできない ○ 作物が植えられている区画を通過することはできない ● 作物 ○ 作物毎に植えなければならない時期と収穫時期が決まっている
問題の要約 ● 目標 ○ どの区画にいつどの作物を植えるのかの計画 を最適化して、できるだけ多くの作物を植えて収穫し、 得点を最大化する ○ 育つのに必要な時間が長い作物を植えた方が 得点が高い
アルゴリズムを考える ● ビジュアライザ ○ AHCではビジュアライザが問題ごとに付属している ○ 自分のプログラムが提出した結果について、 直感的にわかる形で見ることができる ○ 今回は「時期ごとの栽培状況」と 「区画ごとにどれほど得点を 得られたか」がわかる
アルゴリズムを考える ● アルゴリズム１ ○ 入口の１区画だけを使い収穫期間が長いものを植える ● ➡ 得点は99,775 ● 改善点 ○ 入口以外の区画を使用する
アルゴリズムを考える ● アルゴリズム２ ○ 最初にすべての区画に一斉に植える ○ 収穫が遅い作物を奥に植える ➡ 入口に近い順で収穫されるためトラクタが入れる ● ➡ 得点は15,160,100 ● 改善点 ○ すべての区画を一度ずつしか使用していない ➡ 一斉に植えることの回数を増やす
アルゴリズムを考える ● アルゴリズム３ ○ アルゴリズム２と同様の方法で２回一斉に植える ○ ２回目をどのタイミングにするのが良いかを全て試し、 得点が最大になるタイミングにする ● ➡ 得点は21,350,075 ● 改善点 ○ この方法をn回で一般化する ➡ 得点は23,642,100 ○ 全体ではなくいくつかに分ける
アルゴリズムを考える ● アルゴリズム４ ○ 全体ではなくいくつかに分けて、 それぞれに対してアルゴリズム３を行う ○ ランダムな区画をいくつか選んで、 すべての区画を最も近いものに 所属させてグループ分けする ● 改善点 ➡ 得点は30,270,775 ○ グループの大きさをそろえる ○ 時間いっぱい繰り返して最高得点を選ぶ ○ グループの数を最適化する
アルゴリズムを考える ● アルゴリズム５（自分の最終解答） ○ アルゴリズム４でグループの大きさ、数を最適化して、 時間いっぱいまで繰り返す ● ➡ 得点は34,582,175 ● ここからの改善点 ○ 通路となっている部分を活用する
AHCの個人的な楽しさ ● 自分のプログラムを少しずつ改良、拡充していく ➡ 大きなプログラムを作成できたことの達成感 ● ビジュアライザがあることで ○ 改良点を考えやすい ○ どれぐらい良くなったかがわかりやすい ● 改良のフィードバックが得点としてわかる